为什么处理排序数组比未排序数组*慢*？ （Java 的 ArrayList.indexOf）

它看起来像缓存/预取效果。

线索是您比较双精度数（对象），而不是双精度数（基元）。当您在一个线程中分配对象时，它们通常在内存中按顺序分配。因此，当 indexOf 扫描一个列表时，它会遍历连续的内存地址。这对于 CPU 缓存预取启发式方法很有用。

但是在对列表进行排序之后，您仍然需要平均执行相同数量的内存查找，但这一次内存访问将是随机顺序的。

更新

Here is the benchmark 证明分配对象的顺序很重要。

Benchmark            (generator)  (length)  (postprocess)  Mode  Cnt  Score   Error  Units
ListIndexOf.indexOf       random   1000000           none  avgt   10  1,243 ± 0,031  ms/op
ListIndexOf.indexOf       random   1000000           sort  avgt   10  6,496 ± 0,456  ms/op
ListIndexOf.indexOf       random   1000000        shuffle  avgt   10  6,485 ± 0,412  ms/op
ListIndexOf.indexOf   sequential   1000000           none  avgt   10  1,249 ± 0,053  ms/op
ListIndexOf.indexOf   sequential   1000000           sort  avgt   10  1,247 ± 0,037  ms/op
ListIndexOf.indexOf   sequential   1000000        shuffle  avgt   10  6,579 ± 0,448  ms/op

我认为我们正在看到内存缓存未命中的影响：

创建未排序列表时

for (int i = 0; i < LIST_LENGTH; i++) {
    list.add(r.nextDouble());
}

所有双精度最有可能分配在连续的内存区域中。遍历它会产生很少的缓存未命中。

另一方面，在排序列表中，引用以混乱的方式指向内存。

现在，如果您创建一个具有连续内存的排序列表：

Collection.sort(list);
List<Double> list2 = new ArrayList<>();
for (int i = 0; i < LIST_LENGTH; i++) {
    list2.add(new Double(list.get(i).doubleValue()));
}

此排序列表与原始列表具有相同的性能（我的时间）。

作为确认 answer by wero 和 answer by apangin (+1!) 的简单示例：以下对两个选项进行简单比较：

创建随机数，并可选择对它们进行排序

创建序列号，并选择性地改组它们

它也不是作为 JMH 基准实现的，但与原始代码类似，只是稍作修改以观察效果：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class SortedListTest
{
    private static final long SLOW_ITERATION_MILLIS = 1000L * 3L;

    public static void main(String[] args)
    {
        int size = 100000;
        testBinarySearchOriginal(size, true);
        testBinarySearchOriginal(size, false);
        testBinarySearchShuffled(size, true);
        testBinarySearchShuffled(size, false);
    }

    public static void testBinarySearchOriginal(int size, boolean sort)
    {
        Random r = new Random(0);
        List<Double> list = new ArrayList<>(size);
        for (int i = 0; i < size; i++)
        {
            list.add(r.nextDouble());
        }
        if (sort)
        {
            Collections.sort(list);
        }
        list = new ArrayList<>(list);

        int count = 0;
        int nIterations = 0;
        long startTime = System.currentTimeMillis();
        do
        {
            int index = r.nextInt(size);
            if (index == list.indexOf(list.get(index)))
            {
                count++;
            }
            nIterations++;
        }
        while (System.currentTimeMillis() < startTime + SLOW_ITERATION_MILLIS);
        long duration = System.currentTimeMillis() - startTime;
        double slowFindsPerSec = (double) nIterations / duration * 1000;

        System.out.printf("Size %8d sort %5s iterations %10.3f count %10d\n",
            size, sort, slowFindsPerSec, count);
    }

    public static void testBinarySearchShuffled(int size, boolean sort)
    {
        Random r = new Random(0);
        List<Double> list = new ArrayList<>(size);
        for (int i = 0; i < size; i++)
        {
            list.add((double) i / size);
        }
        if (!sort)
        {
            Collections.shuffle(list);
        }
        list = new ArrayList<>(list);

        int count = 0;
        int nIterations = 0;
        long startTime = System.currentTimeMillis();
        do
        {
            int index = r.nextInt(size);
            if (index == list.indexOf(list.get(index)))
            {
                count++;
            }
            nIterations++;
        }
        while (System.currentTimeMillis() < startTime + SLOW_ITERATION_MILLIS);
        long duration = System.currentTimeMillis() - startTime;
        double slowFindsPerSec = (double) nIterations / duration * 1000;

        System.out.printf("Size %8d sort %5s iterations %10.3f count %10d\n",
            size, sort, slowFindsPerSec, count);
    }

}

我机器上的输出是

Size   100000 sort  true iterations   8560,333 count      25681
Size   100000 sort false iterations  19358,667 count      58076
Size   100000 sort  true iterations  18554,000 count      55662
Size   100000 sort false iterations   8845,333 count      26536

很好地表明时间正好与另一个相反：如果对随机数进行排序，则排序后的版本会更慢。如果序列号被打乱，那么打乱的版本会更慢。