ArrayList без накладных расходов на копирование?

Question

Кто-нибудь знает о реализации List, которая имеет постоянное время get (int index) (I.e. реализует RandomAccess), но не нужно копировать весь список, когда он растет, как ArrayList делает?

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

public class ChunkedList<T> implements List<T>, RandomAccess { 
    private LinkedList<ArrayList<T>> chunks; 
    public T get(int index) { 
    return findCorrectChunk(index).get(computeChunkIndex(index)); 
    } 
} 

Answer 1

Если бы существовала такая структура, все использовали бы ее вместо массивов.

Однако я считаю более близкую структуру, о которой мне рассказывали в университетской лекции. Он имеет постоянное время доступа и время добавления/удаления элемента в произвольную позицию в основном O (sqrt (N)), и только когда N пересекает квадрат целочисленного значения, он принимает O (N). Амортизированное время - O (sqrt (N)). Вот идея.

N элементов в этой структуре хранятся в непрерывном массиве, который разделен на квадраты sqrt (N) смежных элементов sqrt (N) (возможно, последний фрагмент содержит меньше элементов). Каждый кусок - это ring buffer, для которого позиция первого элемента хранится в отдельном массиве sqrt (N). Чтобы получить доступ к элементу, вы должны определить, в каком фрагменте он находится (принимает одно деление), и выполнить правильный сдвиг в кольцевом буфере (сумма и модуль). Это постоянное время для доступа.

Чтобы добавить элемент до i-го положения, определите кусок k, элемент будет в конечном итоге, а затем отметьте все последние элементы в каждом фрагменте в k .. sqrt(N)-1. Сдвиньте отмеченный элемент в предыдущем фрагменте в свободный слот в последнем фрагменте, который будет главой кольцевого буфера (доступ к дополнительному массиву для определения где именно). Затем в положение перемещенного элемента из предыдущего фрагмента перемещайте отмеченный элемент из пред-предыдущего фрагмента. Повторите это, и вы получите свободный слот в середине массива, чтобы разместить элемент, который вы собираетесь добавить.

Магия заключается в том, что вы должны только увеличивать значения в дополнительном массиве на единицу (принимает время O (sqrt (N)), что делает структуру последовательной для доступа снова. Магия sqrt (N) также находится здесь: вы должны работать с каждым из X кусков и по каждому из элементов N/X вспомогательного массива. min (X + N/X) достигается для X = sqrt (N).

Если нет места в последней порции, чтобы добавить еще один элемент (т.е. SQRT (N), используемые до сих пор слишком мал), переупакуйте массив с SQRT (N) увеличивается на единицу. Это занимает время O (N). Амортизированное время по-прежнему равно O (sqrt (N)) за элемент.

Поэтому добавление элемента в произвольное место массива принимает O (sqrt (N)). Удаление происходит в одно и то же время. Время доступа принимает O (1).

Это идея.Я не знаю, как это называется, и профессор не знал ни того, что сам изобрел его. Любые ссылки будут оценены. И OP мог его реализовать, но, я уверен, кто-то уже имеет.

Answer 2

Ну, на самом деле это не идеальное решение, но для этого вы можете использовать TreeMap. Ваш ChunkedList будет warapper вокруг этого. Ваши ключи в TreeMap будут иметь тип Integer или Long и будут содержать индексы списка. Время доступа и вставки будет o (log (n)) (не константа, но намного лучше, чем n). И внутренне TreeMap работает аналогично LinkedList, т. Е. Узлы просто связаны со ссылками.

EDIT: Что-то вроде этого:

public class ChunkedList<T> implements List<T>, RandomAccess { 

    private TreeMap<Integer, T> data = new TreeMap<Integer, T>(); 

    public T get(int index) { 
     return data.get(index); 
    } 

    public boolean add(T o) { 
     data.put(data.size() + 1, o); 
     return true; 
    } 

     // Other operations 

} 

Конечно, другие операции будут немного более сложным и займет больше времени, чем в ArrayList.

Answer 3

Вы можете, конечно, написать реализацию списка как массив массивов. Существует много вариантов точного алгоритма. Производительность теоретически постоянна (игнорируя эффекты кеша и т. Д.).

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

(кстати, в данном примере вопроса коде LinkedList неуместно, так как это почти всегда бывает.)

Answer 4

Вы смотрели только намекая максимальный размер конструктора ArrayList?

Answer 5

Посмотрите на списки случайного доступа. Вы можете получить O (1) вставку с обоих концов и O (log (n)) доступ к элементам.

В конце концов, какая-то структура дерева-иса должна дать наилучшее время поиска/вставки.

Answer 6

Это звучит как преждевременная оптимизация. Профилировали ли вы функцию add() и показали, что она медленная? Поскольку ArrayList удваивает размер базового массива каждый раз, когда у него заканчивается пространство, поэтому вам не нужно копировать список каждый раз, когда вы добавляете его.

Возможно, вы пытаетесь решить проблему, которая не существует.

Answer 7

Невозможно написать такую ​​структуру данных. Самое близкое, что вы можете получить, - это предварительный размер массива ArrayList до максимального размера, предполагая, что вы знаете max. Интересно, что такие алгоритмы, как Collections.sort(), будут выполнять хуже по адресу ChunkedList, если его обозначение RandomAccess.