Как стать автором
Обновить

Комментарии 19

Вы делаете очень серьезное допущение. Для такой задачи можно использовать структуру список с пропусками(ConcurrentSkipListMap). Ну или если элементы не повторяются, то одну из реализаций SortedSet.
Допущение серьезное, однако, на ряде задач вполне допустимое. Далее, вы говорите о коллекциях, которые к java.util.List не имеют отношения. Причем здесь они? Я рассматриваю именно реализации java.util.List и задачи, которые для них свойственны.
Ваша структура по сути представляет два 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
Хорошо, т.е. вы считаете, что в теории моя структура работает не быстрее чем ArrayList. Вас не смущает, что на практике она показывает гораздо лучший результат для некоторых типов задач?
НЛО прилетело и опубликовало эту надпись здесь
Весьма интересно посмотреть на реализацию java.util.List на основе Skip List'ов. Не дадите ссылочку?

Под универсальностью я имел ввиду то, что DoubleArrayList на любых задачах будет не хуже, чем ArrayList или LinkedList с точностью до коэффициента. Пока что это мои эмпирические предположения, подтвержденные экспериментально. Более полный анализ, конечно-же, надо произвести.
Мне кажетя, что если бы вы разобрались в вопросе и поняли главное отличие LL от AL, что при вставке или удалении не происходит копирования, то вы бы не стали решать несуществующую проблему.
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;
}

}
А это к чему? Человек mou так и сказал — в AL копирование есть, в LL — нету.
Протупил.
Ну я отлично понимаю это отличие и что же это нам дает? LL проседает при доступе по индексу, AL при вставке в середину. Это и есть проблема и она существует.
Вот смотрите, есть четыре операции: поиск, доступ к произвольному элементу, вставка и удаление. Поиск для 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 означает ассимптотически сверху, а не «операции происходят рядом». В ассимптотических оценках нету понятия «допущения». Ну либо реализуйте структуру так, что бы она не позволяла производить вставки не рядом.
«Для вставки и удаления из LL O(1)» — вон она Ваша ошибка. Для того чтобы элемент вставить или удалить в произвольном месте списка, это место еще надо найти. А на поиск нужно O(N). Единственный вариант когда LinkedList эффективней ArrayList — это когда он используется через итераторы. В этом случае мы можем сказать, что все операции вставки и удаления происходят рядом, ну или последовательно. В этом случае, перемещение разрыва в DoubleArrayList будет асимптотически не хуже, чем поиск элемента итератором LinkedList.
Встречал подобную реализацию в «базе данных». Только там использовалось не два списка, а один список с дыркой. На практике я переписываю алгоритмы с ArrayList чтобы избежать квадратичного времени работы вместо использования подобной структуры данных.
На практике оно понятно. Мест где имеется разница в использовании ArrayList и LinkedList совсем не много. А уж найти такое, где нужны были бы свойства и того и другого, так вообще не реально. Но я задался вопросом: «возможно ли создать структуру, которая будет одинаково хорошо справляться с различными типами задач? » Решение перед Вами.

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

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

Публикации

Истории