Почему индексный доступ быстрее, чем доступ по ссылке в Java?

Question

Я сравниваю производительность метода contains в ArrayList и LinkedList для последовательности цифр от 0 до 1000.

Для обоих списков я использую contains (400). Производительность ArrayList всегда в 3 раза выше, чем у LinkedList. Сравнение выполняется с использованием JMH.

ArrayList занял 329 642 наносекунды

LinkedList занял 945 881 наносекунду

Если оба списка имеют O (n) производительность метода contains, почему LinkedList в 3 раза хуже?

Класс сравнения:

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Warmup(iterations = 5)
public class Comparation {
    @State(Scope.Thread)
    public static class MyState {
        private List<Integer> arrayList = new ArrayList<>();
        private List<Integer> linkedList = new LinkedList<>();
        private int iterations = 1000;

        @Setup(Level.Trial)
        public void setUp() {
            for (int i = 0; i < iterations; i++) {
                arrayList.add(i);
                linkedList.add(i);
            }
        }
    }

    @Benchmark
    public boolean testLinkedListContains(MyState state) {
        return state.linkedList.contains(400);
    }
    @Benchmark
    public boolean testArrayListContains(MyState state) {
        return state.arrayList.contains(400);
    }
}

Результат:

Benchmark                           Mode  Cnt    Score    Error  Units
Comparation.testArrayListContains   avgt   20  329,642 ± 20,709  ns/op
Comparation.testLinkedListContains  avgt   20  945,881 ± 43,621  ns/op

Answer 1

Ваш вопрос: Если оба списка имеют O (n) производительность метода contains, почему LinkedList в 3 раза хуже?

Это не противоречит правилу сложности O (n), рассмотрите O (n ) как что-то, что описывает алгоритм с линейным временем. Вопреки тому, что вы думаете, это не означает, что все реализации этого алгоритма имеют одинаковую скорость. Это означает, что время, которое они занимают, является линейной функцией их входных данных, здесь ArrayList в три раза быстрее, но если вы увеличите количество элементов в List, вы увидите, что ArrayList все равно в три раза быстрее, а время для итерации обоих из них растет как линейная функция количества элементов в List. Итак, если вы скажете, что Arraylist требуется 2n для выполнения этой функции, а LinkedList требует 10000n для выполнения этой функции, вы можете сказать, что они оба работают за O (n).

Здесь вы точно пришли к такому выводу, что LikedList в три раза хуже, это означает, что они имеют одинаковую сложность O (n).

Но если, увеличивая количество входных данных, вы обнаружите, что он больше не в 3 раза хуже, а становится 5 раз хуже или в 30 раз хуже, и это число растет в зависимости от количества входных данных (которое равно n), они не имеют одинаковой сложности O (n).

Answer 2

В ArrayList данные поддерживаются массивом, элементы которого расположены в памяти непрерывно. Таким образом, очень быстро увеличить итератор -> Просто go до следующего адреса в памяти.

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

Answer 3

Очень просто: разные структуры данных имеют разные компромиссы в производительности.

https://dzone.com/articles/arraylist-vs-linkedlist-vs

LinkedList реализован как список с двойной связью. Его производительность при добавлении и удалении лучше, чем у Arraylist, но хуже при использовании методов get и set.

Другими словами, если вашей мотивацией было постоянно изменять список, LinkedList мог бы быть лучшим выбором. Но чтобы просто создать и просмотреть список, ArrayList «выиграет».

Чтобы продолжить:

По мере добавления элементов в список ArrayList, его размер увеличивается динамически. Доступ к его элементам можно получить напрямую с помощью методов get и set, поскольку ArrayList по сути является массивом. ...

Vector и ArrayList требуют места по мере добавления дополнительных элементов. Vector каждый раз удваивает размер своего массива, тогда как ArrayList каждый раз увеличивает свой размер на 50%. ...

LinkedList, однако, также реализует интерфейс Queue, который добавляет больше методов, чем ArrayList и Vector, например, offer (), peek (), poll (), et c. ...

Примечание: начальная емкость ArrayList по умолчанию довольно мала. Хорошая привычка - создавать ArrayList с более высокой начальной емкостью. Это поможет избежать затрат на изменение размера.

В этом случае массив работает быстрее ... но менее гибок.