SO面试题11：为什么排序后的数组要比未排序数组运行快3倍以上？

周末，在 stackoverflow 上面发现一个有趣的问题：Why is it faster to process a sorted array than an unsorted array?

提问者用256的模数随机填充一个固定大小的大数组，然后对数组的一半元素求和，并分别用 C++ 和 Java 代码来证实了这一现象，本文主要用 Java 来说明，代码如下。

我通过 IDEA 运行发现，先排序后计算比不排序直接计算快三倍。

那么，问题来了，本例子中的代码在数组填充时已经加入了分区函数，充分保证填充值的随机性，计算时也是按一半的元素来求和，所以不存在特例情况。而且，计算也完全不涉及到数据的有序性，即数组是否有序理论上对计算不会产生任何作用。在这样的前提下，为什么排序后的数组要比未排序数组运行快3倍以上？

我看获赞最高的答案提到了一个关键字：分支预测器。

它的英文名叫做 Branch predictor，是一种数字电路，在分支指令执行结束之前猜测哪一路分支将会被运行，以提高处理器的指令流水线的性能。使用分支预测器的目的，在于改善指令管线化的流程。—— 引自维基百科

这个分支预测器，跟在无线电还未普及的 19 世纪的铁路交叉口的扳道工很相似，假如你就是一个搬道工，当听到火车快来了的时候，你无法猜测它应该朝哪个方向走。于是你叫停了火车，上前去问火车司机该朝哪个方向走，以便你能正确地切换铁轨。

要知道，火车是非常庞大的，切急速行驶时有巨大的惯性。为了完成上述停车-问询-切轨的一系列动作，火车需耗费大量时间减速，停车，重新开启。

既然上述过程非常耗时，那是否有更好的方法？当然有！当火车即将行驶过来前，你可以猜测火车该朝哪个方向走。

如果猜对了，它直接通过，继续前行。

如果猜错了，车头将停止，倒回去，你将铁轨扳至反方向，火车重新启动，驶过道口。

如果你不幸每次都猜错了，那么火车将耗费大量时间，停车-倒回-重启。

如果你很幸运，每次都猜对了呢？火车将从不停车，持续前行！

我相信谁都不会一直都有好运，那有没有好的方法使得每次猜对的几率变大呢？是有的，可以通过小旗子来作为信号判断火车的走向。

是不是很形象？这样你就知道引起本文代码出现这一现象的关键原因在于分支跳转指令。

那么问题又来了，处理器是采用什么策略用最小的次数来尽量猜对指令分支的下一步走向呢？

一般来说，对于处理器而言，只能利用历史运行记录来进行分析。

由于上例 data 数组里的元素是按照 0-255 的值被均匀存储的，数组 data 有序时，前面一半元素的迭代将不会进入 if-statement，超过一半时，元素迭代将全部进入 if-statement。

具体分析如下。

有序数组的分支预测流程：

无序数组的分支预测流程：

所以，咱们可以得出结论：造成无序数组耗时较多的原因在于它迭代过程中 50% 的错误率。

那问题来了，对于这个例子，有没有好的优化方案呢？

是有的，可以利用位运算来取消分支跳转，代码如下。

更多的位运算 hack 操作，可以参考 bithacks。

这个例子是不是很有趣啊？

如果你涨知识了，记得转发哦。

参考

• https://en.wikipedia.org/wiki/Branch_predictor

• http://graphics.stanford.edu/~seander/bithacks.html

• https://stackoverflow.com/questions/11227809/why-is-it-faster-to-process-a-sorted-array-than-an-unsorted-array

 往期推荐 

🔗

 

点击阅读原文，获得更多精彩内容