Lambda 表达式是 Java 8 的新语法，可以极大地简化代码，增强语言的表达力。这里不赘述 Lambda 表达式的语法，主要从一道题目出发来说 Lambda 表达式的一个特性。
从前阵子开始，坚持每天在 LeetCode 做一道题。这是前话。今天在做这道题的时候，碰到一个问题，记录下来备忘。
从题目说起
题目本身很好理解：给几个区间，将其中重叠相交的合并，返回合并后的区间。
做法也不难：将区间按照"起点小的在前，起点一样的则终点小的在前"排序。
选定第一个区间 A，按序依次遍历剩下的区间 B，如果 B 的起点比 A 的终点小，则 A 和 B 可以合并。
不断重复这个选定第一个区间的操作，直至将所有可合并的区间进行合并。
最后返回剩下的区间即可。
按理说不难，做完之后，也能通过了。代码如下：
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (o1, o2) -> {
if (o1[0] != o2[0]) {
return Integer.compare(o1[0], o2[0]);
}
return Integer.compare(o1[1], o2[1]);
});
boolean[] vis = new boolean[intervals.length];
Arrays.fill(vis, true);
for (int i = 0; i < intervals.length; i++) {
if (!vis[i]) {
continue;
}
for (int j = i + 1; j < intervals.length; j++) {
if (intervals[j][0] <= intervals[i][1]) {
vis[j] = false;
if (intervals[i][1] < intervals[j][1]) {
intervals[i][1] = intervals[j][1];
}
}
}
}
int count = 0;
for (boolean v : vis) {
if (v) {
count++;
}
}
int[][] ans = new int[count][];
for (int i = 0, j = 0; i < intervals.length; i++) {
if (!vis[i]) {
continue;
}
ans[j++] = intervals[i];
}
return ans;
}
不太理解的是 LeetCode 上的执行时间是 84 ms，已经战胜 28.32 % 的 java 提交记录。我左思右想，这已经是 O(N) 复杂度的解法(当然还有常数级别的优化空间)，难道还能有更高效的做法？
效率差距的疑惑
于是我看了一下别人的解法，大体上是一样的，复杂的也是 O(N)。因为一些细节上的处理，会有常数级别的差距，但应该不至于有这么大的差距才对。
一开始怀疑是数据量很大，在遍历的过程需要访问当前数据和之前的数据，可能是在这时发生了取数据的耗时操作。于是尝试把需要比较的数据用临时变量存储下来。结果发现耗时并没有什么变化。
最后实在想不出来，于是照着别人的代码，一点点改，边改边看执行时间。
最后发现是排序这里的 lambda 表达式造成了效率的差距。
Java 的 Lambda
Google 搜索后看到了 Stack Overflow 上的这个提问 Java lambdas 20 times slower than anonymous classes。
可以看到 Lambda 表达式的一些特性：
- Lambda 表达式对应的类是在运行时动态生成的。运行时动态生成，并不是这里慢的原因。动态生成一个结构简单的类，比从外部资源加载同样的字节流要更快。
- 程序必须要加载用于生成 Lambda 类的框架，才能使用 Lambda 表达式。加载框架才是这里慢的原因。(Oracle JDK 使用 ASM 来实现。)
- 如果不考虑加载 Lambda 框架的时间，使用 Lambda 表达式的效率会比使用类高一点。
所以，程序使用 Lambda 表达式后慢的原因也就呼之而出了：LeetCode 执行提交的代码之前，没有使用到 Lambda 表达式。当执行我们的代码时，要先加载处理 Lambda 表达式的框架。加载框架的时间会算到程序的运行时间里。
进一步的验证
虽然原理已经知道，但也要用代码从实际来验证一遍。
- 就像该回答中提到的，定义更多的 Lambda 表达式，也不会对运行时间有明显的影响。
- 我自己也做了一个实验：在程序的一次运行期间，多次执行"合并区间"的操作。每次都使用相同的数据，可以明显看到第一次执行的时间明显比后面每一次的时间都要长。这也验证了的确存在"加载 Lambda 框架"这个步骤的存在，以及这个加载过程也是主要的耗时操作。
网友评论