为什么在 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 次浏览

为你的职业扫除障碍

通过完成课程获得认证

入门