Имя структуры данных: массив/связанный список комбинации
Я придумал структуру данных, которая комбинирует некоторые преимущества связанных списков с некоторыми преимуществами массивов фиксированного размера. Это кажется очень очевидным для меня, и таким образом, я ожидал бы, что кто-то будет думать о нем и уже назовет его. Делает любой знает то, чем это называют:
Возьмите небольшой массив фиксированного размера. Если число элементов, Вы хотите вставить свой массив, больше, чем размер массива, добавьте новый массив и безотносительно указателей, которые Вы любите между старым и новым.
Таким образом Вы имеете:
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
———————————— ————————————
Править: Для ссылки этот алгоритм обеспечивает довольно плохое выполнение дополнения/удаления худшего случая и не намного лучший средний случай. Большим преимуществом для моего сценария является улучшенная производительность кэша для операций чтения.
Щедрость ре редактирования: ответ Antal S-Z был так завершен и хорошо исследован, что я хотел предоставить им щедрость для него. По-видимому Переполнение стека не позволяет мне принять ответ, как только я предложил щедрость, таким образом, я должен буду ожидать (по общему признанию, я злоупотребляю системой поощрения намерения несколько, хотя это от имени вознаграждения кого-то для превосходного ответа). Конечно, если кому-то действительно удается предоставить лучший ответ, больше питания им, и у них может несомненно быть щедрость вместо этого!
Имена ре редактирования: я не интересуюсь тем, что Вы назвали бы им, если Вы не назовете его что, потому что это - то, что полномочия на предмете назвали бы им. Если это - имя, Вы просто придумали, мне не интересно. То, что я хочу, является именем, которое я могу искать в учебниках и с Google. (Кроме того, вот подсказка: ответ Antal - то, что я искал. Если Ваш ответ не является "развернутым связанным списком" без очень серьезного основания, это просто неправильно.)
6 ответов
Это называется развернутым связанным списком . Похоже, есть несколько преимуществ: одно в скорости, другое в космосе. Во-первых, если количество элементов в каждом узле имеет соответствующий размер (, например, , самое большее, размер одной строки кэша), вы получите заметно лучшую производительность кэша за счет улучшенной локализации памяти. Во-вторых, поскольку у вас есть 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/dev/archive/2005/08/22/454887.aspx
- “Список пропуска », http://en.wikipedia.org/wiki/Skip_list
- Лекции со списком пропуска из моего класса алгоритмов.
Кодирование CDR (если вы достаточно взрослые, чтобы помнить Lisp-машины).
См. Также ropes , который является обобщением этой идеи списка / массива для строк.
Каковы преимущества этой структуры данных с точки зрения вставки и удаления? Например: Что если вы хотите добавить элемент между 3 и 4? Все равно придется делать сдвиг, это займет O(N). Как узнать правильное ведро для элементаAt?
Я согласен с jer, вы должны взглянуть на skip list. Он сочетает в себе преимущества Linked List и Arrays. Большинство операций выполняется за O(log N)
Вы можете назвать это LinkedArrays.
Также я хотел бы увидеть псевдокод для операции removeIndex.
Хотя я не знаю вашей задачи, я настоятельно рекомендую вам взглянуть на списки пропусков.
Что касается названия, я думаю, что список желаний, вероятно, будет наиболее подходящим