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

[Noofiz]

Вы делаете очень серьезное допущение. Для такой задачи можно использовать структуру список с пропусками(ConcurrentSkipListMap). Ну или если элементы не повторяются, то одну из реализаций SortedSet.

[kefirfromperm]

Допущение серьезное, однако, на ряде задач вполне допустимое. Далее, вы говорите о коллекциях, которые к java.util.List не имеют отношения. Причем здесь они? Я рассматриваю именно реализации java.util.List и задачи, которые для них свойственны.

[Noofiz]

Ваша структура по сути представляет два ArrayList`а, из теории алгоритмов:
O(n) * 2 = O(n)
Т.е. два ArrayList ничем не лучше чем один или десять.
Копайте:
ru.wikipedia.org/wiki/%D0%92%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C

ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2

[kefirfromperm]

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

[kefirfromperm]

Весьма интересно посмотреть на реализацию java.util.List на основе Skip List'ов. Не дадите ссылочку?

Под универсальностью я имел ввиду то, что DoubleArrayList на любых задачах будет не хуже, чем ArrayList или LinkedList с точностью до коэффициента. Пока что это мои эмпирические предположения, подтвержденные экспериментально. Более полный анализ, конечно-же, надо произвести.

[mou]

Мне кажетя, что если бы вы разобрались в вопросе и поняли главное отличие LL от AL, что при вставке или удалении не происходит копирования, то вы бы не стали решать несуществующую проблему.

[kefirfromperm]

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;
}
…
}

[j2k6]

А это к чему? Человек mou так и сказал — в AL копирование есть, в LL — нету.

[kefirfromperm]

Протупил.

[kefirfromperm]

Ну я отлично понимаю это отличие и что же это нам дает? LL проседает при доступе по индексу, AL при вставке в середину. Это и есть проблема и она существует.

[mou]

Вот смотрите, есть четыре операции: поиск, доступ к произвольному элементу, вставка и удаление. Поиск для 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 означает ассимптотически сверху, а не «операции происходят рядом». В ассимптотических оценках нету понятия «допущения». Ну либо реализуйте структуру так, что бы она не позволяла производить вставки не рядом.

[kefirfromperm]

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

[halyavin]

Встречал подобную реализацию в «базе данных». Только там использовалось не два списка, а один список с дыркой. На практике я переписываю алгоритмы с ArrayList чтобы избежать квадратичного времени работы вместо использования подобной структуры данных.

[kefirfromperm]

На практике оно понятно. Мест где имеется разница в использовании ArrayList и LinkedList совсем не много. А уж найти такое, где нужны были бы свойства и того и другого, так вообще не реально. Но я задался вопросом: «возможно ли создать структуру, которая будет одинаково хорошо справляться с различными типами задач? » Решение перед Вами.

Дырка тоже интересный вариант. Возможно он даже лучше.

[Falland]

А чем вам не угодил тот же UnrolledLinkedList, у него вставка в середину очень быстрая, я думаю и фильтрацию он осилит легко?

[kefirfromperm]

С фильтрацией и LinkedList справляется легко. UnrolledLinkedList, насколько я понимаю, имеет скорость поиска по индексу O(N).

[Falland]

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

[kefirfromperm]

Конечно можно. github.com/kefirfromperm/multi-array-list там все есть. Только сейчас, это жуткое нагромождение жуткого кода.

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