Есть некоторые структуры данных вокруг, которые действительно полезны, но неизвестны большинству программистов. Какие из них?
Все знают о связанных списках, бинарных деревьях и хэшах, но как насчет Пропустить списки и Bloom filters. Я хотел бы знать больше структур данных, которые не так распространены, но их стоит знать, потому что они полагаются на отличные идеи и обогащают программный ящик программы.
PS: Меня также интересуют такие методы, как Dancing links, которые умело используют свойства общей структуры данных.
ИЗМЕНИТЬ: Попробуйте включить ссылки на страницы, описывающие структуры данных, более подробно. Кроме того, попробуйте добавить пару слов о том, почему структура данных крутая (как уже отмечал Jonas Kölker). Кроме того, постарайтесь предоставить одну структуру данных за каждый ответ. Это позволит лучше структурировать данные на вершине, основываясь только на своих голосах.
Прогоняет, также известный как префикс-деревья или crit- битовые деревья, существуют уже более 40 лет, но все еще относительно неизвестны. Очень крутое использование попыток описано в "TRASH - динамическая структура LC-trie и хэш-данных ", которая объединяет trie с хешем функция.
Bloom filter: бит-массив из m бит, изначально все установлены на 0.
Чтобы добавить элемент, вы запускаете его через k хеш-функции, которые дадут вам k-индексы в массиве, которые вы затем установили в 1.
Чтобы проверить, находится ли элемент в наборе, вычислите индексы k и проверьте, все ли они установлены на 1.
Конечно, это дает некоторую вероятность ложноположительных (согласно wikipedia его около 0,61 ^ (m/n), где n - количество вставленных элементов). Ложные негативы невозможны.
Удаление элемента невозможно, но вы можете реализовать фильтр цветения подсчета, представленный массивом int и increment/decment.
Rope: строка, которая позволяет использовать дешевые прединдеры, подстроки, средние вставки и добавления. У меня на самом деле было только одно применение, но никакой другой структуры не хватило бы. Регулярные строки и массивы добавок были слишком дорогими для того, что нам нужно было делать, и отменить все, о чем не могло быть и речи.
Пропустить списки довольно аккуратно.
Wikipedia
Список пропусков - это вероятностная структура данных, основанная на нескольких параллельных, отсортированных связанных списках, с эффективностью, сравнимой с деревом двоичного поиска (журнал заказов n среднее время для большинства операций).
Они могут использоваться в качестве альтернативы сбалансированным деревьям (используя вероятностную балансировку, а не строгое соблюдение балансировки). Их легко реализовать и быстрее, чем сказать, красно-черное дерево. Я думаю, что они должны быть в каждом хорошем программисте.
Если вы хотите получить углубленное введение в списки пропуска, здесь ссылка на видео в MIT Введение в лекции алгоритмов на них.
Кроме того, здесь - это апплет Java, демонстрирующий списки пропусков визуально.
Пространственные индексы, в частности R-деревья и KD-tree, эффективно хранить пространственные данные. Они хороши для данных координаты географических карт и мест размещения и маршрутизации VLSI, а иногда и для поиска ближайших соседей.
Бит-массивы сохраняют отдельные биты компактно и позволяют выполнять быстрые бит.
Молнии - производные структур данных, которые изменяют структуру, чтобы иметь естественное понятие "курсор" - - Текущее местоположение. Они действительно полезны, поскольку они гарантируют, что индикаторы не могут быть не связаны, например, в диспетчер окон xmonad, чтобы отслеживать, какое окно сфокусировано.
Удивительно, вы можете получить их применение методов из исчисления к типу исходной структуры данных!
Вот несколько:
Суффикс пытается. Полезно для почти всех видов поиска строк ( http://en.wikipedia.org/wiki/Suffix_trie#Functionality). См. Также массивы суффиксов; они не такие быстрые, как суффиксные деревья, но намного меньше.
Разделите деревья (как упоминалось выше). Причина, по которой они круты, трижды:
Куча упорядоченных деревьев поиска: вы храните кучу пар (key, prio) в дереве, так что это дерево поиска по отношению к ключам и упорядочено по кустам относительно приоритетов. Можно показать, что такое дерево имеет уникальную форму (и оно не всегда полностью упаковано вверх-и-на -лево). При случайных приоритетах он дает ожидаемое время поиска O (log n), IIRC.
Ниша - это списки смежности для неориентированных плоских графов с O (1) соседними запросами. Это не столько структура данных, сколько особый способ организации существующей структуры данных. Вот как вы это делаете: каждый плоский граф имеет node со степенью не выше 6. Выберите такой node, поместите его соседей в свой список соседей, удалите его из графика и повторите, пока граф не станет пустым. При задании пары (u, v) найдите u в списке v-соседей и для v в списке соседей u. Оба имеют размер не более 6, поэтому это O (1).
В соответствии с вышеприведенным алгоритмом, если u и v являются соседями, вы не будете иметь как u в списке v, так и v в списке u. Если вам это нужно, просто добавьте каждый node отсутствующих соседей в этот список сокетов node, но сохраните, сколько из списка соседей вам нужно просмотреть для быстрого поиска.
Я думаю, что беззаботные альтернативы стандартным структурам данных, а также блокировка очереди, стека и списка сильно игнорируются. Они становятся все более актуальными, так как concurrency становится более высоким приоритетом и является гораздо более замечательной целью, чем использование мутексов или блокировок для обработки параллельных операций чтения/записи.
Здесь несколько ссылок
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
Я думаю, что Disjoint Set довольно изящна для случаев, когда вам нужно разделить кучу элементов на разные наборы и членство в запросе. Хорошая реализация операций "Союз" и "Найти" приводит к амортизированным издержкам, которые являются фактически постоянными (обратная функция Акерманна, если я правильно помню свой класс структур данных).
Они используются в некоторых из наиболее быстрых известных алгоритмов (асимптотически) для множества связанных с графом проблем, таких как проблема Shortest Path. Алгоритм Дейкстры выполняется в O (E log V) времени со стандартными двоичными кучами; используя кучи Фибоначчи, улучшает это до O (E + V log V), что является огромным ускорением для плотных графов. К сожалению, однако, они имеют высокий постоянный фактор, часто делая их практически непрактичными на практике.
Любой, кто имеет опыт 3D-рендеринга, должен быть знаком с деревьями BSP. Как правило, это метод путем структурирования 3D-сцены, которая может быть управляемой для визуализации знания координат камеры и несущей.
Разделение двоичного пространства (BSP) является метод рекурсивного разбиения пространства в выпуклые множества гиперплоскостями. Это подразделение представление сцены средствами структуры данных дерева, известной как Дерево BSP.
Другими словами, это метод разрушение сложной формы многоугольники в выпуклые множества или меньшие полигоны, состоящие полностью из не рефлекторные углы (углы меньше 180 °). Для более общего описания пространственного разбиения, см. пространство разделение.
Первоначально этот подход был предложен в 3D-компьютерной графике увеличить эффективность рендеринга. Некоторые другие приложения включают выполнение геометрические операции с фигурами (конструктивная сплошная геометрия) в САПР, обнаружение столкновения в робототехнике и 3D компьютерные игры и другой компьютер приложения, которые включают обработку сложные пространственные сцены.
Деревья Хаффмана - используется для сжатия.
Посмотрите Finger Trees, особенно если вы фанат ранее упомянутых чисто функциональных структур данных. Они являются функциональным представлением постоянных последовательностей, поддерживающих доступ к концам в амортизированном постоянном времени, и конкатенацией и расщеплением во времени логарифмическим размером меньшего размера.
По исходная статья:
Наши функциональные 2-3 пальцевые деревья являются примером общей методики проектирования, введенной Окасаки (1998), которая называется неявным рекурсивным замедлением. Мы уже отмечали, что эти деревья являются расширением его неявной структуры deque, заменяя пары на 2-3 узла, чтобы обеспечить гибкость, необходимую для эффективного конкатенации и разделения.
A Finger Tree можно параметризовать с помощью monoid, и использование разных моноидов приведет к разному поведению для дерева. Это позволяет Finger Trees моделировать другие структуры данных.
Циклический или кольцевой буфер - используется для потоковой передачи, между прочим.
Я удивлен, что никто не упомянул деревья Меркле (т.е. Hash Trees).
Используется во многих случаях (программы P2P, цифровые подписи), где вы хотите проверить хэш целого файла, когда у вас есть только часть доступного вам файла.
<zvrba> Деревья Ван Эмд-Боас
Я думаю, было бы полезно узнать, почему они классные. В общем, вопрос "почему" является самым важным, чтобы спросить;)
Отвечаю, что они дают вам слова O (log log n) с ключами {1..n}, независимо от того, сколько ключей используется. Точно так же, как повторное наполовину дает вам O (log n), повторный sqrting дает вам O (log log n), что и происходит в дереве vEB.
Как насчет splay trees?
Кроме того, приходят на ум Крис Окасаки чисто функциональные структуры данных.
Интересный вариант хеш-таблицы называется Cuckoo Hashing. Он использует несколько хеш-функций вместо 1, чтобы справиться с хэш-коллизиями. Столкновения разрешаются удалением старого объекта из местоположения, указанного основным хешем, и перемещения его в место, заданное альтернативной хэш-функцией. Cuckoo Hashing позволяет более эффективно использовать пространство памяти, потому что вы можете увеличить коэффициент загрузки до 91% только с 3 хэш-функциями и по-прежнему иметь хорошее время доступа.
A min-max heap - это вариант heap, который реализует двухсторонний приоритетной очереди. Это достигается путем простого изменения свойства кучи: Дерево считается минимальным, если каждый элемент на четных (нечетных) уровнях меньше (больше), чем все дети и внуки. Уровни нумеруются начиная с 1.
http://internet512.chonbuk.ac.kr/datastructure/heap/img/heap8.jpg
Мне нравится Cache Oblivious datastructures. Основная идея состоит в том, чтобы выложить дерево в рекурсивно меньших блоках, чтобы кеши разных размеров использовали преимущества блоков, которые им удобны. Это приводит к эффективному использованию кэширования для всего, начиная с кеша L1 в ОЗУ и заканчивая большими фрагментами данных, считываемых с диска, без необходимости знать особенности размеров любого из этих слоев кеширования.
Левые опускающиеся красно-черные деревья. Значительно упрощенная реализация красно-черных деревьев Робертом Седжуиком, опубликованная в 2008 году (~ половина строк кода для реализации). Если вам когда-либо приходилось сталкиваться с проблемой создания дерева красно-черных, прочитайте об этом варианте.
Очень похоже (если не идентично) деревьям Андерссон.
Работа кражи очереди
Блокированная структура данных для деления рабочего равенства между несколькими потоками Реализация очереди кражи работы в C/С++?
Загруженные кусочно-биномиальные кучи от Gerth Stølting Brodal и Chris Okasaki:
Несмотря на свое длинное имя, они обеспечивают асимптотически оптимальные операции кучи даже в настройке функции.
O(1) размер, объединение, вставить, минимумO(log n) deleteMinОбратите внимание, что объединение принимает O(1), а не O(log n) время, в отличие от более известных куч, которые обычно рассматриваются в учебниках по структуре данных, таких как левые кучи. И в отличие от Fibonacci heaps, эти асимптотики в худшем случае, а не амортизируются, даже если они используются постоянно!
В Haskell есть несколько реализация.
Они были совместно выработаны Бродалем и Окасаки, после того как Бродаль придумал императивную кучу с той же асимптотикой.
Большинство, если не все, из них задокументированы в NIST Словарь алгоритмов и структур данных
Шары. Просто потому, что они заставляют людей хихикать.
Дерево шаров - это структура данных, которая индексирует точки в метрическом пространстве. Здесь статья о их создании. Они часто используются для поиска ближайших соседей в точке или ускорения k-средних.
Не действительно структура данных; больше возможностей для оптимизации динамически распределенных массивов, но буферы разметки, используемые в Emacs, выглядят довольно круто.
Дерево Фенвика. Это структура данных, чтобы содержать счетчик суммы всех элементов в векторе, между двумя данными субиндексами я и j. Тривиальное решение, предварительно вычисляющее сумму с начала, не позволяет обновить элемент (вам нужно выполнить O (n), чтобы не отставать).
Деревья Fenwick позволяют вам обновлять и запрашивать в O (log n), и как это работает, действительно круто и просто. Это действительно хорошо объяснено в оригинальной бумаге Фенвика, свободно доступной здесь:
http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol24/issue3/spe884.pdf
Его отец, дерево RQM также очень круто: он позволяет вам сохранять информацию о минимальном элементе между двумя индексами вектора, а также работает в O (log n) обновлении и запросе. Мне нравится сначала обучать RQM, а затем Fenwick Tree.
деревья Ван Эмд-Боас. У меня есть даже С++ реализация, для целых 2 ^ 20 целых чисел.
Вложенные наборы хороши для представления деревьев в реляционных базах данных и выполнения запросов на них. Например, ActiveRecord (Ruby on Rails по умолчанию ORM) поставляется с очень простым вложенным набором плагинов, что делает работу с деревьями тривиальной.
Это довольно специфичная для домена, но структура данных половинного края довольно аккуратная. Он обеспечивает возможность итерации по многоугольным сеткам (граням и краям), что очень полезно в компьютерной графике и вычислительной геометрии.