language-agnostic - это - programming tree types




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

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

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

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

EDIT : попробуйте включить ссылки на страницы, описывающие структуры данных, более подробно. Кроме того, попробуйте добавить пару слов о том, почему структура данных остыла (как уже указывал Йонас Кёлькер ). Кроме того, попробуйте предоставить одну структуру данных для каждого ответа . Это позволит лучше структурировать данные на вершине, основываясь только на своих голосах.


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

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

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


Fenwick Tree. Это структура данных, чтобы содержать счетчик суммы всех элементов в векторе, между двумя данными субиндексами 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.


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



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


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


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

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

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

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


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

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


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


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

Вот несколько ссылок
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

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


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

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


Загруженные косо-биномиальные кучи Gerth Stølting Brodal и Chris Okasaki:

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

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

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

В Haskell существует multiple implementations .

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



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

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


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


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


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

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



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

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


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

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







computer-science