DoubleArrayList — универсальная реализация java.util.List

Не так давно я считал. что нет оправдания использованию java.util.LinkedList в качестве реализации java.util.List. Но что-то заставило меня его поискать. Давайте разберемся. Любой грамотный Java-специалист знает, что java.util.ArrayList нужно использовать тогда, когда нам нужен быстрый доступ по индексу, а java.util.LinkedList, если нам нужно вставлять или удалять элементы в середине списка. Не многие из них догадываются, что если мы будем вставлять или удалять элементы в середине списка методами remove(int index) и add(int index, E element), то на поиск нужного элемента будет затрачено время в среднем пропорциональное размеру списка O(N). Так когда же возникает выгода от использования java.util.LinkedList?

При использовании итераторов. Точнее когда вы удаляете или вставляете элементы через java.util.ListIterator. В конце-концов, в поисках оправдания я нашел вполне реальный пример кода, на котором java.util.LinkedList дает значительное преимущество перед java.util.ArrayList. Это простейший алгоритм фильтрации, который удаляет из списка все элементы, не удовлетворяющие заданному условию.

for (Iterator<E> i = list.iterator(); i.hasNext(); ) {
    E val = i.next();
    if (!condition(val)) {
        i.remove();
    }
}

Этот же код можно запросто переписать с использованием дополнительного списка и тогда алгоритм с java.util.ArrayList, как минимум, не будет иметь квадратичную зависимость от первоначального размера.

List<E> list1 = new ArrayList<E>();
for (Iterator<E> i = list.iterator(); i.hasNext(); ) {
    E val = i.next();
    if (condition(val)) {
        list1.add(val);
    }
}
list.clear();
list.addAll(list1);

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

Для этого нам понадобится допущение: «Операции вставки и удаления происходят рядом.» Конечно, мы можем представить ситуацию, в которой операции вставки и удаления будут происходить хаотично, но в этом случае нас не спасет ни java.util.ArrayList, ни java.util.LinkedList, с которыми мы сражаемся. Ведь чтобы добавить или удалить произвольный элемент java.util.ArrayList должен в общем случае сдвинуть в массиве количество элементов пропорциональное размеру O(N), а java.util.LinkedList должен его найти O(N).

Идея такова. Список хранится не в одном массиве, а в 2х. Причем, каждый массив может вместить его целиком.

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

Вы скажете: «Да, мы сдвинули меньше элементов, чем в случае с java.util.ArrayList, но оно всё равно пропорционально размеру списка.» Вы правы, но если вспомнить о нашем допущении, то каждый раз, кроме первого, мы будем двигать незначительное количество элементов.

То же самое происходит и при удалении. Разрыв смещается на то место, откуда был удален элемент.

Я быстренько написал реализацию этого списка. И прогнал тесты: заполнение, последовательное сканирование, сканирование по индексу, фильтрация, удаление всего списка с головы по одному элементу. Т.к. результаты сильно разнятся для разных списков, визуализировать их достаточно сложно. Поэтому просто покажу таблицы. Графики будут, но позже.

ArrayList

Как можно видеть из таблицы, java.util.ArrayList отлично справляется с заполнением и любым сканированием, а на операциях фильтрации и даже удаления списка с головы терпит сокрушительное поражение.

LinkedList

Слабым местом java.util.LinkedList является доступ по индексу, а вот операция фильтрации выполняется заметно быстрее.

DoubleArrayList

Ну и, наконец, моя реализаци org.kefirsf.list.DoubleArrayList не проседает ни на одном из тестов.

Давайте сравним с LinkedList на больших объемах.

Заполнение

Фильтрация

Удаление с головы

Из всех этих графиков видно, что на различных операциях DoubleArrayList работает за время сопоставимое с java.util.LinkedList. Пусть даже не всегда лучше. Главное, что не возникает квадратичной зависимости от размера массива, а все операции выполняются за O(N), а это значит, что единичные операции в среднем выполняются за O(1). Таким образом, цель достигнута.

Код org.kefirsf.list.DoubleArrayList доступен на GitHub: github.com/kefirfromperm/multi-array-list
Предостережение: не пытайтесь использовать его в промышленной разработке. org.kefirsf.list.DoubleArrayList ещё недостаточно хорошо покрыт тестами, его использование может приводить к утечкам памяти.

Автор: kefirfromperm

Источник