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

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

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

Списки

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

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

Сравнение структур данных списка
	Пик (индекс)	Изменить (вставить или удалить) в…			Лишнее пространство, средний
	Пик (индекс)	Начало	Конец	Середина	Лишнее пространство, средний
Связанный список	Θ( п )	Я(1)	Θ(1) — известный конечный элемент; Θ( n ), неизвестный конечный элемент	Θ( п ) ^[1]^[2]	Θ( п )
Множество	Я(1)	—	—	—	0
Динамический массив	Я(1)	Θ( п )	Θ(1) амортизировано	Θ( п )	Θ( п ) ^[3]
Сбалансированное дерево	Θ(логарифм n)	Θ(логарифм n)	Θ(логарифм n )	Θ(логарифм n )	Θ( п )
произвольного доступа Список	Θ(логарифм n) ^[4]	Я(1)	— ^[4]	— ^[4]	Θ( п )
Дерево хешированного массива	Я(1)	Θ( п )	Θ(1) амортизировано	Θ( п )	Θ(√ п )

Карты

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

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

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

Структура данных	Поиск, удаление		Вставка		Заказал
Структура данных	средний	худший случай	средний	худший случай	Заказал
Список ассоциаций	На )	На )	О(1)	О(1)	Нет
B-дерево ^[6]	О( вход )	О( вход )	О( вход )	О( вход )	Да
Хэш-таблица	О(1)	На )	О(1)	На )	Нет
Несбалансированное двоичное дерево поиска	О( вход )	На )	О( вход )	На )	Да

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

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

Структура данных	Поиск, удаление		Вставка		Космос
Структура данных	средний	худший случай	средний	худший случай	Космос
Дерево слияния	[ ? ]	O(log _m n )	[ ? ]	[ ? ]	На )
Дерево Ван Эмде Боаса	O(журнал журнал м )	O(журнал журнал м )	O(журнал журнал м )	O(журнал журнал м )	О( м )
X-быстрая попытка	О( п журнал м ) ^[а]	[ ? ]	O(журнал журнал м )	O(журнал журнал м )	О( п журнал м )
Y-быстрая попытка	O(журнал журнал м ) ^[а]	[ ? ]	O(журнал журнал м ) ^[а]	[ ? ]	На )

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

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

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

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

Кучи

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

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

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

Вот временные сложности ^[7] различных структур данных кучи. Аббревиатура ам. указывает, что данная сложность амортизируется, в противном случае это сложность наихудшего случая. Значение « O ( f )» и « Θ ( f )» см в обозначении Big O. . Имена операций предполагают максимальную кучу.

Операция	найти-макс	удалить-макс	клавиша увеличения	вставлять	сливаться	помойка ^[б]
Двоичный ^[7]	я (1)	Θ (логарифм n )	Θ (логарифм n )	Θ (логарифм n )	Θ ( н )	Θ ( н )
Перекос ^[8]	я (1)	О (log n ) утра.	О (log n ) утра.	О (log n ) утра.	О (log n ) утра.	Θ ( н ) утра.
Левый ^[9]	я (1)	Θ (логарифм n )	Θ (логарифм n )	Θ (логарифм n )	Θ (логарифм n )	Θ ( н )
Биномиальный ^[7]^[11]	я (1)	Θ (логарифм n )	Θ (логарифм n )	Θ (1) утра.	Θ (логарифм n ) ^[с]	Θ ( н )
Наклонный бином ^[12]	я (1)	Θ (логарифм n )	Θ (логарифм n )	я (1)	Θ (логарифм n ) ^[с]	Θ ( н )
2–3 кучи ^[14]	я (1)	О (log n ) утра.	я (1)	Θ (1) утра.	О ( войти ) ^[с]	Θ ( н )
Перекос снизу вверх ^[8]	я (1)	О (log n ) утра.	О (log n ) утра.	Θ (1) утра.	Θ (1) утра.	Θ ( н ) утра.
Сопряжение ^[15]	я (1)	О (log n ) утра.	о (log n ) утра. ^[д]	я (1)	я (1)	Θ ( н )
Сопряжение по рангам ^[18]	я (1)	О (log n ) утра.	Θ (1) утра.	я (1)	я (1)	Θ ( н )
Фибоначчи ^[7]^[19]	я (1)	О (log n ) утра.	Θ (1) утра.	я (1)	я (1)	Θ ( н )
Строгий Фибоначчи ^[20]^[и]	я (1)	Θ (логарифм n )	я (1)	я (1)	я (1)	Θ ( н )
Мостовая долина ^[21]^[и]	я (1)	Θ (логарифм n )	я (1)	я (1)	я (1)	Θ ( н ) ^[22]

^ Jump up to: ^а ^б ^с Амортизированное время.
^ make-heap — это операция построения кучи из последовательности из n неотсортированных элементов. Это можно сделать за время Θ ( n ), когда объединение выполняется за время O (log n ) (при этом обе сложности могут быть амортизированы). ^[8]^[9] Другой алгоритм достигает Θ ( n ) для двоичных куч. ^[10]
^ Jump up to: ^а ^б ^с Для постоянных куч (не поддерживающих увеличения-ключа ) общее преобразование снижает стоимость объединения до стоимости вставки , в то время как новая стоимость удаления-макс является суммой старых затрат удаления-макс и объединения . ^[13] Здесь он выполняет объединение за время Θ (1) (амортизируется, если стоимость вставки равна), в то время как delete-max все еще выполняется за O (log n ). Применительно к косым биномиальным кучам он дает очереди Бродала-Окасаки, постоянные кучи с оптимальной сложностью для наихудшего случая. ^[12]
^ Нижняя граница $\Omega (\log \log n),$ ^[16] верхняя граница $O(2^{2{\sqrt {\log \log n}}}).$ ^[17]
^ Jump up to: ^а ^б Очереди Бродала и строгие кучи Фибоначчи обеспечивают оптимальную сложность кучи в наихудшем случае. Впервые они были описаны как императивные структуры данных. Очередь Бродала-Окасаки представляет собой постоянную структуру данных, обеспечивающую тот же оптимум, за исключением того, что ключ увеличения не поддерживается.

Примечания

^ Основной доклад дня 1 — Бьерн Страуструп: Стиль C++11 на GoingNative 2012 на канале Channel9.msdn.com с 45-й минуты или с 44-й минуты.
^ Обработка чисел: почему вы никогда и НИКОГДА не должны снова использовать связанный список в своем коде на kjellkod.wordpress.com
^ Бродник, Андрей; Карлссон, Сванте; Седжвик, Роберт ; Манро, Дж.И.; Демейн, ED (1999), Массивы изменяемого размера в оптимальном времени и пространстве (технический отчет CS-99-09) (PDF) , факультет компьютерных наук, Университет Ватерлоо
^ Jump up to: ^а ^б ^с Крис Окасаки (1995). «Чисто функциональные списки произвольного доступа». Материалы седьмой международной конференции по языкам функционального программирования и компьютерной архитектуре : 86–95. дои : 10.1145/224164.224187 .
^ Мельхорн, Курт ; Сандерс, Питер (2008), «4 хэш-таблицы и ассоциативные массивы», Алгоритмы и структуры данных: базовый набор инструментов (PDF) , Springer, стр. 81–98, заархивировано (PDF) из оригинала 2 августа 2014 г.
^ Кормен и др. 2022 , с. 484
^ Jump up to: ^а ^б ^с ^д Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л. (1990). Введение в алгоритмы (1-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03141-8 .
^ Jump up to: ^а ^б ^с Слитор, Дэниел Доминик ; Тарьян, Роберт Эндре (февраль 1986 г.). «Саморегулирующиеся кучи» . SIAM Journal по вычислительной технике . 15 (1): 52–69. CiteSeerX 10.1.1.93.6678 . дои : 10.1137/0215004 . ISSN 0097-5397 .
^ Jump up to: ^а ^б Тарьян, Роберт (1983). «3.3. Левые кучи». Структуры данных и сетевые алгоритмы . стр. 38–42. дои : 10.1137/1.9781611970265 . ISBN 978-0-89871-187-5 .
^ Хейворд, Райан; МакДиармид, Колин (1991). «Анализ среднего случая построения кучи путем повторной вставки» (PDF) . Дж. Алгоритмы . 12 : 126–153. CiteSeerX 10.1.1.353.7888 . дои : 10.1016/0196-6774(91)90027-в . Архивировано из оригинала (PDF) 5 февраля 2016 г. Проверено 28 января 2016 г.
^ «Биномиальная куча | Блестящая вики по математике и естественным наукам» . блестящий.орг . Проверено 30 сентября 2019 г.
^ Jump up to: ^а ^б Бродал, Герт Столтинг; Окасаки, Крис (ноябрь 1996 г.), «Оптимальные чисто функциональные очереди приоритетов», Journal of Functional Programming , 6 (6): 839–857, doi : 10.1017/s095679680000201x
^ Окасаки, Крис (1998). «10.2. Структурная абстракция». Чисто функциональные структуры данных (1-е изд.). стр. 158–162. ISBN 9780521631242 .
^ Такаока, Тадао (1999), Теория 2–3 куч (PDF) , стр. 12
^ Яконо, Джон (2000), «Улучшенные верхние границы для спаривания куч», Proc. 7-й скандинавский семинар по теории алгоритмов (PDF) , Конспекты лекций по информатике, том. 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
^ Фредман, Майкл Лоуренс (июль 1999 г.). «Об эффективности объединения куч и связанных структур данных» (PDF) . Журнал Ассоциации вычислительной техники . 46 (4): 473–501. дои : 10.1145/320211.320214 .
^ Петти, Сет (2005). К окончательному анализу парных куч (PDF) . FOCS '05 Материалы 46-го ежегодного симпозиума IEEE по основам информатики. стр. 174–183. CiteSeerX 10.1.1.549.471 . дои : 10.1109/SFCS.2005.75 . ISBN 0-7695-2468-0 .
^ Хёплер, Бернхард; Сен, Сиддхартха; Тарьян, Роберт Э. (ноябрь 2011 г.). «Кучи ранговых пар» (PDF) . СИАМ Дж. Компьютерные технологии . 40 (6): 1463–1485. дои : 10.1137/100785351 .
^ Фредман, Майкл Лоуренс ; Тарьян, Роберт Э. (июль 1987 г.). «Кучи Фибоначчи и их использование в улучшенных алгоритмах оптимизации сети» (PDF) . Журнал Ассоциации вычислительной техники . 34 (3): 596–615. CiteSeerX 10.1.1.309.8927 . дои : 10.1145/28869.28874 .
^ Бродал, Герт Столтинг ; Лагояннис, Джордж; Тарьян, Роберт Э. (2012). Строгие кучи Фибоначчи (PDF) . Материалы 44-го симпозиума по теории вычислений - STOC '12. стр. 1177–1184. CiteSeerX 10.1.1.233.1740 . дои : 10.1145/2213977.2214082 . ISBN 978-1-4503-1245-5 .
^ Бродал, Герт С. (1996), «Эффективные приоритетные очереди для наихудшего случая» (PDF) , Proc. 7-й ежегодный симпозиум ACM-SIAM по дискретным алгоритмам , стр. 52–58.
^ Гудрич, Майкл Т .; Тамассия, Роберто (2004). «7.3.6. Построение кучи снизу вверх». Структуры данных и алгоритмы в Java (3-е изд.). стр. 338–341. ISBN 0-471-46983-1 .

Ссылки

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

[amortized-7] Jump up to: ^а ^б ^с Амортизированное время.

[12] make-heap — это операция построения кучи из последовательности из n неотсортированных элементов. Это можно сделать за время Θ ( n ), когда объединение выполняется за время O (log n ) (при этом обе сложности могут быть амортизированы). ^[8]^[9] Другой алгоритм достигает Θ ( n ) для двоичных куч. ^[10]

[bootstrap-meld-14] Jump up to: ^а ^б ^с Для постоянных куч (не поддерживающих увеличения-ключа ) общее преобразование снижает стоимость объединения до стоимости вставки , в то время как новая стоимость удаления-макс является суммой старых затрат удаления-макс и объединения . ^[13] Здесь он выполняет объединение за время Θ (1) (амортизируется, если стоимость вставки равна), в то время как delete-max все еще выполняется за O (log n ). Применительно к косым биномиальным кучам он дает очереди Бродала-Окасаки, постоянные кучи с оптимальной сложностью для наихудшего случая. ^[12]

[pairingdecreasekey-21] Нижняя граница $\Omega (\log \log n),$ ^[16] верхняя граница $O(2^{2{\sqrt {\log \log n}}}).$ ^[17]

[optimum-25] Jump up to: ^а ^б Очереди Бродала и строгие кучи Фибоначчи обеспечивают оптимальную сложность кучи в наихудшем случае. Впервые они были описаны как императивные структуры данных. Очередь Бродала-Окасаки представляет собой постоянную структуру данных, обеспечивающую тот же оптимум, за исключением того, что ключ увеличения не поддерживается.

[1] Основной доклад дня 1 — Бьерн Страуструп: Стиль C++11 на GoingNative 2012 на канале Channel9.msdn.com с 45-й минуты или с 44-й минуты.

[2] Обработка чисел: почему вы никогда и НИКОГДА не должны снова использовать связанный список в своем коде на kjellkod.wordpress.com

[3] Бродник, Андрей; Карлссон, Сванте; Седжвик, Роберт ; Манро, Дж.И.; Демейн, ED (1999), Массивы изменяемого размера в оптимальном времени и пространстве (технический отчет CS-99-09) (PDF) , факультет компьютерных наук, Университет Ватерлоо

[okasakiComparison-4] Jump up to: ^а ^б ^с Крис Окасаки (1995). «Чисто функциональные списки произвольного доступа». Материалы седьмой международной конференции по языкам функционального программирования и компьютерной архитектуре : 86–95. дои : 10.1145/224164.224187 .

[ms-5] Мельхорн, Курт ; Сандерс, Питер (2008), «4 хэш-таблицы и ассоциативные массивы», Алгоритмы и структуры данных: базовый набор инструментов (PDF) , Springer, стр. 81–98, заархивировано (PDF) из оригинала 2 августа 2014 г.

[FOOTNOTECormenLeisersonRivestStein2022484-6] Кормен и др. 2022 , с. 484

[CLRS-8] Jump up to: ^а ^б ^с ^д Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л. (1990). Введение в алгоритмы (1-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03141-8 .

[sleator-tarjan-skew-9] Jump up to: ^а ^б ^с Слитор, Дэниел Доминик ; Тарьян, Роберт Эндре (февраль 1986 г.). «Саморегулирующиеся кучи» . SIAM Journal по вычислительной технике . 15 (1): 52–69. CiteSeerX 10.1.1.93.6678 . дои : 10.1137/0215004 . ISSN 0097-5397 .

[tarjan-leftist-10] Jump up to: ^а ^б Тарьян, Роберт (1983). «3.3. Левые кучи». Структуры данных и сетевые алгоритмы . стр. 38–42. дои : 10.1137/1.9781611970265 . ISBN 978-0-89871-187-5 .

[hayward-mcdiarmid-heap-build-11] Хейворд, Райан; МакДиармид, Колин (1991). «Анализ среднего случая построения кучи путем повторной вставки» (PDF) . Дж. Алгоритмы . 12 : 126–153. CiteSeerX 10.1.1.353.7888 . дои : 10.1016/0196-6774(91)90027-в . Архивировано из оригинала (PDF) 5 февраля 2016 г. Проверено 28 января 2016 г.

[13] «Биномиальная куча | Блестящая вики по математике и естественным наукам» . блестящий.орг . Проверено 30 сентября 2019 г.

[brodal-okasaki-15] Jump up to: ^а ^б Бродал, Герт Столтинг; Окасаки, Крис (ноябрь 1996 г.), «Оптимальные чисто функциональные очереди приоритетов», Journal of Functional Programming , 6 (6): 839–857, doi : 10.1017/s095679680000201x

[16] Окасаки, Крис (1998). «10.2. Структурная абстракция». Чисто функциональные структуры данных (1-е изд.). стр. 158–162. ISBN 9780521631242 .

[17] Такаока, Тадао (1999), Теория 2–3 куч (PDF) , стр. 12

[Iacono-18] Яконо, Джон (2000), «Улучшенные верхние границы для спаривания куч», Proc. 7-й скандинавский семинар по теории алгоритмов (PDF) , Конспекты лекций по информатике, том. 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

[Fredman1999-19] Фредман, Майкл Лоуренс (июль 1999 г.). «Об эффективности объединения куч и связанных структур данных» (PDF) . Журнал Ассоциации вычислительной техники . 46 (4): 473–501. дои : 10.1145/320211.320214 .

[20] Петти, Сет (2005). К окончательному анализу парных куч (PDF) . FOCS '05 Материалы 46-го ежегодного симпозиума IEEE по основам информатики. стр. 174–183. CiteSeerX 10.1.1.549.471 . дои : 10.1109/SFCS.2005.75 . ISBN 0-7695-2468-0 .

[22] Хёплер, Бернхард; Сен, Сиддхартха; Тарьян, Роберт Э. (ноябрь 2011 г.). «Кучи ранговых пар» (PDF) . СИАМ Дж. Компьютерные технологии . 40 (6): 1463–1485. дои : 10.1137/100785351 .

[Fredman_And_Tarjan-23] Фредман, Майкл Лоуренс ; Тарьян, Роберт Э. (июль 1987 г.). «Кучи Фибоначчи и их использование в улучшенных алгоритмах оптимизации сети» (PDF) . Журнал Ассоциации вычислительной техники . 34 (3): 596–615. CiteSeerX 10.1.1.309.8927 . дои : 10.1145/28869.28874 .

[24] Бродал, Герт Столтинг ; Лагояннис, Джордж; Тарьян, Роберт Э. (2012). Строгие кучи Фибоначчи (PDF) . Материалы 44-го симпозиума по теории вычислений - STOC '12. стр. 1177–1184. CiteSeerX 10.1.1.233.1740 . дои : 10.1145/2213977.2214082 . ISBN 978-1-4503-1245-5 .

[26] Бродал, Герт С. (1996), «Эффективные приоритетные очереди для наихудшего случая» (PDF) , Proc. 7-й ежегодный симпозиум ACM-SIAM по дискретным алгоритмам , стр. 52–58.

[27] Гудрич, Майкл Т .; Тамассия, Роберто (2004). «7.3.6. Построение кучи снизу вверх». Структуры данных и алгоритмы в Java (3-е изд.). стр. 338–341. ISBN 0-471-46983-1 .

[1]

[2]

[3]

[4]

[5]

[6]

[а]

[7]

[б]

[8]

[9]

[11]

[с]

[12]

[14]

[15]

[д]

[18]

[19]

[20]

[и]

[21]

[22]

[10]

[13]

[16]

[17]