I am practicing leetcode and oftenTimes I see different ways of reversing data structures. I was wondering if there is a benefit to doing it one way vs the other?
For example to create a max heap from a PriortiyQueue i can
PriorityQueue<Integer> heap = new PriorityQueue<>((a,b) -> b-a);
or
PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
Is the time and space complexity the same? Should i be defaulting to use a comparator or is the collections.reverseOrder() good?
CodePudding user response：
The first Comparator (one with lambda) is wrong because it is subject to integer overflow (for example, with b = Integer.MIN_VALUE and a > 0, this would return a positive value, not a negative one), you should use:
PriorityQueue<Integer> heap = new PriorityQueue<>((a,b) -> Integer.compare(b, a));
Which is also called by Integer.compareTo, which is called by reverseOrder.
As said in other answer, you should use the reverseOrder or Comparator.reversed() because it make the intention clear.
Now, for your question in depth, you should note that:
- The lambda
(a, b) -> b - ais affected by unboxing and should be readb.intValue() - a.intValue()and since this one is not valid for some values due to integer overflow: it should beInteger.compare(b.intValue(), a.intValue()). - The
reverseOrdersimply callsb.compareTo(a)which callsInteger.compare(value, other.value)where value is the actual value of the boxedInteger.
The performance difference would amount to:
- The cost of the two unboxing
- Cost of calling methods.
- The JVM optimization
You could wind up a JMH test (like the one below, based on another that I wrote for another answer): I shortened the values v1/v2 does to 3 because it takes times (~40m).
package stackoverflow;
import java.util.*;
import java.util.stream.*;
import java.util.concurrent.TimeUnit;
import org.openjdk.jmh.annotations.*;
import org.openjdk.jmh.infra.Blackhole;
@State(Scope.Benchmark)
@Warmup( time = 1, timeUnit = TimeUnit.SECONDS)
@Measurement( time = 1, timeUnit = TimeUnit.SECONDS)
@Fork(1)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@BenchmarkMode({ Mode.AverageTime})
public class ComparatorBenchmark {
private List<Integer> values;
@Param({ "" Integer.MIN_VALUE, "" Integer.MAX_VALUE, "10", "-1000", "5000", "10000", "20000", "50000", "100000" })
private Integer v1;
@Param({ "" Integer.MIN_VALUE, "" Integer.MAX_VALUE, "10", "1000", "-5000", "10000", "20000", "50000", "100000" })
private Integer v2;
private Comparator<Integer> cmp1;
private Comparator<Integer> cmp2;
private Comparator<Integer> cmp3;
@Setup
public void setUp() {
cmp1 = (a, b) -> Integer.compare(b, a);
cmp2 = (a, b) -> b - a;
cmp3 = Collections.reverseOrder();
}
@Benchmark
public void with_Integer_compare(Blackhole blackhole) {
blackhole.consume(cmp1.compare(v1, v2));
}
@Benchmark
public void with_b_minus_a(Blackhole blackhole) {
blackhole.consume(cmp2.compare(v1, v2));
}
@Benchmark
public void with_reverse_comparator(Blackhole blackhole) {
blackhole.consume(cmp3.compare(v1, v2));
}
}
Running this on:
- Windows 10
- Java 17.0.2
- AMD Ryzen 7 2700X @ 3.70 GHz
Produces the following result (I limited it to 3 values: MIN_VALUE, MAX_VALUE and 10 because its ETA is ~40m):
Benchmark (v1) (v2) Mode Cnt Score Error Units
ComparatorBenchmark.with_Integer_compare -2147483648 -2147483648 avgt 5 1,113 ± 0,074 ns/op
ComparatorBenchmark.with_Integer_compare -2147483648 2147483647 avgt 5 1,111 ± 0,037 ns/op
ComparatorBenchmark.with_Integer_compare -2147483648 10 avgt 5 1,111 ± 0,075 ns/op
ComparatorBenchmark.with_Integer_compare 2147483647 -2147483648 avgt 5 1,122 ± 0,075 ns/op
ComparatorBenchmark.with_Integer_compare 2147483647 2147483647 avgt 5 1,123 ± 0,070 ns/op
ComparatorBenchmark.with_Integer_compare 2147483647 10 avgt 5 1,102 ± 0,039 ns/op
ComparatorBenchmark.with_Integer_compare 10 -2147483648 avgt 5 1,097 ± 0,024 ns/op
ComparatorBenchmark.with_Integer_compare 10 2147483647 avgt 5 1,094 ± 0,019 ns/op
ComparatorBenchmark.with_Integer_compare 10 10 avgt 5 1,097 ± 0,034 ns/op
ComparatorBenchmark.with_b_minus_a -2147483648 -2147483648 avgt 5 1,105 ± 0,054 ns/op
ComparatorBenchmark.with_b_minus_a -2147483648 2147483647 avgt 5 1,099 ± 0,040 ns/op
ComparatorBenchmark.with_b_minus_a -2147483648 10 avgt 5 1,094 ± 0,038 ns/op
ComparatorBenchmark.with_b_minus_a 2147483647 -2147483648 avgt 5 1,112 ± 0,044 ns/op
ComparatorBenchmark.with_b_minus_a 2147483647 2147483647 avgt 5 1,105 ± 0,029 ns/op
ComparatorBenchmark.with_b_minus_a 2147483647 10 avgt 5 1,112 ± 0,068 ns/op
ComparatorBenchmark.with_b_minus_a 10 -2147483648 avgt 5 1,086 ± 0,010 ns/op
ComparatorBenchmark.with_b_minus_a 10 2147483647 avgt 5 1,125 ± 0,084 ns/op
ComparatorBenchmark.with_b_minus_a 10 10 avgt 5 1,125 ± 0,082 ns/op
ComparatorBenchmark.with_reverse_comparator -2147483648 -2147483648 avgt 5 1,121 ± 0,050 ns/op
ComparatorBenchmark.with_reverse_comparator -2147483648 2147483647 avgt 5 1,122 ± 0,067 ns/op
ComparatorBenchmark.with_reverse_comparator -2147483648 10 avgt 5 1,129 ± 0,094 ns/op
ComparatorBenchmark.with_reverse_comparator 2147483647 -2147483648 avgt 5 1,117 ± 0,046 ns/op
ComparatorBenchmark.with_reverse_comparator 2147483647 2147483647 avgt 5 1,122 ± 0,072 ns/op
ComparatorBenchmark.with_reverse_comparator 2147483647 10 avgt 5 1,116 ± 0,080 ns/op
ComparatorBenchmark.with_reverse_comparator 10 -2147483648 avgt 5 1,114 ± 0,052 ns/op
ComparatorBenchmark.with_reverse_comparator 10 2147483647 avgt 5 1,133 ± 0,068 ns/op
ComparatorBenchmark.with_reverse_comparator 10 10 avgt 5 1,134 ± 0,036 ns/op
As you can see, the score are within the same margin.
You would not gain/lose much from neither implementation, and as already said, you should use Collections.reverseOrder() to make your intention clear, and if not use Integer.compare, not a subtraction subject to integer overflow unless you are sure that each Integer is limited (for example, Short.MIN_VALUE to Short.MAX_VALUE).
CodePudding user response：
I think time and space complexity must be same because at the end your passing the comparator in both object creations so the only difference is :-
//passing specified comparator
PriorityQueue<Integer> heap = new PriorityQueue<>((a,b) -> b-a);
//Collection.reverseOrder will return comparator with natural reverse ordering
PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
CodePudding user response：
Yes, the time and space complexity is the same (constant).
Using Collections.reverseOrder() is better because it names the order explicitly, instead of making the reader read the implementation and infer the order.
CodePudding user response：
The asymptotics are the same, but Collections.reverseOrder() has several important advantages:
- It guarantees that it doesn't do an allocation. (
(a, b) -> b - aprobably doesn't allocate, either, butreverseOrderguarantees a singleton.) - It is clearly self-documenting.
- It works for all integers;
b-awill break if comparing e.g.Integer.MAX_VALUEand -2 due to overflow.