今天周日，沒什么重要的事情要做，于是我早早的就醒來了?？戳艘粫?huì)渡邊淳一的書，內(nèi)心逐漸感到平靜——心情不佳的時(shí)候，書好像是最好的藥物。心情平靜了，就需要做一些更有意義的事情——逛技術(shù)網(wǎng)站，學(xué)習(xí)精進(jìn)。

Stack Overflow 是我最喜歡逛的一個(gè)網(wǎng)站，它是我 Chrome 瀏覽器的第一個(gè)書簽。

里面有很多很多經(jīng)典的問題，其中一些回答，剖析得深入我心。就比如說這個(gè)：“為什么處理排序后的數(shù)組比沒有排序的快？”

毫無疑問，直觀印象里，排序后的數(shù)組處理起來就是要比沒有排序的快，甚至不需要理由，就好像我們知道“夏天吃冰激凌就是爽，冬天穿羽絨服就是暖和”一樣。

但本著“知其然知其所以然”的態(tài)度，我們確實(shí)需要去搞清楚到底是為什么？

來看一段 Java 代碼：

/**
?*?@author?沉默王二，一枚有趣的程序員
?*/
public?class?SortArrayFasterDemo?{
????public?static?void?main(String[]?args)?{
????????//?聲明數(shù)組
????????int?arraySize?=?32768;
????????int?data[]?=?new?int[arraySize];

????????Random?rnd?=?new?Random(0);
????????for?(int?c?=?0;?c?????????????data[c]?=?rnd.nextInt()?%?256;
????????}

????????//?!!!?排序后，比沒有排序要快
????????Arrays.sort(data);

????????//?測(cè)試
????????long?start?=?System.nanoTime();
????????long?sum?=?0;

????????for?(int?i?=?0;?i?100000;?++i)
????????{
????????????//?循環(huán)
????????????for?(int?c?=?0;?c?????????????{
????????????????if?(data[c]?>=?128)?{
????????????????????sum?+=?data[c];
????????????????}
????????????}
????????}

????????System.out.println((System.nanoTime()?-?start)?/?1000000000.0);
????????System.out.println("sum?=?"?+?sum);
????}
}

這段代碼非常簡單，我來解釋一下：

• 聲明一個(gè)指定長度（32768）的數(shù)組。

• 聲明一個(gè) Random 隨機(jī)數(shù)對(duì)象，種子是 0；rnd.nextInt() % 256 將會(huì)產(chǎn)生一個(gè)余數(shù)，余數(shù)的絕對(duì)值在 0 到 256 之間，包括 0，不包括 256，可能是負(fù)數(shù)；使用余數(shù)對(duì)數(shù)組進(jìn)行填充。

• 使用 Arrays.sort() 進(jìn)行排序。

• 通過 for 循環(huán)嵌套計(jì)算數(shù)組累加后的結(jié)果，并通過 System.nanoTime() 計(jì)算前后的時(shí)間差，精確到納秒級(jí)。

我本機(jī)的環(huán)境是 Mac OS，內(nèi)存 16 GB，CPU ?Intel Core i7，IDE 用的是 IntelliJ IDEA，排序后和未排序后的結(jié)果如下：

排序后：2.811633398
未排序：9.41434346

時(shí)間差還是很明顯的，對(duì)吧？未排序的時(shí)候，等待結(jié)果的時(shí)候讓我有一種擔(dān)心：什么時(shí)候結(jié)束?。坎粫?huì)結(jié)束不了吧？

讀者朋友們有沒有玩過火炬之光啊？一款非常經(jīng)典的單機(jī)游戲，每一個(gè)場(chǎng)景都有一副地圖，地圖上有很多分支，但只有一個(gè)分支可以通往下一關(guān)；在沒有刷圖之前，地圖是模糊的，玩家并不知道哪一條分支是正確的。

如果僥幸跑的是一條正確的分支，那么很快就能到達(dá)下一關(guān)；否則就要往回跑，尋找正確的那條分支，需要花費(fèi)更多的時(shí)間，但同時(shí)也會(huì)收獲更多的經(jīng)驗(yàn)和聲望。

作為一名玩過火炬之光很久的老玩家，幾乎每一幅地圖我都刷過很多次，刷的次數(shù)多了，地圖差不多就刻進(jìn)了我的腦袋，即便是一開始地圖是模糊的，我也能憑借經(jīng)驗(yàn)和直覺找到最正確的那條分支，就省了很多折返跑的時(shí)間。

讀者朋友們應(yīng)該注意到了，上面的代碼中有一個(gè) if 分支——if (data[c] >= 128)，也就是說，如果數(shù)組中的值大于等于 128，則對(duì)其進(jìn)行累加，否則跳過。

那這個(gè)代碼中的分支就好像火炬之光中的地圖分支，如果處理器能夠像我一樣提前預(yù)判，那累加的操作就會(huì)快很多，對(duì)吧？

處理器的內(nèi)部結(jié)構(gòu)我是不懂的，但它應(yīng)該和我的大腦是類似的，遇到 if 分支的時(shí)候也需要停下來，猜一猜，到底要不要繼續(xù)，如果每次都猜對(duì)，那顯然就不需要折返跑，浪費(fèi)時(shí)間。

這就是傳說中的分支預(yù)測(cè)！

我需要刷很多次圖才能正確地預(yù)測(cè)地圖上的路線，處理器需要排序才能提高判斷的準(zhǔn)確率。

計(jì)算機(jī)發(fā)展了這么多年，已經(jīng)變得非常非常聰明，對(duì)于條件的預(yù)測(cè)通常能達(dá)到 90% 以上的命中率。但是，如果分支是不可預(yù)測(cè)的，那處理器也無能為力啊，對(duì)不對(duì)？

排序后花費(fèi)的時(shí)間少，未排序花費(fèi)的時(shí)間多，罪魁禍?zhǔn)拙驮?if 語句上。

if?(data[c]?>=?128)?{
????sum?+=?data[c];
}

數(shù)組中的值是均勻分布的（-255 到 255 之間），至于是怎么均勻分布的，我們暫且不管，反正由 Random 類負(fù)責(zé)。

為了方便講解，我們暫時(shí)忽略掉負(fù)數(shù)的那一部分，從 0 到 255 說起。

來看經(jīng)過排序后的數(shù)據(jù)：

data[]?=?0,?1,?2,?3,?4,?...?126,?127,?128,?129,?130,?...?250,?251,?252,?...
branch?=?N??N??N??N??N??...???N????N????T????T????T??...???T????T????T??...

???????=?NNNNNNNNNNNN?...?NNNNNNNTTTTTTTTT?...?TTTTTTTTTT

N 是小于 128 的，將會(huì)被 if 條件過濾掉；T 是將要累加到 sum 中的值。

再來看未排序的數(shù)據(jù)：

data[]?=?226,?185,?125,?158,?198,?144,?217,?79,?202,?118,??14,?150,?177,?182,?133,?...
branch?=???T,???T,???N,???T,???T,???T,???T,??N,???T,???N,???N,???T,???T,???T,???N??...

???????=?TTNTTTTNTNNTTTN?...???

完全沒有辦法預(yù)測(cè)。

對(duì)比過后，就能發(fā)現(xiàn)，排序后的數(shù)據(jù)在遇到分支預(yù)測(cè)的時(shí)候，能夠輕松地過濾掉 50% 的數(shù)據(jù)，對(duì)吧？是有規(guī)律可循的。

那假如說不想排序，又想節(jié)省時(shí)間，有沒有辦法呢？

如果你直接問我的話，我肯定毫無辦法，兩手一攤，一副無奈臉。不過，Stack Overflow 以上帝視角給出了答案。

把：

if?(data[c]?>=?128)?{
????sum?+=?data[c];
}

更換為：

int?t?=?(data[c]?-?128)?>>?31;
sum?+=?~t?&?data[c];

通過位運(yùn)算消除了 if 分支（并不完全等同），但我測(cè)試了一下，計(jì)算后的 sum 結(jié)果是相同的。

/**
?*?@author?沉默王二，一枚有趣的程序員
?*/
public?class?SortArrayFasterDemo?{
????public?static?void?main(String[]?args)?{
????????//?聲明數(shù)組
????????int?arraySize?=?32768;
????????int?data[]?=?new?int[arraySize];

????????Random?rnd?=?new?Random();
????????for?(int?c?=?0;?c?????????????data[c]?=?rnd.nextInt()?%?256;
????????}

????????//?測(cè)試
????????long?start?=?System.nanoTime();
????????long?sum?=?0;

????????for?(int?i?=?0;?i?100000;?++i)
????????{
????????????//?循環(huán)
????????????for?(int?c?=?0;?c?????????????{
????????????????if?(data[c]?>=?128)?{
????????????????????sum?+=?data[c];
????????????????}
????????????}
????????}

????????System.out.println((System.nanoTime()?-?start)?/?1000000000.0);
????????System.out.println("sum?=?"?+?sum);

????????//?測(cè)試
????????long?start1?=?System.nanoTime();
????????long?sum1?=?0;

????????for?(int?i?=?0;?i?100000;?++i)
????????{
????????????//?循環(huán)
????????????for?(int?c?=?0;?c?????????????{
????????????????int?t?=?(data[c]?-?128)?>>?31;
????????????????sum1?+=?~t?&?data[c];
????????????}
????????}

????????System.out.println((System.nanoTime()?-?start1)?/?1000000000.0);
????????System.out.println("sum1?=?"?+?sum1);
????}
}

輸出結(jié)果如下所示：

8.734795196
sum?=?156871800000
1.596423307
sum1?=?156871800000

數(shù)組累加后的結(jié)果是相同的，但時(shí)間上仍然差得非常多，這說明時(shí)間確實(shí)耗在分支預(yù)測(cè)上——如果數(shù)組沒有排序的話。

最后，不得不說一句，大神級(jí)程序員不愧是大神級(jí)程序員，懂得位運(yùn)算的程序員就是屌。

建議還在讀大學(xué)的讀者朋友多讀一讀《計(jì)算機(jī)操作系統(tǒng)原理》這種涉及到底層的書，對(duì)成為一名優(yōu)秀的程序員很有幫助。畢竟大學(xué)期間，學(xué)習(xí)時(shí)間充分，社會(huì)壓力小，能夠做到心無旁騖，加油！