Как-то на собеседовании мне задали вопрос: какая реализация списка выполнит вставку в середину быстрее: 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), при этом держим в уме, что создание объекта — «дорогая» операция.
Анализ исходного кода ситуацию не разъяснил, поэтому стал писать тесты. Я решил исследовать зависимость от двух параметров: начальный размер списка и количество вставок подряд (количество итераций).
Для каждого размера списка и количества итераций создаются по одному массиву ArrayList и LinkedList, они заполняются одинаковыми объектами, после чего под замер скорости производится n вставок одного объекта в середину. В качестве сравниваемой величины я использую десятичный логарифм от отношения времён выполнения ArrayList к LinkedList. Когда это значение меньше нуля, ArrayList справляется быстрее, когда больше — быстрее LinkedList.
Привожу результаты теста в таблице:
И в графике:
На оси X указан изначальный размер списка, линии представляют разные количества итераций, а на оси Y отношение скорости работы двух реализаций списка.
Так как с каждой итерацией размер списка увеличивается, можно сделать общий вывод: LinkList работает быстрее при небольшом размере списка. Но самое главное: без чёткой конкретизации условий сравнивать скорость работы этих двух алгоритмов нельзя!
Чтобы увеличить точность, я отказался от параметра количества вставок и уменьшил шаг размера до одного. Для каждого из размеров я провёл тест тысячу раз и взял среднее значение. Получил график:
На графике ярко выражены всплески. Они находятся точно на тех местах, где ArrayList производит увеличение массива. Следовательно, можно сказать, что пренебрегать этой операцией нельзя, как я посчитал в начале, анализируя исходный код.
Общий вывод можно сделать такой: операция вставки в середину происходит в основном быстрее в ArrayList, но не всегда. С теоретической точки зрения нельзя однозначно сравнить скорость этих двух алгоритмов без учёта изначального размера списка.
Спасибо за внимание, надеюсь, кому-то моя работа покажется интересной и/или полезной.
Когда я пришёл домой, я задумался над этим вопросом. Поискал решение этой задачи на форумах. Кто-то был согласен со мной, но многие учли, что операция смещения производится 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<String> arrayList;
LinkedList<String> 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<String> list, int size) {
for (int i = 0; i < size; i++) {
list.add("0");
}
}
static double calculateRatio(ArrayList<String> arrayList, LinkedList<String> 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<String> 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<String> 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.
Привожу результаты теста в таблице:
| Итераций | |||||||||||
| Размер | 1 | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512 | |
| 1 | -0,12 | 0,01 | -0,04 | 0,01 | 0,03 | -0,04 | -0,09 | -0,19 | -0,21 | -0,31 | |
| 5 | -0,14 | 0,02 | -0,02 | 0,07 | -0,08 | 0 | -0,15 | -0,31 | -0,42 | -0,52 | |
| 25 | -0,12 | 0,2 | 0,19 | 0,13 | 0,07 | 0,04 | -0,1 | -0,29 | -0,47 | -0,56 | |
| 125 | -0,31 | -0,01 | 0,01 | 0 | -0,03 | -0,11 | -0,17 | -0,35 | -0,48 | -0,57 | |
| 625 | -0,47 | -0,49 | -0,48 | -0,45 | -0,49 | -0,51 | -0,53 | -0,6 | -0,67 | -0,78 |
И в графике:
На оси X указан изначальный размер списка, линии представляют разные количества итераций, а на оси Y отношение скорости работы двух реализаций списка.
Так как с каждой итерацией размер списка увеличивается, можно сделать общий вывод: LinkList работает быстрее при небольшом размере списка. Но самое главное: без чёткой конкретизации условий сравнивать скорость работы этих двух алгоритмов нельзя!
Чтобы увеличить точность, я отказался от параметра количества вставок и уменьшил шаг размера до одного. Для каждого из размеров я провёл тест тысячу раз и взял среднее значение. Получил график:
На графике ярко выражены всплески. Они находятся точно на тех местах, где ArrayList производит увеличение массива. Следовательно, можно сказать, что пренебрегать этой операцией нельзя, как я посчитал в начале, анализируя исходный код.
Общий вывод можно сделать такой: операция вставки в середину происходит в основном быстрее в ArrayList, но не всегда. С теоретической точки зрения нельзя однозначно сравнить скорость этих двух алгоритмов без учёта изначального размера списка.
Спасибо за внимание, надеюсь, кому-то моя работа покажется интересной и/или полезной.
