我在这里看到了很多有关Java Lambda性能的问题，但大多数问题都像“ Lambda稍快，但使用闭包时变慢”或“预热与执行时间不同”或其他类似的问题。

但是，我在这里碰到了一件很奇怪的事情。考虑这个LeetCode问题：

给定一组不重叠的间隔，请在间隔中插入一个新间隔（必要时合并）。

您可以假设间隔最初是根据其开始时间排序的。

这个问题被贴上了标签，所以我认为线性方法不是他们想要的。因此，我决定想出一种巧妙的方法，将二进制搜索与对输入列表的修改相结合。现在，在修改输入列表时，问题还不是很清楚，即使签名需要返回对列表的引用，它也显示为“插入”，但现在不要紧。这是完整的代码，但是只有前几行与此问题相关。我将其余的保留在这里，以便任何人都可以尝试：

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;
}

这种方法运行良好并被接受，但运行时为80毫秒，而大多数解决方案为4-5毫秒和18-19毫秒。当我查找它们时，它们都是线性的并且非常原始。人们不会期望从标记为“困难”的问题中得到期望。

但是问题来了：在最坏的情况下，我的解决方案也是线性的（因为添加/清除操作是线性时间）。为什么 这么 慢？然后我这样做了：

    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);

从80毫秒降低到4毫秒！这里发生了什么？不幸的是，我不知道LeetCode在什么样的环境下运行什么样的测试，但是仍然不是20倍吗？