為什麼在 C++ 程式中處理一個已排序的陣列要比處理一個未排序的陣列更快？

在 C++ 中，處理一個已排序的陣列要比處理一個未排序的陣列更快，這是由於分支預測。在計算機體系結構中，分支預測確定程式中一條指令流中的一個條件分支（跳轉）是否可能被使用。

讓我們看一個示例

if(arr[i] > 50) {
   Do some operation B
} else {
   Do some operation A
}

如果我們針對未排序和已排序訂單中的 100 個元素執行此程式碼，則如下事件將會發生

對於已排序陣列

1,2,3,4,5,……50,51………100
A,A,A,A,A A,B B
It will load the correct branch in pipeline and correct sequence A,A,A, A,A,A,A,A A,B B

對於未排序陣列

5,51,6,90,4,49,60…
A,B,A,B,A,A,A,B

分支預測在此處不發揮顯著作用。很難預測 A 和 B 之間的正確運算。

詹妮弗·尼古拉斯

更新時間：2019 年 7 月 30 日

131 次瀏覽

為你的職業掃除障礙

透過完成課程獲得認證

入門