Вставка в середину: ArrayList против LinkedList18.07.2015 11:34

Как-то на собеседовании мне задали вопрос: какая реализация списка выполнит вставку в середину быстрее: ArrayList или LinkedList? С первого взгляда вопрос простой — нужно посчитать алгоритмическую сложность каждого варианта и сравнить их. Вставку в середину можно разделить на две операции: поиск середины списка и саму вставку. Для ArrayList поиск элемента по индексу не составляет труда, так как элементы списка находятся в массиве. Алгоритмическая сложность составляет O (1). В случае LinkedList придётся последовательно перебрать все элементы, пока не доберёмся до нужного элемента. Сложность будет O (n). Вставка в ArrayList связана со сдвигом всех элементов, находящихся после точки вставки, поэтому алгоритмическая сложность этой операции O (n). В LinkedList вставка заключается в создании нового связующего объекта и установки ссылок на него у соседних элементов. Сложность O (1). В сумме сложность вставки в середину у ArrayList и у LinkedList получается одинаковая — O (n). Эти рассуждения я показал интервьюеру, на что он мне задал вопрос: «Так что всё-таки быстрее: пробежаться по элементам или сместить элементы?». Я быстро прикинув, что операция чтения по сути быстрее операции записи, сказал, что LinkedList справится быстрее.
Когда я пришёл домой, я задумался над этим вопросом. Поискал решение этой задачи на форумах. Кто-то был согласен со мной, но многие учли, что операция смещения производится native методом, который работает быстрее, поэтому ArrayList выполнит вставку в середину быстрее. Не получив окончательного и неопровержимого ответа, я решил провести собственное исследование.

Сперва я углубился в изучение исходного кода этих классов. Вставка элемента в ArrayList проходит так: сначала, при необходимости, массив увеличивается, затем все элементы, стоящие после места вставки сдвигаются на число позиций, равное количеству вставляемых элементов (я рассматриваю один элемент), и в конце встаёт на свое место вставляемый элемент. Массив увеличивается со скоростью n*1,5, где n — размер массива, а минимальное увеличение при стандартных условиях (capacity=10) — 5 элементов. В связи с этим, операцией по увеличению массива при расчёте алгоритмической сложности вставки можно пренебречь. Сдвиг элементов, находящихся после точки вставки обладает алгоритмической сложностью O (n). Таким образом общая сложность всё равно остаётся O (n). Да, мы держим в уме, что операция увеличения массива незначительно повышает сложность, но нативность действий с массивом увеличивает скорость работы.

Поиск элемента в LinkedList начинается в цикле от края списка. Если искомый элемент находится в первой половине списка, то поиск идёт с начала, в обратном случае — с конца. Так как мы вставляем именно в середину, то в цикле пройдём ровно половину элементов. Сложность O (n). Сама вставка, как я уже писал выше, заключается в создании объекта и указании ссылок на него. Сложность O (1). Опять же ничего нового я не выяснил: общая сложность осталась O (n), при этом держим в уме, что создание объекта — «дорогая» операция.

Анализ исходного кода ситуацию не разъяснил, поэтому стал писать тесты. Я решил исследовать зависимость от двух параметров: начальный размер списка и количество вставок подряд (количество итераций).

package com.jonasasx.liststest;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Main {

        private static final int        MAX_SIZE                = 1000;
        private static final int        MAX_ITERATIONS  = 10000;
        private static final float      STEP_SIZE               = 2f;
        private static final float      STEP_ITERATIONS = 5;
        private static final int        TESTS_COUNT             = 100;

        public static void main(String[] args) throws InterruptedException {
                ArrayList arrayList;
                LinkedList linkedList;
                for (float size = 1; size < MAX_SIZE; size *= STEP_SIZE) {
                        for (float iterations = 1; iterations < MAX_ITERATIONS; iterations *= STEP_ITERATIONS) {
                                double sum = 0;
                                for (int k = 0; k < TESTS_COUNT; k++) {
                                        arrayList = new ArrayList<>();
                                        linkedList = new LinkedList<>();
                                        fillList(arrayList, (int) size);
                                        fillList(linkedList, (int) size);
                                        sum += Math.log10(calculateRatio(arrayList, linkedList, (int) iterations));
                                }
                                double logRatio = sum / TESTS_COUNT;
                                System.out.println(String.format("%07d\t%07d\t%07.2f\t%s", (int) size, (int) iterations, logRatio, logRatio > 0 ? "Linked" : "Array"));
                        }
                        System.out.println();
                }
        }

        static void fillList(List list, int size) {
                for (int i = 0; i < size; i++) {
                        list.add("0");
                }
        }

        static double calculateRatio(ArrayList arrayList, LinkedList linkedList, int iterations) {
                long l1 = calculateAL(arrayList, iterations);
                long l2 = calculateLL(linkedList, iterations);
                if (l1 == 0 || l2 == 0)
                        throw new java.lang.IllegalStateException();
                return (double) l1 / (double) l2;
        }

        static long calculateAL(ArrayList list, int m) {
                long t = System.nanoTime();
                for (int i = 0; i < m; i++) {
                        list.add(list.size() / 2, "0");
                }
                return System.nanoTime() - t;
        }

        static long calculateLL(LinkedList list, int m) {
                long t = System.nanoTime();
                for (int i = 0; i < m; i++) {
                        list.add(list.size() / 2, "0");
                }
                return System.nanoTime() - t;
        }
}

Для каждого размера списка и количества итераций создаются по одному массиву ArrayList и LinkedList, они заполняются одинаковыми объектами, после чего под замер скорости производится n вставок одного объекта в середину. В качестве сравниваемой величины я использую десятичный логарифм от отношения времён выполнения ArrayList к LinkedList. Когда это значение меньше нуля, ArrayList справляется быстрее, когда больше — быстрее LinkedList.

Привожу результаты теста в таблице:

И в графике:

На оси X указан изначальный размер списка, линии представляют разные количества итераций, а на оси Y отношение скорости работы двух реализаций списка.

Так как с каждой итерацией размер списка увеличивается, можно сделать общий вывод: LinkList работает быстрее при небольшом размере списка. Но самое главное: без чёткой конкретизации условий сравнивать скорость работы этих двух алгоритмов нельзя!

Чтобы увеличить точность, я отказался от параметра количества вставок и уменьшил шаг размера до одного. Для каждого из размеров я провёл тест тысячу раз и взял среднее значение. Получил график:

На графике ярко выражены всплески. Они находятся точно на тех местах, где ArrayList производит увеличение массива. Следовательно, можно сказать, что пренебрегать этой операцией нельзя, как я посчитал в начале, анализируя исходный код.

Общий вывод можно сделать такой: операция вставки в середину происходит в основном быстрее в ArrayList, но не всегда. С теоретической точки зрения нельзя однозначно сравнить скорость этих двух алгоритмов без учёта изначального размера списка.

Спасибо за внимание, надеюсь, кому-то моя работа покажется интересной и/или полезной.

© Habrahabr.ru