先看再點贊，給自己一點思考的時間，微信搜索【沉默王二】關注這個有顏值卻假裝靠才華茍且的程式員，
本文 GitHub github.com/itwanger 已收錄，里面還有我精心為你準備的一線大廠面試題，
今天周日，沒什么重要的事情要做，于是我早早的就醒來了，看了一會渡邊淳一的書，內心逐漸感到平靜——心情不佳的時候，書好像是最好的藥物，心情平靜了，就需要做一些更有意義的事情——逛技術網站，學習精進，
Stack Overflow 是我最喜歡逛的一個網站，它是我 Chrome 瀏覽器的第一個書簽，里面有很多很多經典的問題，其中一些回答，剖析得深入我心，就比如說這個：“為什么處理排序后的陣列比沒有排序的快？”
毫無疑問，直觀印象里，排序后的陣列處理起來就是要比沒有排序的快，甚至不需要理由，就好像我們知道“夏天吃冰激凌就是爽，冬天穿羽絨服就是暖和”一樣，
但本著“知其然知其所以然”的態度，我們確實需要去搞清楚到底是為什么？
來看一段 Java 代碼：
/**
* @author 沉默王二，一枚有趣的程式員
*/
public class SortArrayFasterDemo {
public static void main(String[] args) {
// 宣告陣列
int arraySize = 32768;
int data[] = new int[arraySize];
Random rnd = new Random(0);
for (int c = 0; c < arraySize; ++c) {
data[c] = rnd.nextInt() % 256;
}
// !!! 排序后，比沒有排序要快
Arrays.sort(data);
// 測驗
long start = System.nanoTime();
long sum = 0;
for (int i = 0; i < 100000; ++i)
{
// 回圈
for (int c = 0; c < arraySize; ++c)
{
if (data[c] >= 128) {
sum += data[c];
}
}
}
System.out.println((System.nanoTime() - start) / 1000000000.0);
System.out.println("sum = " + sum);
}
}
這段代碼非常簡單，我來解釋一下：
宣告一個指定長度（32768）的陣列，
宣告一個 Random 亂數物件，種子是 0；
rnd.nextInt() % 256將會產生一個余數，余數的絕對值在 0 到 256 之間，包括 0，不包括 256，可能是負數；使用余數對陣列進行填充，使用
Arrays.sort()進行排序，通過 for 回圈嵌套計算陣列累加后的結果，并通過
System.nanoTime()計算前后的時間差，精確到納秒級，
我本機的環境是 Mac OS，記憶體 16 GB，CPU Intel Core i7，IDE 用的是 IntelliJ IDEA，排序后和未排序后的結果如下：
排序后：2.811633398
未排序：9.41434346
時間差還是很明顯的，對吧？未排序的時候，等待結果的時候讓我有一種擔心：什么時候結束啊？不會結束不了吧？
讀者朋友們有沒有玩過火炬之光啊？一款非常經典的單機游戲，每一個場景都有一副地圖，地圖上有很多分支，但只有一個分支可以通往下一關；在沒有刷圖之前，地圖是模糊的，玩家并不知道哪一條分支是正確的，
如果僥幸跑的是一條正確的分支，那么很快就能到達下一關；否則就要往回跑，尋找正確的那條分支，需要花費更多的時間，但同時也會識訓更多的經驗和聲望，
作為一名玩過火炬之光很久的老玩家，幾乎每一幅地圖我都刷過很多次，刷的次數多了，地圖差不多就刻進了我的腦袋，即便是一開始地圖是模糊的，我也能憑借經驗和直覺找到最正確的那條分支，就省了很多折返跑的時間，
讀者朋友們應該注意到了，上面的代碼中有一個 if 分支——if (data[c] >= 128)，也就是說，如果陣列中的值大于等于 128，則對其進行累加，否則跳過，
那這個代碼中的分支就好像火炬之光中的地圖分支，如果處理器能夠像我一樣提前預判，那累加的操作就會快很多，對吧？
處理器的內部結構我是不懂的，但它應該和我的大腦是類似的，遇到 if 分支的時候也需要停下來，猜一猜，到底要不要繼續，如果每次都猜對，那顯然就不需要折返跑，浪費時間，
這就是傳說中的分支預測！
我需要刷很多次圖才能正確地預測地圖上的路線，處理器需要排序才能提高判斷的準確率，
計算機發展了這么多年，已經變得非常非常聰明，對于條件的預測通常能達到 90% 以上的命中率，但是，如果分支是不可預測的，那處理器也無能為力啊，對不對？
排序后花費的時間少，未排序花費的時間多，罪魁禍首就在 if 陳述句上，
if (data[c] >= 128) {
sum += data[c];
}
陣列中的值是均勻分布的（-255 到 255 之間），至于是怎么均勻分布的，我們暫且不管，反正由 Random 類負責，
為了方便講解，我們暫時忽略掉負數的那一部分，從 0 到 255 說起，
來看經過排序后的資料：
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 的，將會被 if 條件過濾掉；T 是將要累加到 sum 中的值，
再來看未排序的資料：
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 ...
完全沒有辦法預測，
對比過后，就能發現，排序后的資料在遇到分支預測的時候，能夠輕松地過濾掉 50% 的資料，對吧？是有規律可循的，
那假如說不想排序，又想節省時間，有沒有辦法呢？
如果你直接問我的話，我肯定毫無辦法，兩手一攤，一副無奈臉，不過，Stack Overflow 以上帝視角給出了答案，
把：
if (data[c] >= 128) {
sum += data[c];
}
更換為：
int t = (data[c] - 128) >> 31;
sum += ~t & data[c];
通過位運算消除了 if 分支（并不完全等同），但我測驗了一下，計算后的 sum 結果是相同的，
/**
* @author 沉默王二，一枚有趣的程式員
*/
public class SortArrayFasterDemo {
public static void main(String[] args) {
// 宣告陣列
int arraySize = 32768;
int data[] = new int[arraySize];
Random rnd = new Random();
for (int c = 0; c < arraySize; ++c) {
data[c] = rnd.nextInt() % 256;
}
// 測驗
long start = System.nanoTime();
long sum = 0;
for (int i = 0; i < 100000; ++i)
{
// 回圈
for (int c = 0; c < arraySize; ++c)
{
if (data[c] >= 128) {
sum += data[c];
}
}
}
System.out.println((System.nanoTime() - start) / 1000000000.0);
System.out.println("sum = " + sum);
// 測驗
long start1 = System.nanoTime();
long sum1 = 0;
for (int i = 0; i < 100000; ++i)
{
// 回圈
for (int c = 0; c < arraySize; ++c)
{
int t = (data[c] - 128) >> 31;
sum1 += ~t & data[c];
}
}
System.out.println((System.nanoTime() - start1) / 1000000000.0);
System.out.println("sum1 = " + sum1);
}
}
輸出結果如下所示：
8.734795196
sum = 156871800000
1.596423307
sum1 = 156871800000
陣列累加后的結果是相同的，但時間上仍然差得非常多，這說明時間確實耗在分支預測上——如果陣列沒有排序的話，
最后，不得不說一句，大神級程式員不愧是大神級程式員，懂得位運算的程式員就是屌，
建議還在讀大學的讀者朋友多讀一讀《計算機作業系統原理》這種涉及到底層的書，對成為一名優秀的程式員很有幫助，畢竟大學期間，學習時間充分，社會壓力小，能夠做到心無旁騖，加油！
我是沉默王二，一枚有顏值卻假裝靠才華茍且的程式員，關注即可提升學習效率，別忘了三連啊，點贊、收藏、留言，我不挑，奧利給??，
注：如果文章有任何問題，歡迎毫不留情地指正，
如果你覺得文章對你有些幫助，歡迎微信搜索「沉默王二」第一時間閱讀，回復關鍵字「小白」可以免費獲取我肝了 4 萬+字的 《Java 小白從入門到放肆》2.0 版；本文 GitHub github.com/itwanger 已收錄，歡迎 star，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/73381.html
標籤：Java
上一篇：Java繼承后訪問成員的特點
下一篇：Java Map 遍歷史上最全