Структура данных, поддерживающая O (1) произвольный доступ и O (1) в худшем случае, добавляется?

Question

Я понимаю, что индексируемая коллекция с изменяемым размером, которая использует массив для хранения своих элементов (например, List<T> в .NET или ArrayList в Java), имеет амортизированное O (1) время вставки в конце Коллекция. Но всегда есть то, что одна надоедливая вставка в критические моменты, когда коллекция достигла своей емкости , только , и для следующей вставки требуется полная копия всех элементов во внутреннем массиве в новый. (предположительно в два раза больше).

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

Я подумал, что может иметь смысл гибридный подход, состоящий из связанного списка массивов, где каждый раз, когда текущий массив «head» достигает своей емкости, новый массив, вдвое больший, добавляется в связанный список. Тогда никакая копия не будет необходима, так как связанный список будет по-прежнему иметь исходный массив. По сути, это кажется аналогичным (для меня) подходу List<T> или ArrayList, за исключением того, что где бы вы раньше не несли расходы на копирование всех элементов внутреннего массива, здесь вы платите только за выделение новый массив плюс вставка одного узла.

Конечно, это усложнило бы другие функции, если бы они были желательны (например, вставка / удаление в / из середины коллекции); но, как я уже сказал в заголовке, я просто ищу коллекцию только для добавления (и повторяем).

Существуют ли какие-либо структуры данных, идеально подходящие для этой цели? Или вы можете думать о себе самостоятельно?

Answer 1

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

[1] [2] [3] [4]

Если вы хотите добавить новое число, скажем 5, вы начинаете с выделения массива, который в два раза больше:

[1] [2] [3] [4]
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]

Далее вы вставляете 5 в новый массив:

[1] [2] [3] [4]
[ ] [ ] [ ] [ ] [5] [ ] [ ] [ ]

Наконец, опустите 4 из старого массива в новый:

[1] [2] [3] [ ]
[ ] [ ] [ ] [4] [5] [ ] [ ] [ ]

С этого момента, каждый раз, когда вы делаете вставку, добавляете элемент в новый массив и вытягиваете еще один элемент из старого массива. Например, после добавления 6 мы получим

[1] [2] [ ] [ ]
[ ] [ ] [3] [4] [5] [6] [ ] [ ]

Вставив еще два значения, мы получим здесь:

[ ] [ ] [ ] [ ]
[1] [2] [3] [4] [5] [6] [7] [8]

Если нам теперь нужно добавить еще один элемент, мы отбрасываем пустой теперь старый массив и выделяем массив, вдвое больший, чем текущий массив (способный содержать 16 элементов):

[1] [2] [3] [4] [5] [6] [7] [8]
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]

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

Поиски все еще O (1), так как вы просто решаете, какой из двух массивов искать, а вставки в середине O (n) из-за тасования.

Если вам интересно, у меня есть Java-реализация этой структуры на моем личном сайте. Я не знаю, насколько вы ее найдете, но вы можете попробовать это из.

Надеюсь, это поможет!

РЕДАКТИРОВАТЬ : Если вы хотите потратить немного времени на чтение исследовательской работы и попытаться реализовать довольно сложную структуру данных, вы можете получить тот же результат (худший - case O (1) append) в O (& radic; n) пространстве (что, кстати, оптимально) с использованием идей, представленных в этой статье. Я никогда не удосужился реализовать это, но это безусловно, стоит прочитать, если память является супер дефицитным ресурсом. Интересно, что эта конструкция использовалась в качестве подпрограммы!

Answer 2

Когда мне нужен такой контейнер, я использую свою реализацию структуры, описанную в «Изменение размеров массивов в оптимальном времени и пространстве»

Answer 3

OK. То, что вы описали, это почти то же, что std :: deque в стандартной библиотеке C ++. Разница в том, что массив (обычно) используется для хранения указателей на подмассивы вместо использования связанного списка.

Answer 4

Одной из идей было бы создать список из нескольких элементов, например:

struct item
{
    int data[NUM_ITEMS];
    item *next;
}

В этом случае вставка займет O(1), а если вы достигли лимита, просто создайте новый блок и добавьте его в конец списка