完全遍歷有序和無序的數組，時間復雜度都是O(n)，為什麼遍歷有序數組比無序數組速度更快？
下面是一個C++代碼，由於一些奇怪的原因，已排序的數據數組比未排序地數組運算差不多快6倍。
#include <algorithm>
#include <ctime>
#include <iostream>
int main()
{
// 生成數據
const unsigned arraySize = 32768;
int data[arraySize];
for (unsigned c = 0; c < arraySize; ++c)
data[c] = std::rand() % 256;
// !!! 排過序，接下來的循環運行會更快
std::sort(data, data + arraySize);
// 開始計時
clock_t start = clock();
long long sum = 0;
for (unsigned i = 0; i < 100000; ++i)
{
//主循環
for (unsigned c = 0; c < arraySize; ++c)
{
if (data[c] >= 128)
sum += data[c];
}
}
//結束計時
double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
std::cout << elapsedTime << std::endl;
std::cout << "sum = " << sum << std::endl;
}
std::sort(data, data + arraySize)，代碼運行時間為11.54s.起初，可能僅僅是語言或者編譯器的反常的原因，因此嘗試用JAVA實現。
import java.util.Arrays;
import java.util.Random;
public class Main
{
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);
}
}
結果跟前面的C++的情況，基本一致，也是排序過的數組比未排序的快很多。
根本原因是由於分支預測器引起的，下面詳細展開解釋
考慮一種鐵路連接器的場景：
為了解釋這樣現象，假設這是早在1800年，一個在長途或無線電通信出現之前的時代。
你是火車軌道連接器的操作員，你聽到火車來了。你根本不知道火車應該往哪個方向走。這時你需要讓火車停下車來，詢問他火車要往哪個方向走。然後你設置適當的開關。
列車是很重並且有很大的慣性，因此需要不停地啟動和減速。
有更好的方法嗎？假設提前猜測火車將要去往哪個方向！
如果你每一次都猜測對了，火車每次都不需要停下來。 如果你猜測錯的次數太頻繁，火車需要花很多時間停下來，回退，重新啟動。
考慮一個if語句，對於處理器的來說，它就是一個分支指令地址：
當處理器遇到分支，並不知道哪一條路該走，應該怎麼辦？ 處理器中止執行，等待前一條判斷語句執行完成。然後你繼續正確的線路。
現代的處理器是復雜的，有很長的管道。因此總是采取“預准備”和“減速”過程。
是否有更好的方法呢？提取猜測進入哪一條分支 - 如果猜測對了，繼續執行 - 如果猜測錯了，需要清空管道，分支回滾，然後重新進入另一個條分支。
如果每一次都猜測對了，處理器每次都不需要停下來。 如果猜測錯的次數太頻繁，處理器需要很多時間停止運轉，回滾，重新運行。
這就是分支預測。這可能不是最好的比喻，因為車可能在路上有信號和標志的方向。但在計算機中，處理器在最後一刻之前並不知道執行哪個分支。
所以，你如何策略性地猜測，使火車回退再進入另一個軌道的發生次數盡可能少？你看看過去的歷史！如果火車99％的時間往左走，那麼你猜測往左。如果左右交替發現，那麼你猜測火車也將交替選擇軌道。如果每3次進入一次某條軌道，你按這個邏輯猜想…
換言之，你試著發現規律並以相同的規律預測分支的選擇策略。這就是分支預測器的主要工作。
大多數的引用程序都有一個較好的分支行為。因此現代的分支預測器基本都能實現大於90%的命中率。但是面對無規律的不可預測的分支是，分支預測器就束手無策了。
關於分支預測，進一步閱讀“Branch predictor” article on Wikipedia.。
前面說到的奇怪現象， 就出在這個if語句：
if (data[c] >= 128)
sum += data[c];
數據隨機分布在0~255區間，當數據被排序，數據的前半部分應該不會進入if語句。之後的講都會進入if語句。 同一個分支連續進入很多次，這對於分支預測器來說是一個非常友好的。即使是簡單的計數器都能正確預測的這樣的分支，除非幾個迭代它切換方向之後。
快速可視化：
T = branch taken
N = branch not taken
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 (easy to predict)
然後，當數據完全是隨機生成的，分支預測器是無用的，因為它無法預測隨機的數據。因此這可能會發生50%左右的錯誤預測。(無異於隨時猜測)
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 ... (completely random - hard to predict)
我們能做什麼呢？
如果編譯器無法優化分支的進入，如果願意犧牲一些可讀性的話，那可以嘗試一些改進。
將原始方案：
if (data[c] >= 128)
sum += data[c];
替換優化方案為：
int t = (data[c] - 128) >> 31;
sum += ~t & data[c];
等效替換分析：
在分析之前，先將一下基本知識，
<< :左移運算符，num << 1，等價於num*2;
>> :右移運算符，num >> 1，等價於num/2; 空位以符號位來補齊
>>> :無符號右移，忽略符號位(最高位)，空位都以0補齊；
~： 非運算符，當位為0，則結果為1；，但位為1，則結果為0；
正式分析：
int t = (data[c] - 128) >> 31，根據帶符號的右移位運算法則，得到t=0，則~t=-1(即所有的位都為1); 從而~t & data[c] = data[c]，故等效sum += data[c];int t = (data[c] - 128) >> 31，根據帶符號的右移位運算法則，得到t=-1，則~t=0; 從而~t & data[c] = 0，故等效此未進入分支;這消除了分支預測，並與一些位運算來替換它的操作。 （這種方案並不能等價於原始的if語句。但是在當前的if語句情況下，對所有的data[]數值是有效的）
Benchmarks: Core i7 920 @ 3.5 GHz
C++ - Visual Studio 2010 - x64 Release
// 原始-隨機的
seconds = 11.777
// 原始-已排序的
seconds = 2.352
// 改進後-隨機的
seconds = 2.564
// 改進後-排序的
seconds = 2.587
Java - Netbeans 7.1.1 JDK 7 - x64
// 原始-隨機的
seconds = 10.93293813
// 原始-已排序的
seconds = 5.643797077
// 改進後-隨機的
seconds = 3.113581453
// 改進後-排序的
seconds = 3.186068823
觀察可知：
一般的經驗法則是避免在臨界循環數據依賴分支。(比如在這個示例中)
另外：
這一切都表明現代成熟的編譯器變在優化代碼上有能力做很多變化。
