Каковы менее известные, но полезные структуры данных?

795

Есть некоторые структуры данных, которые действительно полезны, но неизвестны большинству программистов. Какие они?

Все знают о связанных списках, бинарных деревьях и хешах, но как насчет Пропустить списки и фильтры Блума, например. Я хотел бы узнать больше о структурах данных, которые не так распространены, но которые стоит знать, потому что они опираются на великие идеи и обогащают инструментарий программиста.

PS: мне также интересны такие методы, как « Танцевальные ссылки», которые умно используют свойства общей структуры данных.

РЕДАКТИРОВАТЬ : Пожалуйста, попробуйте включить ссылки на страницы, описывающие структуры данных более подробно. Кроме того, попробуйте добавить пару слов о том, почему структура данных клевая (как уже указывал Йонас Кёлькер ). Кроме того, попробуйте предоставить одну структуру данных для каждого ответа . Это позволит лучшим структурам данных перемещаться к вершине на основе только их голосов.

language-agnostic data-structures computer-science f3lix
источник
16
en.wikipedia.org/wiki/List_of_data_structures + en.wikipedia.org/wiki/Binary_decision_diagram
Fanatic23

Ответы:

271

Попытки , также известные как префиксные деревья или критические биты , существуют уже более 40 лет, но все еще относительно неизвестны. Очень крутое использование попыток описано в « TRASH - динамическая структура данных дерева и хеш-памяти LC », в которой объединяется дерево с хэш-функцией.

David Phillips
источник
12
очень часто используется для проверки орфографии
Стивен А. Лоу
Пакетные попытки также являются интересным вариантом, когда вы используете только префикс строк в качестве узлов и в противном случае сохраняете списки строк в узлах.
Торстен Марек
Движок регулярных выражений в Perl 5.10 автоматически создает попытки.
Брэд Гилберт
По моему опыту, попытки мучительно дороги, учитывая, что указатель обычно длиннее символа, что является позором. Они подходят только для определенных наборов данных.
Джо
18
Поскольку ни один вопрос SO, независимо от темы, не обходится без упоминания jQuery ... Джон Резиг, создатель jQuery, имеет интересную серию структур данных, в которых он рассматривает различные реализации trie среди других: ejohn.org/blog/ Пересмотренный-javascript-словарь-поиск
Оскар Остегард
231

Фильтр Блума : битовый массив из m битов, изначально все установлены в 0.

Чтобы добавить элемент, вы запускаете его через k хеш-функций, которые дадут вам k индексов в массиве, который вы затем установите в 1.

Чтобы проверить, есть ли элемент в наборе, вычислите k индексов и проверьте, все ли они установлены в 1.

Конечно, это дает некоторую вероятность ложных срабатываний (согласно википедии это около 0,61 ^ (m / n), где n - количество вставленных элементов). Ложные негативы невозможны.

Удаление элемента невозможно, но вы можете реализовать фильтр подсчета Блума, представленный массивом целых чисел и увеличением / уменьшением.

albwq
источник
20
Вы забыли упомянуть их использование со словарями :) Вы можете сжать полный словарь в фильтр Блума примерно с 512 Кб, как хеш-таблицу без значений
Chris S
8
Google цитирует использование фильтров Блума в своей реализации BigTable.
Брайан Джанфоркаро
16
@FreshCode На самом деле это позволяет вам дешево проверить отсутствие элемента в наборе, поскольку вы можете получать ложные срабатывания, но никогда не ложные отрицания
Том Сэвидж
26
@FreshCode Как сказал @Tom Savage, это более полезно при проверке на негативы. Например, вы можете использовать его как быструю и маленькую (с точки зрения использования памяти) проверку орфографии. Добавьте все слова и попробуйте найти слова, которые вводит пользователь. Если вы получаете отрицательный, это означает, что это с ошибкой. Затем вы можете выполнить более дорогую проверку, чтобы найти самые близкие совпадения и предложить исправления.
Lacop
5
@ abhin4v: Фильтры Блума часто используются, когда большинство запросов могут вернуть ответ «нет» (например, здесь), что означает, что небольшое количество ответов «да» можно проверить с помощью более медленного точного теста. Это все еще приводит к значительному сокращению среднего времени ответа на запрос. Не знаю, делает ли это безопасный просмотр в Chrome, но это было бы мое предположение.
j_random_hacker
140

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

Патрик
источник
У меня были мысли о чем-то подобном для моих собственных нужд. Приятно знать, что это уже было реализовано где-то еще.
Кибби
15
В SGI STL (1998) есть реализация: sgi.com/tech/stl/Rope.html
quark
2
Не зная, как это называется, я недавно написал что-то очень похожее на Java - производительность была превосходной: code.google.com/p/mikeralib/source/browse/trunk/Mikera/src/…
mikera
Веревка довольно редкая: stackoverflow.com/questions/1863440/…
Уилл
6
Ссылка Микеры устарела, вот текущая .
aptwebapps
128

Пропускать списки довольно аккуратно.

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

Они могут использоваться в качестве альтернативы сбалансированным деревьям (используя пробалистическое балансирование, а не строгое соблюдение баланса). Их легко реализовать и быстрее, чем, скажем, красно-черное дерево. Я думаю, что они должны быть в каждом хорошем инструменте программистов.

Если вы хотите получить подробное представление о пропускаемых списках, то здесь есть ссылка на видео лекции MIT «Введение в алгоритмы».

Также здесь представлен Java-апплет, наглядно демонстрирующий Skip Lists.

оборота Симукаль
источник
+1 Qt использует пропущенные списки, а не RB-деревья для своих отсортированных карт и наборов. Да, они изящны (на императивных языках, во всяком случае).
Майкл Экстранд
2
Redis использует списки пропусков для реализации «Sorted Sets».
антирез
Пропуск списков, вероятно, моя любимая структура данных, которую нужно использовать, когда мне нужна хорошая структура данных, и у меня нет никаких гарантий относительно порядка данных, и я хочу более простую реализацию, чем другие «сбалансированные» структуры данных. Такая хорошая вещь.
Earino
Интересное примечание: если вы добавите достаточное количество уровней в свои списки пропусков, вы по сути получите B-дерево.
Рияд Калла
92

Пространственные индексы , в частности R-деревья и KD-деревья , эффективно хранят пространственные данные. Они хороши для координатных данных географической карты и алгоритмов определения местоположения и маршрута VLSI, а иногда и для поиска ближайших соседей.

Битовые массивы компактно хранят отдельные биты и позволяют выполнять быстрые битовые операции.

Юваль Ф
источник
6
Пространственные индексы также полезны для моделирования N-тел с участием дальнодействующих сил, таких как гравитация.
Джастин Пил
87

Молнии - производные структур данных, которые изменяют структуру, чтобы иметь естественное понятие «курсор» - текущее местоположение. Они действительно полезны, поскольку гарантируют, что индикаторы не могут быть вне границ - использованы, например, в оконном менеджере xmonad для отслеживания того, какое окно было сфокусировано.

Удивительно, но вы можете получить их, применяя методы из исчисления к типу исходной структуры данных!

Дон Стюарт
источник
2
это полезно только в функциональном программировании (в императивных языках вы просто сохраняете указатель или индекс). Кроме того, я до сих пор не понимаю, как на самом деле работают молнии.
Стефан Монов
4
@ Стефан в том, что вам не нужно хранить отдельный индекс или указатель сейчас.
Дон Стюарт
69

Вот несколько из них:

  • Суффикс пытается. Полезно для почти всех видов поиска строк (http://en.wikipedia.org/wiki/Suffix_trie#Functionality ). Смотрите также массивы суффиксов; они не такие быстрые, как суффиксные деревья, но намного меньше.

  • Splay деревья (как упомянуто выше). Причина, по которой они классные, тройная:

    • Они маленькие: вам нужны только левый и правый указатели, как в любом бинарном дереве (не нужно хранить информацию о цвете или размере узла)
    • Их (сравнительно) очень легко реализовать
    • Они предлагают оптимальную амортизированную сложность для целого ряда «критериев измерения» (время просмотра журнала - это то, что всем известно). Видетьhttp://en.wikipedia.org/wiki/Splay_tree#Performance_theorems

  • Упорядоченные кучи деревья поиска: вы храните в дереве несколько пар (key, prio), так что это дерево поиска по ключам и упорядочено по куче относительно приоритетов. Можно показать, что такое дерево имеет уникальную форму (и оно не всегда полностью упаковано слева направо). При случайных приоритетах он дает ожидаемое время поиска O (log n), IIRC.

  • Ниша - списки смежности для неориентированных плоских графов с O (1) соседними запросами. Это не столько структура данных, сколько особый способ организации существующей структуры данных. Вот как это делается: у каждого плоского графа есть узел со степенью не более 6. Выберите такой узел, поместите его соседей в список соседей, удалите его из графа и выполняйте рекурсию до тех пор, пока граф не станет пустым. Когда дана пара (u, v), ищите u в списке соседей v и v в списке соседей u. Оба имеют размер не более 6, так что это O (1).

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

Йонас Кёлкер
источник
Упорядоченное дерево поиска в куче называется treap. Один из трюков, которые вы можете сделать с этим, - изменить приоритет узла, чтобы перенести его в нижнюю часть дерева, где его легче удалить.
Лошадь
1
«Упорядоченное дерево поиска в куче называется трепом». - В определении, которое я слышал, IIRC, трэп - это упорядоченное дерево кучи со случайными приоритетами. Вы можете выбрать другие приоритеты, в зависимости от приложения ...
Jonas Kölker
2
Три- суффикс почти, но не совсем то же самое, что и гораздо более холодное суффиксное дерево , которое имеет строки, а не отдельные буквы по краям и может быть построено за линейное время (!). Кроме того, несмотря на то, что асимптотически медленнее, на практике суффиксные массивы часто намного быстрее, чем суффиксные деревья для многих задач, из-за их меньшего размера и меньшего числа косвенных указателей. Люблю O (1) поиск планарного графика Кстати!
j_random_hacker
@j_random_hacker: массивы суффиксов не асимптотически медленнее. Вот ~ 50 строк кода для построения массива линейных суффиксов: cs.helsinki.fi/u/tpkarkka/publications/icalp03.pdf
Эдвард КМЕТТ,
1
@ Эдвард Кметт: На самом деле я читал эту статью, это был прорыв в создании массива суффиксов . (Несмотря на то, что уже было известно , что линейное время строительства было возможно путем идти «через» суффиксом дерева, это было первое , несомненно , практический «прямой» алгоритм.) Но некоторые операции за пределами строительства все еще асимптотически медленнее в массиве суффиксов если какой - либо LCA стол также построен. Это также можно сделать в O (n), но при этом вы потеряете преимущества размера и локальности массива чистого суффикса.
j_random_hacker
65

Я думаю, что альтернативы стандартным структурам данных без блокировок, т. Е. Очередь без блокировки, стек и список, остаются без внимания.
Они становятся все более актуальными, поскольку параллелизм становится более высоким приоритетом и является гораздо более замечательной целью, чем использование мьютексов или блокировок для обработки одновременных операций чтения / записи.

Вот несколько ссылок
http://www.cl.cam.ac.uk/research/srg/netos/lock-free/
http://www.research.ibm.com/people/m/michael/podc-1996.pdf [Ссылки на PDF]
http://www.boyet.com/Articles/LockfreeStack.html

Блог Майка Актона (часто провокационный) содержит несколько отличных статей о дизайне и подходах без блокировок.

zebrabox
источник
Альтернативы без блокировок так важны в современном многоядерном, очень параллельном, зависимом от масштабируемости мире :-)
earino
Ну, в большинстве случаев разрушитель делает лучшую работу.
Deadalnix
55

Я думаю, что Disjoint Set довольно изящен для случаев, когда вам нужно разделить группу элементов на отдельные наборы и запросить членство. Хорошая реализация операций Union и Find приводит к амортизированным затратам, которые фактически постоянны (обратная функция Ackermnan, если я правильно помню класс структур данных).

Dana
источник
8
Это также называется «структурой данных для поиска объединения». Я был в восторге, когда впервые узнал об этой умной структуре данных в классе алгоритмов ...
BlueRaja - Дэнни Пфлугхофт
Расширения union-find-delete также позволяют удалять в постоянном времени.
Peaker
4
Я использовал Disjoint Set для своего генератора Dungeon, чтобы гарантировать, что все комнаты достижимы проходами :)
goldenratio
52

Кучи Фибоначчи

Они используются в некоторых из самых быстрых известных алгоритмов (асимптотически) для многих задач, связанных с графами, таких как проблема кратчайшего пути. Алгоритм Дейкстры выполняется за O (E log V) со стандартными двоичными кучами; использование куч Фибоначчи улучшает это до O (E + V log V), что является огромным ускорением для плотных графов. К сожалению, тем не менее, они имеют высокий постоянный коэффициент, что часто делает их непрактичными на практике.

Adam Rosenfield
источник
Высокий постоянный фактор, как вы сказали, и трудно реализовать хорошо, по словам друга, который должен был. С финансовой точки зрения это не круто, но все же, возможно, стоит знать.
p4bl0
Эти ребята сделали их конкурентоспособными по сравнению с другими типами кучи: cphstl.dk/Presentation/SEA2010/SEA-10.pdf Существует связанная структура данных, которая называется Pairing Heaps, которая проще в реализации и обеспечивает довольно хорошую практическую производительность. Однако теоретический анализ частично открыт.
Мануэль
Из моего опыта работы с кучами Фибоначчи я обнаружил, что дорогостоящая операция выделения памяти делает ее менее эффективной, чем простая двоичная куча, сопровождаемая массивом.
Чувак
44

Любой, кто имеет опыт работы с 3D-рендерингом, должен быть знаком с деревьями BSP . Как правило, это метод структурирования трехмерной сцены, который должен быть управляемым для рендеринга, зная координаты камеры и направление.

Разделение двоичного пространства (BSP) - это метод рекурсивного разделения пространства на выпуклые множества гиперплоскостями. Это подразделение приводит к представлению сцены посредством древовидной структуры данных, известной как дерево BSP.

Другими словами, это метод разбиения многоугольников сложной формы на выпуклые множества или более мелкие многоугольники, состоящие полностью из неотраженных углов (углов меньше 180 °). Для более общего описания разделения пространства см. Разделение пространства.

Первоначально этот подход был предложен в 3D компьютерной графике для повышения эффективности рендеринга. Некоторые другие приложения включают в себя выполнение геометрических операций с формами (конструктивная сплошная геометрия) в САПР, обнаружение столкновений в робототехнике и трехмерных компьютерных играх, а также другие компьютерные приложения, которые включают обработку сложных пространственных сцен.

spoulson
источник
... и связанные октреи и kd-деревья.
Lloeki
43

Деревья Хаффмана - используются для сжатия.

Люркер Действительно
источник
Хотя это интересно, не является ли это своего рода «введением в алгоритмы», это тема типа «пример жадного алгоритма»?
rshepherd
38

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

Согласно оригинальной статье :

Наши функциональные деревья в 2-3 пальца являются примером общей методики проектирования, введенной Окасаки (1998), называемой неявным рекурсивным замедлением . Мы уже отметили, что эти деревья являются расширением его неявной структуры deque, заменяя пары 2-3 узлами, чтобы обеспечить гибкость, необходимую для эффективной конкатенации и разбиения.

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

huitseeker
источник
Я рекомендую это отличное видео, объясняющее пальчиковые деревья в Clojure
FerD
Посмотрите на этот дубликат ответа , его стоит прочитать!
Франсуа Дж
34

Круговой или кольцевой буфер - используется для потоковой передачи, помимо прочего.

cdonner
источник
4
Также, отвратительно, каким-то образом удалось запатентовать (по крайней мере, при использовании для видео). ip.com/patent/USRE36801
Дэвид Эйсон
Основываясь на прочтении ссылки, я не думаю, что сама структура данных запатентована, но некоторые изобретения основаны на ней. Я согласен, что это определенно очень недостаточно используемая структура данных.
Гравитация
33

Я удивлен, что никто не упомянул деревья Меркле (то есть деревья хеша ).

Используется во многих случаях (программы P2P, цифровые подписи), когда вы хотите проверить хеш целого файла, когда вам доступна только часть файла.

BlueRaja - Дэнни Пфлугхофт
источник
32

<zvrba> деревья Ван Эмде-Боас

Думаю, было бы полезно узнать, почему они крутые. В общем, вопрос «почему» важнее всего задать;)

Мой ответ состоит в том, что они предоставляют вам O (log log n) словарей с ключами {1..n}, независимо от того, сколько ключей используется. Точно так же, как повторное деление пополам дает O (log n), повторное sqrting дает O (log log n), что происходит в дереве vEB.

Йонас Кёлкер
источник
Они хороши с теоретической точки зрения. На практике, однако, довольно сложно добиться от них конкурентных результатов. В известной мне статье они хорошо работают до 32-битных ключей ( citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.7403 ), но подход не будет масштабироваться до более чем 34-35 бит или так и нет реализации этого.
Мануэль
Еще одна причина, по которой они хороши, заключается в том, что они являются ключевым строительным блоком для ряда алгоритмов, не обращающих внимания на кэш.
Эдвард КМЕТТ
29

Интересный вариант хеш-таблицы называется Cuckoo Hashing . Он использует несколько хеш-функций вместо 1, чтобы иметь дело с хеш-коллизиями. Столкновения разрешаются путем удаления старого объекта из местоположения, указанного в основном хеше, и перемещения его в местоположение, указанное альтернативной хэш-функцией. Хэширование с кукушкой позволяет более эффективно использовать пространство памяти, поскольку вы можете увеличить коэффициент загрузки до 91% с помощью всего лишь 3 хэш-функций и при этом иметь хорошее время доступа.

А. Леви
источник
5
Проверьте хеширование классиков, как утверждается, быстрее.
Чмике
27

Мин-макс куча является вариацией кучи , которая реализует очередь раздвоенного приоритета. Это достигается простым изменением свойства кучи: дерево называется минимально-упорядоченным, если каждый элемент на четных (нечетных) уровнях меньше (больше), чем все дочерние элементы и внуки. Уровни нумеруются начиная с 1.

http://internet512.chonbuk.ac.kr/datastructure/heap/img/heap8.jpg

moinudin
источник
Сложно реализовать. Даже лучшие программисты могут ошибаться.
finnw
26

Мне нравятся структуры данных Cache Oblivious . Основная идея состоит в том, чтобы выстроить дерево в рекурсивно меньшие блоки, чтобы кэши разных размеров использовали преимущества блоков, которые в них удобно помещались. Это приводит к эффективному использованию кэширования во всем: от кэша L1 в ОЗУ до больших объемов данных, считываемых с диска, без необходимости знать специфику размеров любого из этих слоев кэширования.

btilly
источник
Интересная транскрипция по этой ссылке: «Ключом является макет Ван Эмде Боаса, названный в честь древовидной структуры данных Ван Эмде Боаса,
созданной
23

Слева склоняются красно-черные деревья . Значительно упрощенная реализация красно-черных деревьев Роберта Седжвика, опубликованная в 2008 году (~ половина строк кода для реализации). Если вам когда-либо приходилось сталкиваться с реализацией красно-черного дерева, прочитайте об этом варианте.

Очень похоже (если не идентично) на деревья Андерссона.

Лукас
источник
19

Герт Стёлтинг Бродал и Крис Окасаки загрузили косые биномиальные кучи :

Несмотря на их длинное имя, они обеспечивают асимптотически оптимальные операции с кучей даже в настройках функций.

  • O(1)размер, соединение , вставка, минимум
  • O(log n) deleteMin

Обратите внимание, что объединение занимает, O(1)а не O(log n)время, в отличие от более известных куч, которые обычно рассматриваются в учебниках по структуре данных, таких как левые кучи . И в отличие от кучи Фибоначчи , эти асимптотики являются наихудшими, а не амортизируются, даже если используются постоянно!

В Haskell есть несколько реализаций .

Они были совместно получены Бродалом и Окасаки после того, как Бродал придумал императивную кучу с такими же асимптотиками.

Эдвард КМЕТТ
источник
18
  • Kd-Trees , структура пространственных данных, используемая (среди прочего) в трассировке лучей в реальном времени, имеет недостаток, заключающийся в том, что треугольники, пересекающие разные пространства, должны быть обрезаны. Обычно BVH быстрее, потому что они более легкие.
  • В квадро-деревьях MX-CIF храните ограничивающие прямоугольники вместо произвольных наборов точек, комбинируя регулярное квадродерево с бинарным деревом по краям четырехугольников.
  • HAMT , иерархическая хеш-карта с временем доступа, которое обычно превышает O (1) хеш-карт из-за задействованных констант.
  • Инвертированный индекс , довольно известный в кругах поисковых систем, потому что он используется для быстрого поиска документов, связанных с различными поисковыми терминами.

Большинство из них, если не все, описаны в Словаре алгоритмов и структур данных NIST.

Jasper Bekkers
источник
18

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

Шариковое дерево - это структура данных, которая индексирует точки в метрическом пространстве. Вот статья о их создании. Они часто используются для нахождения ближайших соседей к точке или ускорения k-средних.

скоро
источник
Они также широко известны как «точки наблюдения» или vp-деревья. en.wikipedia.org/wiki/Vp-tree
Эдвард КМЕТТ
17

Не совсем структура данных; это еще один способ оптимизации динамически распределенных массивов, но буферы гэпов, используемые в Emacs, довольно крутые.

kerkeslager
источник
1
Я определенно считаю, что это структура данных.
Кристофер Барбер
Для всех, кто интересуется, именно так реализованы модели Document (например, PlainDocument), поддерживающие текстовые компоненты Swing; до 1.2 я считаю, что модели документов были прямыми массивами, что приводило к ужасной производительности вставки для больших документов; как только они переехали в Gap Buffers, с миром снова все было в порядке.
Рияд Калла
16

Дерево Фенвика. Это структура данных, позволяющая вести подсчет суммы всех элементов вектора между двумя заданными субиндексами i и j. Тривиальное решение, предварительно вычисляющее сумму, так как начало не позволяет обновить элемент (вы должны выполнить O (n) работу, чтобы не отставать).

Деревья Фенвика позволяют обновлять и запрашивать в O (log n), и как это работает, действительно круто и просто. Это действительно хорошо объяснено в оригинальной статье Фенвика, свободно доступной здесь:

http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol24/issue3/spe884.pdf

Его отец, дерево RQM, также очень круто: оно позволяет хранить информацию о минимальном элементе между двумя индексами вектора, и оно также работает в O (log n) update и query. Мне нравится преподавать сначала RQM, а затем Fenwick Tree.

eordano
источник
Боюсь, это дубликат . Возможно, вы хотели бы добавить к предыдущему ответу?
Франсуа G
Также связаны с деревьями сегментов, которые полезны для выполнения всех видов запросов диапазона.
dhruvbird
13

Вложенные множества удобны для представления деревьев в реляционных базах данных и выполнения запросов к ним. Например, ActiveRecord (ORM по умолчанию в Ruby on Rails) поставляется с очень простым плагином для вложенных множеств , который делает работу с деревьями тривиальной.

оборота эсад
источник
12

Это довольно специфично для предметной области, но структура данных с половинными краями довольно аккуратна. Он обеспечивает способ перебора многоугольников (граней и ребер), что очень полезно в компьютерной графике и вычислительной геометрии.

mpen
источник