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


size fill sequence index filtration remove first
20000 0 0 0 94 47
40000 0 0 0 406 187
60000 16 0 0 891 437
80000 0 0 0 1578 782
100000 0 15 0 2453 1219
120000 16 0 15 3516 1750
140000 16 0 0 4796 2391
160000 16 0 15 6219 3125
180000 16 0 15 7969 3984
200000 63 0 0 9859 4844

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

LinkedList


size fill sequence index filtration remove first
20000 0 0 406 0 0
40000 31 0 1985 0 0
60000 15 0 3828 16 0
80000 0 0 8359 0 0
100000 16 0 24891 0 15
120000 16 0 43562 16 0
140000 16 15 52985 0 15
160000 16 0 57047 15 0
180000 79 0 121531 0 15
200000 32 15 152250 16 16

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

DoubleArrayList


size fill sequence index filtration remove first
20000 0 0 0 0 0
40000 16 0 0 0 0
60000 0 0 0 15 0
80000 0 0 16 0 0
100000 16 0 0 15 0
120000 16 0 0 15 0
140000 16 16 0 15 0
160000 16 16 0 15 0
180000 47 16 0 15 0
200000 32 0 15 0 16

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

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


Заполнение


image

Фильтрация


image

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


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

Код org.kefirsf.list.DoubleArrayList доступен на GitHub: github.com/kefirfromperm/multi-array-list
Предостережение: не пытайтесь использовать его в промышленной разработке. org.kefirsf.list.DoubleArrayList ещё недостаточно хорошо покрыт тестами, его использование может приводить к утечкам памяти.
Ads
AdBlock has stolen the banner, but banners are not teeth — they will be back

More

Comments 19

    +3
    Вы делаете очень серьезное допущение. Для такой задачи можно использовать структуру список с пропусками(ConcurrentSkipListMap). Ну или если элементы не повторяются, то одну из реализаций SortedSet.
  • UFO just landed and posted this here
      +1
      Весьма интересно посмотреть на реализацию java.util.List на основе Skip List'ов. Не дадите ссылочку?

      Под универсальностью я имел ввиду то, что DoubleArrayList на любых задачах будет не хуже, чем ArrayList или LinkedList с точностью до коэффициента. Пока что это мои эмпирические предположения, подтвержденные экспериментально. Более полный анализ, конечно-же, надо произвести.
      –1
      Мне кажетя, что если бы вы разобрались в вопросе и поняли главное отличие LL от AL, что при вставке или удалении не происходит копирования, то вы бы не стали решать несуществующую проблему.
        –1
        public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
        {

        public void add(int index, E element) {
        if (index > size || index < 0)
        throw new IndexOutOfBoundsException(
        «Index: „+index+“, Size: „+size);

        ensureCapacity(size+1); // Increments modCount!!!
        System.arraycopy(elementData, index, elementData, index + 1,
        size — index);
        elementData[index] = element;
        size++;
        }

        public E remove(int index) {
        RangeCheck(index);

        modCount++;
        E oldValue = (E) elementData[index];

        int numMoved = size — index — 1;
        if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
        numMoved);
        elementData[--size] = null; // Let gc do its work

        return oldValue;
        }

        }
          0
          А это к чему? Человек mou так и сказал — в AL копирование есть, в LL — нету.
        0
        Ну я отлично понимаю это отличие и что же это нам дает? LL проседает при доступе по индексу, AL при вставке в середину. Это и есть проблема и она существует.
          0
          Вот смотрите, есть четыре операции: поиск, доступ к произвольному элементу, вставка и удаление. Поиск для LL всегда O(n), для AL O(n), для сортированного AL O(log n). Доступ к элементу для LL O(n/2) (если я ничего не путаю, то там есть оптимизация для обхода списка с хвоста), для AL O(1). Для вставки и удаления из LL O(1), для AL O(n).

          Бегло прочитав вашу реализацию – пришел к выводу, что вы используете 2N памяти и до трех копирований (тоесть вставка у вас O(3N)). Плюс факт наличия у вас двух массивов вынуждает вас синхронизировать работу с ними, что сделает применение данной структуры в многопоточной среде крайне дорогим.

          Но главная ошибка в том, что вы пренебрегаете асимптотикой. Ведь O означает ассимптотически сверху, а не «операции происходят рядом». В ассимптотических оценках нету понятия «допущения». Ну либо реализуйте структуру так, что бы она не позволяла производить вставки не рядом.
            +1
            «Для вставки и удаления из LL O(1)» — вон она Ваша ошибка. Для того чтобы элемент вставить или удалить в произвольном месте списка, это место еще надо найти. А на поиск нужно O(N). Единственный вариант когда LinkedList эффективней ArrayList — это когда он используется через итераторы. В этом случае мы можем сказать, что все операции вставки и удаления происходят рядом, ну или последовательно. В этом случае, перемещение разрыва в DoubleArrayList будет асимптотически не хуже, чем поиск элемента итератором LinkedList.
        0
        Встречал подобную реализацию в «базе данных». Только там использовалось не два списка, а один список с дыркой. На практике я переписываю алгоритмы с ArrayList чтобы избежать квадратичного времени работы вместо использования подобной структуры данных.
          0
          На практике оно понятно. Мест где имеется разница в использовании ArrayList и LinkedList совсем не много. А уж найти такое, где нужны были бы свойства и того и другого, так вообще не реально. Но я задался вопросом: «возможно ли создать структуру, которая будет одинаково хорошо справляться с различными типами задач? » Решение перед Вами.

          Дырка тоже интересный вариант. Возможно он даже лучше.
          0
          А чем вам не угодил тот же UnrolledLinkedList, у него вставка в середину очень быстрая, я думаю и фильтрацию он осилит легко?
            0
            С фильтрацией и LinkedList справляется легко. UnrolledLinkedList, насколько я понимаю, имеет скорость поиска по индексу O(N).
              0
              Да, поиск у UnrolledLinkedList, но амортизация порядка n/k (где k размер ячейки) всё меняет в лучшую для него сторону. Нельзя ли посмотреть исходники ваших тестов, чтобы можно было бы попробовать сравнить и этот вид листа.
                +1
                Конечно можно. github.com/kefirfromperm/multi-array-list там все есть. Только сейчас, это жуткое нагромождение жуткого кода.

                Думаю, реализовать, все таки, список на основе массива с дыркой, он должен быть эффективней и проще. А потом сравнить. Еще есть org.commons.collections.list.TreeList — хороший вариант, но, опять же, не без недостатков. По уму бы еще сравнивать расход памяти.

          Only users with full accounts can post comments. Log in, please.