I've seen a lot of questions here about Java lambdas performance, but most of them go like "Lambdas are slightly faster, but become slower when using closures" or "Warm-up vs execution times are different" or other such things.
However, I hit a rather strange thing here. Consider this LeetCode problem:
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
The problem was tagged hard, so I assumed that a linear approach is not what they want there. So I decided to come up with a clever way to combine binary search with modifications to the input list. Now the problem is not very clear on modifying the input list—it says "insert", even though the signature requires to return a reference to list, but never mind that for now. Here's the full code, but only the first few lines are relevant to this question. I'm keeping the rest here just so that anyone can try it:
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
int start = Collections.binarySearch(intervals, newInterval,
(i1, i2) -> Integer.compare(i1.start, i2.start));
int skip = start >= 0 ? start : -start - 1;
int end = Collections.binarySearch(intervals.subList(skip, intervals.size()),
new Interval(newInterval.end, 0),
(i1, i2) -> Integer.compare(i1.start, i2.start));
if (end >= 0) {
end += skip; // back to original indexes
} else {
end -= skip; // ditto
}
int newStart = newInterval.start;
int headEnd;
if (-start - 2 >= 0) {
Interval prev = intervals.get(-start - 2);
if (prev.end < newInterval.start) {
// the new interval doesn't overlap the one before the insertion point
headEnd = -start - 1;
} else {
newStart = prev.start;
headEnd = -start - 2;
}
} else if (start >= 0) {
// merge the first interval
headEnd = start;
} else { // start == -1, insertion point = 0
headEnd = 0;
}
int newEnd = newInterval.end;
int tailStart;
if (-end - 2 >= 0) {
// merge the end with the previous interval
newEnd = Math.max(newEnd, intervals.get(-end - 2).end);
tailStart = -end - 1;
} else if (end >= 0) {
newEnd = intervals.get(end).end;
tailStart = end + 1;
} else { // end == -1, insertion point = 0
tailStart = 0;
}
intervals.subList(headEnd, tailStart).clear();
intervals.add(headEnd, new Interval(newStart, newEnd));
return intervals;
}
This worked fine and got accepted, but with 80 ms runtime, while most solutions were 4-5 ms and some 18-19 ms. When I looked them up, they were all linear and very primitive. Not something one would expect from a problem tagged "hard".
But here comes the question: my solution is also linear at worst case (because add/clear operations are linear time). Why is it that slower? And then I did this:
Comparator<Interval> comparator = new Comparator<Interval>() {
@Override
public int compare(Interval i1, Interval i2) {
return Integer.compare(i1.start, i2.start);
}
};
int start = Collections.binarySearch(intervals, newInterval, comparator);
int skip = start >= 0 ? start : -start - 1;
int end = Collections.binarySearch(intervals.subList(skip, intervals.size()),
new Interval(newInterval.end, 0),
comparator);
From 80 ms down to 4 ms! What's going on here? Unfortunately I have no idea what kind of tests LeetCode runs or under what environment, but still, isn't 20 times too much?
