为什么对已排序数组求和比对未排序数组求和更快？

Question

我有一个ArrayList，其中的数字从 10 MM 到 20 MM

 List<Long> l = new ArrayList<>();
        for (long i = 10_000_000; i < 20_000_000; i++) {
            l.add(i);
        }

为什么sum()函数在排序数组上比在未排序数组上更快？

public class Main {

    public static void main(String[] args) {
        List<Long> l = new ArrayList<>();
        for (long i = 10_000_000; i < 20_000_000; i++) {
            l.add(i);
        }

        System.out.println(sum(l));

        Collections.shuffle(l);
        System.out.println(sum(l));

        Collections.sort(l);
        System.out.println(sum(l));
    }

    static long sum(List<Long> l) {
        long started = System.nanoTime();
        long result = 0;
        for (long v : l) {
            result += v;
        }
        System.out.println(" duration: " + (System.nanoTime() - started) / 1_000_000 + "ms");
        return result;
    }

}

我执行了sum()函数三次

• 第一次，在排序数组上
• 第二次未排序
• 第三次再次排序

在我的电脑上，执行时间是

1. 85毫秒

2. 250毫秒

3. 97毫秒

为什么sum()函数在排序数组上比在未排序数组上更快？

Answer 1

这与排序本身无关，而是与访问内存的顺序有关。

我将简要描述一些实验来证实这一点：

• 尝试使用long[]而不是ArrayList<Long>. 然后就没有单独分配的Long对象，只有一个直接包含数据的大数组。这使得内存访问顺序sum与数组的内容无关。我没有进行这个实验，因为编写代码需要更多的工作。

• 尝试使用随机排序的值初始化列表。我尝试了（我还把列表缩短了一点以节省时间）并得到了这个结果：

  duration: 31ms
  -6262510617230624864
  duration: 77ms
  -6262510617230624864
  duration: 160ms
  -6262510617230624864
  

  即最快的顺序与创建对象的顺序相同Long，与它们的值无关。

• 打乱后按顺序重新创建Long对象，例如：

    for (int i = 0; i < l.size(); i++)
        l.set(i, new Long(l.get(i)));
  

  这使得sum打乱列表的 再次变快（随后对列表进行排序会取消内存访问模式的顺序并sum再次变慢）。

实际上并不能保证Long一个接一个地分配的对象会在内存中以相同的顺序分配，但这是一种很常见的情况，当分配足够多的对象并且同时不会发生太多干扰时。