Имя структуры данных: массив комбинаций / связанный список

Question

Я придумал структуру данных, которая сочетает в себе некоторые преимущества связанных списков с некоторыми преимуществами массивов фиксированного размера. Это кажется мне очень очевидным, и поэтому я ожидаю, что кто-то подумал об этом и уже назвал его. Кто-нибудь знает, как это называется:

Возьмите небольшой массив фиксированного размера. Если количество элементов, которые вы хотите поместить в свой массив, больше, чем размер массива, добавьте новый массив и любые другие указатели между старым и новым.

Таким образом, у вас есть:

Static array
—————————————————————————
|1|2|3|4|5|6|7|8|9|a|b|c|
—————————————————————————

Linked list
————  ————  ————  ————  ————
|1|*->|2|*->|3|*->|4|*->|5|*->NULL
————  ————  ————  ————  ————

My thing:
————————————  ————————————
|1|2|3|4|5|*->|6|7|8|9|a|*->NULL
————————————  ————————————

Редактировать : Для справки, этот алгоритм обеспечивает довольно низкую производительность добавления / удаления в худшем случае и ненамного лучше среднего случая. Большим преимуществом для моего сценария является улучшенная производительность кэша для операций чтения.

Edit re bounty : Ответ Antal S-Z был настолько полным и хорошо изученным, что я хотел предоставить им вознаграждение за это. Очевидно, переполнение стека не позволяет мне принять ответ, как только я предложу вознаграждение, так что мне придется подождать (правда, я несколько злоупотребляю системой намерений, но это во имя вознаграждения кого-то за отличное вознаграждение). ответ). Конечно, если кто-то сможет дать лучший ответ, больше возможностей для него, и он, безусловно, может получить за это награду!

Редактировать имена : Меня не интересует, как бы вы бы назвали это, если только вы не назовете это так, потому что это так называют власти по этому вопросу. Если это имя, которое вы только что придумали, мне это не интересно. То, что я хочу, это имя, которое я могу найти в учебниках и с Google. (Также вот вам совет: ответ Антала - это то, что я искал. Если ваш ответ не является «развернутым связанным списком» без очень веской причины, это просто неправильно.)

Answer 1

Это называется развернутый связанный список . Кажется, есть несколько преимуществ, одно в скорости и одно в космосе. Во-первых, если количество элементов в каждом узле имеет соответствующий размер (, например, , не более размера одной строки кэша), вы получаете заметно лучшую производительность кэша благодаря улучшенному расположению памяти. Во-вторых, поскольку у вас есть O ( n / m ) ссылок, где n - количество элементов в развернутом связанном списке, а m - это количество элементов, которое вы можете хранить в любом узле, вы также можете сэкономить значительное количество места, что особенно заметно, если каждый элемент маленький. При построении развернутых связанных списков, очевидно, реализации будут пытаться вообще оставить место в узлах; когда вы пытаетесь вставить полный узел, вы перемещаете половину элементов наружу. Таким образом, максимум один узел будет заполнен менее чем наполовину. И согласно тому, что я могу найти (я сам не проводил никакого анализа), если вы вставляете вещи случайным образом, узлы, как правило, заполнены примерно на три четверти или даже полнее, если операции находятся в конце списка.

И, как говорят все остальные (включая Википедию), вы можете проверить пропустить списки . Списки пропусков - это отличная вероятностная структура данных, используемая для хранения упорядоченных данных с ожидаемым временем выполнения O (log n ) для вставки, удаления и поиска. Это реализовано «башней» связанных списков, каждый слой имеет меньше элементов, чем выше. Внизу есть обычный связанный список, содержащий все элементы. На каждом последующем слое меньше элементов с коэффициентом p (обычно 1/2 или 1/4). Способ, которым это построено, является следующим. Каждый раз, когда элемент добавляется в список, он вставляется в соответствующее место в нижней строке (здесь используется операция «найти», которая также может быть выполнена быстро). Затем с вероятностью p он вставляется в соответствующее место в связанном списке «над ним», создавая этот список, если это необходимо; если он был помещен в более высокий список, то он снова появится выше с вероятностью p . Чтобы запросить что-то в этой структуре данных, вы всегда проверяете верхнюю полосу и смотрите, сможете ли вы ее найти. Если элемент, который вы видите, слишком велик, вы переходите на следующую нижнюю полосу и начинаете искать снова. Это как бинарный поиск. Википедия объясняет это очень хорошо и с хорошими диаграммами. Конечно, использование памяти будет хуже, и у вас не будет улучшенной производительности кеша, но обычно она будет быстрее.

Ссылки

• «Развернутый связанный список», http://en.wikipedia.org/wiki/Unrolled_linked_list
• «Развернутые связанные списки», http://blogs.msdn.com/b/devdev/archive/2005/08/22/454887.aspx
• «Список пропусков», http://en.wikipedia.org/wiki/Skip_list
• Список пропущенных лекций из класса моих алгоритмов.

Answer 2

CDR-кодирование (если вы достаточно взрослый, чтобы помнить Lisp Machines).

Также см. ropes , который является обобщением этой идеи списка / массива для строк.

Answer 3

Пока я не знаю вашу задачу, я настоятельно рекомендую вам посмотреть списки пропусков.

Что касается имени, я думаю, что список корзины, вероятно, был бы наиболее уместным

Answer 4

Я бы назвал это списком ведра.

Answer 5

Каковы преимущества этой структуры данных с точки зрения вставки и удаления? Пример: Что если вы хотите добавить элемент между 3 и 4? все равно придется сделать смену, требуется O (N) Как вы узнаете правильное ведро для elementAt?

Я согласен с Джером, вы должны взглянуть на Пропустить список . Это приносит преимущества связанного списка и массивов. Большинство операций выполняются в O (log N)

Answer 6

Вы можете назвать это LinkedArrays.

Кроме того, я хотел бы видеть псевдокод для операции removeIndex.