Сравнение структур данных

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

Сравнения в этой статье организованы по абстрактному типу данных . Поскольку одна конкретная структура данных может использоваться для реализации многих абстрактных типов данных, некоторые структуры данных могут появляться в нескольких сравнениях (например, хэш-карта может использоваться для реализации ассоциативного массива или множества ).

Списки

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

• peek : доступ к элементу по указанному индексу.
• вставка : вставка нового элемента по заданному индексу. Когда индекс равен нулю, это называется добавление в начало ; когда индекс является последним индексом в списке, это называется добавление в конец .
• удалить : удалить элемент по указанному индексу.

Карты

Карты хранят коллекцию пар (ключ, значение), так что каждый возможный ключ появляется в коллекции не более одного раза. Они обычно поддерживают три операции: ^[3]

• Вставить : добавить новую пару (ключ, значение) в коллекцию, сопоставляя ключ с его новым значением. Любое существующее сопоставление перезаписывается. Аргументами этой операции являются ключ и значение.
• Remove : удалить пару (ключ, значение) из коллекции, отменив сопоставление заданного ключа с его значением. Аргументом этой операции является ключ.
• Поиск : найти значение (если есть), привязанное к данному ключу. Аргументом этой операции является ключ, а значение возвращается из операции.

Если не указано иное, все структуры данных в этой таблице требуют O( n ) пространства.

Целочисленные ключи

Некоторые структуры данных карт предлагают превосходную производительность в случае целочисленных ключей. В следующей таблице пусть m будет числом бит в ключах.

Приоритетные очереди

Приоритетная очередь — это абстрактный тип данных, похожий на обычную очередь или стек . Каждый элемент в приоритетной очереди имеет связанный с ним приоритет. В приоритетной очереди элементы с высоким приоритетом обслуживаются раньше элементов с низким приоритетом. Приоритетные очереди поддерживают следующие операции:

• вставка : добавление элемента в очередь с соответствующим приоритетом.
• find-max : возвращает элемент из очереди, имеющий наивысший приоритет.
• delete-max : удалить элемент из очереди, имеющий наивысший приоритет.

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

Кучи

(Макс) куча — это древовидная структура данных , которая удовлетворяет свойству кучи : для любого заданного узла C, если P является родительским узлом C, то ключ ( значение ) P больше или равен ключу C.

В дополнение к операциям абстрактной приоритетной очереди в следующей таблице приведена сложность двух дополнительных логических операций:

• Increase-key : обновление ключа.
• объединение : объединение двух куч для формирования новой допустимой кучи, содержащей все элементы обеих, с уничтожением исходных куч.

Вот временные сложности ^[5] различных структур данных кучи. Сокращение am. указывает на то, что данная сложность амортизирована, в противном случае это сложность наихудшего случая. Для значения " O ( f )" и " Θ ( f )" см . нотацию Big O. Имена операций предполагают максимальную кучу.

1. Амортизированное время.
2. make-heap — это операция построения кучи из последовательности из n неотсортированных элементов. Она может быть выполнена за время Θ ( n ), когда meld выполняется за время O (log  n ) (где обе сложности могут быть амортизированы). ^{[6] [7]} Другой алгоритм достигает Θ ( n ) для двоичных куч. ^[8]
3. Для постоянных куч (не поддерживающих Increase-key ) универсальное преобразование снижает стоимость meld до стоимости insert , в то время как новая стоимость delete-max является суммой старых стоимостей delete-max и meld . ^[11] Здесь это заставляет meld работать за Θ (1) время (амортизированное, если стоимость insert равна ), в то время как delete-max по-прежнему работает за O (log  n ). Применительно к перекошенным биномиальным кучам это дает очереди Бродала-Окасаки, постоянные кучи с оптимальной сложностью в худшем случае. ^[10]
4. Нижняя граница ^[14] верхняя граница ^[15] ${\displaystyle \Omega (\log \log n),}$ ${\displaystyle O(2^{2{\sqrt {\log \log n}}}).}$
5. Очереди Бродала и строгие кучи Фибоначчи достигают оптимальных сложностей в худшем случае для куч. Они были впервые описаны как императивные структуры данных. Очередь Бродала-Окасаки — это постоянная структура данных, достигающая того же оптимума, за исключением того, что Increase-key не поддерживается.

Примечания

1. Бродник, Андрей; Карлссон, Сванте; Седжвик, Роберт ; Манро, Дж.И.; Демейн, Э.Д. (1999), Изменяемые массивы в оптимальном времени и пространстве (технический отчет CS-99-09) (PDF) , Кафедра компьютерных наук, Университет Ватерлоо
2. Крис Окасаки (1995). «Чисто функциональные списки случайного доступа». Труды Седьмой международной конференции по языкам функционального программирования и архитектуре компьютеров : 86–95. doi :10.1145/224164.224187.
3. Мельхорн, Курт ; Сандерс, Питер (2008), «4 хэш-таблицы и ассоциативные массивы», Алгоритмы и структуры данных: базовый набор инструментов (PDF) , Springer, стр. 81–98, заархивировано (PDF) из оригинала 2014-08-02
4. Кормен и др. 2022, стр. 484.
5. Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л. (1990). Введение в алгоритмы (1-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03141-8.
6. Sleator, Daniel Dominic ; Tarjan, Robert Endre (февраль 1986 г.). «Саморегулирующиеся кучи». SIAM Journal on Computing . 15 (1): 52–69. CiteSeerX 10.1.1.93.6678 . doi :10.1137/0215004. ISSN  0097-5397. 
7. Tarjan, Robert (1983). "3.3. Левые кучи". Структуры данных и сетевые алгоритмы . стр. 38–42. doi :10.1137/1.9781611970265. ISBN 978-0-89871-187-5.
8. Хейворд, Райан; МакДиармид, Колин (1991). "Анализ среднего случая построения кучи путем повторной вставки" (PDF) . J. Algorithms . 12 : 126–153. CiteSeerX 10.1.1.353.7888 . doi :10.1016/0196-6774(91)90027-v. Архивировано из оригинала (PDF) 2016-02-05 . Получено 2016-01-28 . 
9. "Биномиальная куча | Brilliant Math & Science Wiki". brilliant.org . Получено 2019-09-30 .
10. Brodal, Gerth Stølting; Okasaki, Chris (ноябрь 1996 г.), «Оптимальные чисто функциональные очереди с приоритетами», Journal of Functional Programming , 6 (6): 839–857, doi : 10.1017/s095679680000201x
11. Окасаки, Крис (1998). "10.2. Структурная абстракция". Чисто функциональные структуры данных (1-е изд.). С. 158–162. ISBN 9780521631242.
12. Такаока, Тадао (1999), Теория 2–3 куч (PDF) , стр. 12
13. Яконо, Джон (2000), «Улучшенные верхние границы для парных куч», Труды 7-го Скандинавского семинара по теории алгоритмов (PDF) , Lecture Notes in Computer Science, т. 1851, Springer-Verlag, стр. 63–77, arXiv : 1110.4428 , CiteSeerX 10.1.1.748.7812 , doi : 10.1007/3-540-44985-X_5, ISBN  3-540-67690-2
14. Фредман, Майкл Лоуренс (июль 1999 г.). «Об эффективности парных куч и связанных с ними структур данных» (PDF) . Журнал Ассоциации вычислительной техники . 46 (4): 473–501. doi :10.1145/320211.320214.
15. Pettie, Seth (2005). Towards a Final Analysis of Pairing Heaps (PDF) . Труды FOCS '05 46-го ежегодного симпозиума IEEE по основам компьютерной науки. стр. 174–183. CiteSeerX 10.1.1.549.471 . doi :10.1109/SFCS.2005.75. ISBN  0-7695-2468-0.
16. Хёплер, Бернхард; Сен, Сиддхартха; Тарьян, Роберт Э. (ноябрь 2011 г.). «Кучи ранговых пар» (PDF) . СИАМ Дж. Компьютерные технологии . 40 (6): 1463–1485. дои : 10.1137/100785351.
17. Фредман, Майкл Лоуренс ; Тарьян, Роберт Э. (июль 1987 г.). «Кучи Фибоначчи и их использование в улучшенных алгоритмах сетевой оптимизации» (PDF) . Журнал Ассоциации вычислительной техники . 34 (3): 596–615. CiteSeerX 10.1.1.309.8927 . doi :10.1145/28869.28874. 
18. Бродал, Герт Столтинг ; Лагогианнис, Джордж; Тарьян, Роберт Э. (2012). Строгие кучи Фибоначчи (PDF) . Труды 44-го симпозиума по теории вычислений - STOC '12. стр. 1177–1184. CiteSeerX 10.1.1.233.1740 . doi :10.1145/2213977.2214082. ISBN  978-1-4503-1245-5.
19. Бродал, Герт С. (1996), «Эффективные очереди с приоритетами в наихудшем случае» (PDF) , Труды 7-го ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , стр. 52–58
20. Гудрич, Майкл Т .; Тамассиа, Роберто (2004). "7.3.6. Построение кучи снизу вверх". Структуры данных и алгоритмы в Java (3-е изд.). С. 338–341. ISBN 0-471-46983-1.

Ссылки

• Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (05 апреля 2022 г.). Введение в алгоритмы, четвертое издание. МТИ Пресс. ISBN 978-0-262-36750-9.