Почему обработка отсортированного массива * медленнее *, чем несортированный массив? (Java ArrayList.indexOf)

Ответ 1

Он выглядит как эффект кэширования/предварительной выборки.

Ключ в том, что вы сравниваете парные (объекты), а не удваиваете (примитивы). Когда вы выделяете объекты в одном потоке, они обычно выделяются последовательно в памяти. Поэтому, когда indexOf просматривает список, он проходит через последовательные адреса памяти. Это хорошо для эвристики предварительной выборки кэша ЦП.

Но после сортировки списка вам все равно придется делать одинаковое количество запросов к памяти в среднем, но на этот раз доступ к памяти будет в случайном порядке.

UPDATE

Вот эталонный показатель, чтобы доказать, что порядок распределенных объектов имеет значение.

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

Ответ 2

Я думаю, что мы видим эффект промахов в кэше памяти:

При создании несортированного списка

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()));
}

этот отсортированный список имеет ту же производительность, что и исходная (мое время).

Ответ 3

Как простой пример, подтверждающий ответ wero и ответ 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

приятно показывает, что тайминги - это точно противоположности другого: если случайные числа отсортированы, то отсортированная версия будет медленнее. Если последовательные номера перетасовываются, то перетасованная версия работает медленнее.