为什么处理一个排好序的数组比未排序的数组要快？

阳光穿透心脏的1/2处 2024-03-27 02:24 84阅读 0赞

这是stack overflow上一个非常火热的问题：

![format_png][]

为什么对数组排序能提高执行效率？先看下面的代码，执行分为：

1.  生成随机数放入数组
2.  对数组进行排序
3.  对数组中的数字进行累加

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);
        }
    }
    复制代码

排序后的执行时间：2.2350021s 未排序后的执行时间：6.385857s

可以发现：**排序后的执行时间是未排序的执行时间的3倍。**

为什么会这样，这就跟分支预测有关系，什么是分支预测呢？

计算机在执行某一条指令的过程中，会分为四个步骤：

![ed5aa72b73f6b2e11b17f3db105166e8.png][]

每个步骤会有对应的电路组件负责。

假设现在有一段程序对应的计算机指令为：

![a2cda34e8600728d67b7918962c524c3.png][]

那么计算机应该先执行指令1，然后根据指令1的结果看接下来应该执行哪条指令，假设接下来要执行的就是指令2，那指令流水线会是下图吗？

![format_png 1][]

假设每个步骤要1毫秒，那执行完这两条指令就需要8毫秒，但是前面说过，指令的四个步骤是由特定的组件来执行的，所以其实可以这么执行：

在解码指令1的过程中，就可以读取指令2了，这样执行完两条指令只需要5毫秒，如果后续指令也按这个节奏执行，那么效率提升会很大，比如串行执行3条指令需要3\*4=12毫秒，而并行执行3条指令只需要6毫秒，快了一倍了。

那这个跟分支预测有什么关系呢？

我们在来看

![1ee9463bbf947b7c6c592ba09740f347.png][]

假如指令2是一条判断指令，根据判断结果，要么执行指令3，要么执行指令4。

如果不对判断结果进行预测，那么就只能等指令2执行完之后才知道接下来要执行哪条指令，那指令流水线就是下面这样：

![f3fdb7d0fe7f4b9e876fa0251af3f746.png][]

执行这三条指令要9毫秒。

但是，如果在执行指令2之前，我们就能预测出指令2的判断结果，假如预测的是指令3，那么指令流水线就可以这样：

![format_png 2][]

相当于在解码指令2的时候，就同时去读取指令3，如果执行完指令2后，发现判断结果和预测的结果**是一致的**，那么就可以直接把指令3的结果写回了，这样就大大提高效率，执行这3条指令只需要6毫秒。

当然如果执行完指令2后，发现预测错了，那么就不能把指令3的结果写回了，而是得读取并执行正确的指令。

以上就是分支预测，简单总结一下就是，计算机会对分支，比如判断指令的结果进行预测，从而提前去做一些事情，而不是等判断结果出来后才去做事情。

回到上面的Java代码：

for (int c = 0; c < arraySize; ++c) {
        if (data[c] >= 128)
            sum += data[c];
    }
    复制代码

if语句就相当于是一个判断指令，根据判断结果就会有两个分支：

1.  要么进行累加
2.  要么取数组中的下一个数字。

所以，当执行if语句时，计算机就可以进行预测:

1.  比如预测当前判断的数字是大于128的，那么就可以在判断结果没有出来之前提前进行累加
2.  或者预测当前判断的数字是小于128的，那么就可以在判断结果没有出来之前提前取下一个数字

只要预测对了，就能提高执行效率，所以，我们要做的就是尽可能让计算机能预测准确，这就是**数组排序的作用**。

比如计算机在执行指令过程中，发现连续10个数字都是大于128的，那么就可以预测接下来的一个数字也是大于128的，所以只要数组是排好序的，那么这个预测就是正确的，从而也就提高了执行效率。

以上，就是分支预测，不知道大家看明白没...

作者：Hoeller  
链接：https://juejin.cn/post/7188781090986721339

[format_png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/99a8de166a654c1096dd9fb2df3faa57.png
[ed5aa72b73f6b2e11b17f3db105166e8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/e7667d1a36934a6fb54446738c19080b.png
[a2cda34e8600728d67b7918962c524c3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/311d32395e0f4f6eaf9904d212460748.png
[format_png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/df6b1d6ae23846bd963e33ad2e6e1627.png
[1ee9463bbf947b7c6c592ba09740f347.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/1f02ffdba13d42b6b4ac10430459b9cf.png
[f3fdb7d0fe7f4b9e876fa0251af3f746.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/002a20610ee546ec9de3bf2bded40951.png
[format_png 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/9a56eac20ef64d5ea1566ce424329dd6.png