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

Как насчет косые деревья ?

кроме того, Chris Okasaki чисто функциональные структуры данных приходят на ум.

< zvrba> деревья Emde-удавов Фургона

я думаю, что было бы полезно знать , почему они прохладны. В целом вопрос, "почему" является самым важным для выяснения ;)

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

Попытки , также известный как деревья префикса или разрядные критикой деревья , существовали больше 40 лет, но все еще относительно неизвестны. Очень прохладное использование попыток описано в" МУСОР - динамический LC-trie и структура данных хеша ", который комбинирует trie с хеш-функцией.

Вот некоторые:

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

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

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

• заказанный "куче" деревья поиска: Вы храните набор (ключ, prio) пары в дереве, таком, что это - дерево поиска относительно ключей, и заказанный "куче" относительно приоритетов. Можно показать, что такое дерево имеет уникальную форму (и оно не всегда полностью упаковывало up-and-to-the-left). Со случайными приоритетами это дает Вам, ожидал O (зарегистрируйте n), время поиска, IIRC.

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

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

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

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

• Kd-деревья , пространственная используемая структура данных (среди других) в режиме реального времени Трассировка лучей, имеют оборотную сторону, что должны быть отсечены треугольники, что крест пересекает различные пробелы. Обычно BVH's быстрее, потому что они более легки.
• Деревья квадрантов MX-CIF , сохраните ограничительные рамки вместо наборов произвольной точки путем объединения регулярного дерева квадрантов с двоичным деревом на краях четверок.
• HAMT, иерархическая карта хеша с временами доступа, которые обычно превышают O (1) карты хеша из-за включенных констант.
• Инвертированный индекс , довольно известный в кругах поисковой системы, потому что это используется для быстрого извлечения документов, связанных с различными критериями поиска.

Большинство, если не все, их документируются на словаре NIST Алгоритмов и Структур данных

фильтр Цветка : Битовый массив м биты, первоначально весь набор к 0.

Для добавления объекта Вы выполняете его до К хеш-функции, которые дадут Вам К индексы в массиве, который Вы затем устанавливаете на 1.

, Чтобы проверить, находится ли объект в наборе, вычислите К индексы и проверка, если они все установлены на 1.

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

Удаление объекта невозможно, но можно реализовать фильтр цветка подсчета , представленный массивом ints и инкремента/декремента.

деревья Emde-удавов Фургона . У меня есть даже C++ реализация из него, поскольку до 2^20 целые числа.

Соединяющаяся "куча" является типом структуры данных "кучи" с относительно простой реализацией и превосходной практической амортизируемой производительностью.

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

Мне нравится treaps - за простую, все же эффективную идею наложить структуру "кучи" со случайным приоритетом над деревом двоичного поиска для балансировки его.

• Бинарная схема принятия решений (моя очень любимая структура данных, хорошая для представления булевых уравнений и решения их. Эффективный для большой партии вещей)
• "куча" (дерево, где родитель узла всегда поддерживает некоторое отношение к детям узла, например, родитель узла всегда больше, чем каждый из, его - дети (макс. "куча"))
• Приоритетные Очереди (действительно просто минимальная "куча" и макс. "куча", хорошая для того, чтобы поддержать порядок большого количества элементов там, например, объект с самым высоким значением, как предполагается, удален сначала)
• Хеш-таблицы, (со всеми видами стратегий поиска, и переполнение блока, обрабатывающее)
• Сбалансированные деревья двоичного поиска (Каждый из них, имеют их собственные преимущества)
  • RB-деревья (в целом хороший, при вставке, поиск, удалении и итерации заказанным способом)
  • Avl-деревья (быстрее для поиска, чем RB, но в других отношениях очень похожий на RB)
  • Косые деревья (быстрее для поиска, когда недавно используемые узлы, вероятно, будут снова использованы)
  • дерево Fusion (Использование быстрого умножения для получения еще лучших времен поиска)
  • B+Trees (Используемый для индексации в базах данных и файловых системах, очень эффективных, когда задержка к чтению-записи из/в индекс будет значительной).
• Пространственные индексы (Превосходный для запросов для того, являются ли точки/круги/прямоугольники/строки/кубы в непосредственной близости от или содержавший друг в друге)
  • дерево BSP
  • Дерево квадрантов
  • Дерево октантов
  • дерево Диапазона
  • Партии подобных но немного отличающихся деревьев и различные размеры
• деревья Интервала (хорошее открытие перекрывающиеся интервалы, линейные)
• Графики
  • список смежности (в основном список краев)
  • матрица смежности (таблица, представляющая ориентированные ребра графика с единственным битом на край. Очень быстро для обхода графика)

Они - те, я могу задуматься о. Существуют еще больше на Википедию приблизительно структуры данных

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

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

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

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

списки Пропуска круты.

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

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

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

кроме того, здесь апплет Java, демонстрирующий Списки Пропуска визуально.

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

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

Расширенные алгоритмы хеширования довольно интересны. Линейное хеширование аккуратно, потому что оно позволяет разделять один "блок" в Вашей хеш-таблице за один раз, вместо того, чтобы перехешировать всю таблицу. Это особенно полезно для распределенных кэшей. Однако с самыми простыми политиками разделения, Вы заканчиваете тем, что разделили все блоки в быстрой последовательности, и коэффициент загрузки таблицы колеблется довольно плохо.

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

Бинарная схема принятия решений является одной из моих любимых структур данных или на самом деле Уменьшенной заказанной бинарной схемой принятия решений (ROBDD).

Подобные структуры могут, например, использоваться для:

• наборы Представления объектов и выполнения очень быстрых логических операций на тех наборах.
• Любое булево выражение, с намерением найти все решения для Примечания выражения

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

деревья Huffman - используемый для сжатия.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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