Lambda 表達(dá)式是 Java 8 的新語法局雄，可以極大地簡化代碼，增強(qiáng)語言的表達(dá)力型豁。這里不贅述 Lambda 表達(dá)式的語法尚蝌，主要從一道題目出發(fā)來說 Lambda 表達(dá)式的一個(gè)特性。
從前陣子開始衣形，堅(jiān)持每天在 LeetCode 做一道題姿鸿。這是前話。今天在做這道題的時(shí)候苛预，碰到一個(gè)問題，記錄下來備忘腻菇。
從題目說起
題目本身很好理解：給幾個(gè)區(qū)間，將其中重疊相交的合并糖耸，返回合并后的區(qū)間。
做法也不難：將區(qū)間按照"起點(diǎn)小的在前嘉竟，起點(diǎn)一樣的則終點(diǎn)小的在前"排序洋侨。
選定第一個(gè)區(qū)間 A，按序依次遍歷剩下的區(qū)間 B妥粟，如果 B 的起點(diǎn)比 A 的終點(diǎn)小贸伐，則 A 和 B 可以合并哑舒。
不斷重復(fù)這個(gè)選定第一個(gè)區(qū)間的操作播急，直至將所有可合并的區(qū)間進(jìn)行合并桩警。
最后返回剩下的區(qū)間即可昌妹。
按理說不難，做完之后烂叔，也能通過了固歪。代碼如下：
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 上的執(zhí)行時(shí)間是 84 ms牢裳，已經(jīng)戰(zhàn)勝 28.32 % 的 java 提交記錄。我左思右想忘朝，這已經(jīng)是 O(N) 復(fù)雜度的解法(當(dāng)然還有常數(shù)級別的優(yōu)化空間)伶椿，難道還能有更高效的做法？
效率差距的疑惑
于是我看了一下別人的解法导狡，大體上是一樣的偎痛，復(fù)雜的也是 O(N)。因?yàn)橐恍┘?xì)節(jié)上的處理枚赡，會有常數(shù)級別的差距谓谦，但應(yīng)該不至于有這么大的差距才對反粥。
一開始懷疑是數(shù)據(jù)量很大，在遍歷的過程需要訪問當(dāng)前數(shù)據(jù)和之前的數(shù)據(jù)才顿，可能是在這時(shí)發(fā)生了取數(shù)據(jù)的耗時(shí)操作郑气。于是嘗試把需要比較的數(shù)據(jù)用臨時(shí)變量存儲下來。結(jié)果發(fā)現(xiàn)耗時(shí)并沒有什么變化忙芒。
最后實(shí)在想不出來讳侨，于是照著別人的代碼，一點(diǎn)點(diǎn)改甘桑，邊改邊看執(zhí)行時(shí)間歹叮。
最后發(fā)現(xiàn)是排序這里的 lambda 表達(dá)式造成了效率的差距。
Java 的 Lambda
Google 搜索后看到了 Stack Overflow 上的這個(gè)提問 Java lambdas 20 times slower than anonymous classes德谅。
可以看到 Lambda 表達(dá)式的一些特性：
- Lambda 表達(dá)式對應(yīng)的類是在運(yùn)行時(shí)動(dòng)態(tài)生成的萨螺。運(yùn)行時(shí)動(dòng)態(tài)生成愧驱，并不是這里慢的原因椭盏。動(dòng)態(tài)生成一個(gè)結(jié)構(gòu)簡單的類，比從外部資源加載同樣的字節(jié)流要更快掏颊。
- 程序必須要加載用于生成 Lambda 類的框架，才能使用 Lambda 表達(dá)式盆偿。加載框架才是這里慢的原因准浴。(Oracle JDK 使用 ASM 來實(shí)現(xiàn)。)
- 如果不考慮加載 Lambda 框架的時(shí)間句旱，使用 Lambda 表達(dá)式的效率會比使用類高一點(diǎn)晰奖。
所以匾南，程序使用 Lambda 表達(dá)式后慢的原因也就呼之而出了：LeetCode 執(zhí)行提交的代碼之前，沒有使用到 Lambda 表達(dá)式蛆楞。當(dāng)執(zhí)行我們的代碼時(shí)豹爹，要先加載處理 Lambda 表達(dá)式的框架。加載框架的時(shí)間會算到程序的運(yùn)行時(shí)間里光稼。
進(jìn)一步的驗(yàn)證
雖然原理已經(jīng)知道孩等，但也要用代碼從實(shí)際來驗(yàn)證一遍。
- 就像該回答中提到的冰垄，定義更多的 Lambda 表達(dá)式虹茶，也不會對運(yùn)行時(shí)間有明顯的影響。
- 我自己也做了一個(gè)實(shí)驗(yàn)：在程序的一次運(yùn)行期間蝴罪，多次執(zhí)行"合并區(qū)間"的操作。每次都使用相同的數(shù)據(jù)感局，可以明顯看到第一次執(zhí)行的時(shí)間明顯比后面每一次的時(shí)間都要長暂衡。這也驗(yàn)證了的確存在"加載 Lambda 框架"這個(gè)步驟的存在狂巢，以及這個(gè)加載過程也是主要的耗時(shí)操作书聚。
