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

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

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

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

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
————————————  ————————————

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

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

Изменить имена имен. Меня не интересует то, что вы бы назвали, если вы не назовете это, потому что то, что власти по этому вопросу назовут. Если это имя вы только что придумали, мне это неинтересно. Я хочу это имя, которое я могу найти в учебниках и в Google. (Кроме того, здесь совет: Antal ответ - это то, что я искал. Если ваш ответ не "разворачивается связанный список" без серьезной причины, это просто неправильно.)

Ответы

Ответ 1

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

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

Ссылки

Ответ 2

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

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

Ответ 3

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

Ответ 4

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

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

Ответ 5

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

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

Ответ 6

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

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