Продвинутые структуры данных на практике

Question

За 10 лет, которые я программировал, я могу подсчитать количество структур данных, которые я использовал с одной стороны: массивы, связанные списки (я собираю стеки и очереди с этим) и словари. Это не удивительно, учитывая, что почти все написанные мной приложения попадают в категорию форм-над-данными / CRUD.

Мне никогда не приходилось использовать красно-черное дерево, список пропусков, двустороннюю очередь, циклически связанный список, приоритетную очередь, кучи, графики или любые из десятков экзотических структур данных, которые были исследованы в последние 50 лет Я чувствую, что пропускаю.

Это открытый вопрос, но где эти "экзотические" структуры данных используются на практике? Кто-нибудь имеет реальный опыт использования этих структур данных для решения конкретной проблемы?

Answer 1

Несколько примеров. Они расплывчаты, потому что работали на работодателей:

• A heap , чтобы получить первые N результатов поиска в стиле Google. (Начиная с кандидатов в индексе, проходите их все линейно, просеивая их через минимальную кучу максимального размера N.) Это было для прототипа поиска изображения.

• Фильтры Блума сокращают размер определенных данных о том, что миллионы пользователей увидели, до объема, который поместился бы в существующих серверах (все это должно было быть в оперативной памяти для скорости); исходный дизайн потребовал бы много новых серверов только для этой базы данных.

• A представление треугольного массива вдвое уменьшило размер плотного симметричного массива для механизма рекомендаций (снова RAM по той же причине).

• Пользователи должны были быть сгруппированы в соответствии с определенными ассоциациями; union-find сделал это простым, быстрым и точным, а не медленным, хакерским и приблизительным.

• Приложение для выбора магазинов розничной торговли в зависимости от времени в пути для жителей района использовало Кратчайший путь Дейкстры с приоритетными очередями. В других работах по ГИС использовались индексы quadtree и Morton .

Знание того, что существует в структурах данных, очень полезно - «недели в лаборатории могут сэкономить вам часы в библиотеке». Случай с фильтром Блум был полезен только из-за масштаба: если бы проблема возникла при запуске вместо Yahoo, я бы использовал старую хеш-таблицу. Другие примеры, на мой взгляд, приемлемы везде (хотя в настоящее время вы реже их сами кодируете).

Answer 2

B-деревья находятся в базах данных.

R-деревья предназначены для географического поиска (например, если у меня есть 10000 фигур, каждая с ограничивающим прямоугольником, разбросанным по 2-D плоскости, какие из этих фигур пересекают произвольную ограничивающую рамку B?)

deques формы в C ++ STL являются растущими векторами (более эффективными по памяти, чем связанные списки, и с постоянным временем для «просмотра» произвольных элементов в середине). Насколько я помню, я никогда не использовал deque в полном объеме (вставка / удаление с обоих концов), но достаточно общего, чтобы вы могли использовать его как стек (вставка / удаление с одного конца) или очередь (вставка с одной стороны, удалить с другой), а также иметь высокопроизводительный доступ для просмотра произвольных элементов в середине.

Я только что закончил читать Обобщения и коллекции Java - часть "дженерики" ранит мою голову, но часть коллекций была полезна, и они указывают на некоторые различия между пропущенными списками и деревьями ( оба могут реализовывать карты / наборы): пропускающие списки дают вам встроенную итерацию с постоянным временем от одного элемента к другому (деревья - это O (log n)) и намного проще для реализации алгоритмов без блокировок в многопоточных ситуациях.

Приоритетные очереди используются для планирования среди прочего (вот веб-страница , в которой кратко обсуждается применение); кучи обычно используются для их реализации. Я также обнаружил, что heapsort (по крайней мере, для меня) является самым простым из всех видов O (n log n) для понимания и реализации.

Answer 3

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

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

Возьмите сортировку, например:

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

• главное преимущество кучи сортировка в том, что это можно сделать в situ с минимальным промежуточным хранение, что делает его довольно хорошим для использования в ограниченном объеме памяти системы. Пока медленнее в среднем (хотя все еще n log (n)), не страдает от плохой производительности в худшем случае быстрой сортировки.

• Третий пример - слияние сортировка , что можно сделать последовательно, что делает его лучшим много выбора для сортировки наборов данных больше, чем ваша основная память. Другое название для этого «внешний вид», то есть вы можете сортировка с использованием внешнего хранилища (диск или лента) для промежуточных результатов.

Answer 4

Это зависит от уровня абстракции, на которой вы работаете.

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

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

Answer 5

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

Древесные структуры широко используются в компьютерной графике.

Если вы используете карту STL или задаете структуры данных, то, вероятно, вы используете красно-черное дерево, даже не зная об этом!

Answer 6

кучи Фибоначчи используются для эффективной реализации алгоритма Дейкстры .

Answer 7

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

Answer 8

Я думаю, вы видите, что причудливые структуры данных используют большинство алгоритмов более высокого уровня. Главный пример, который мне приходит в голову, это A *, который использует Graph и Priority Queue, реализованные в Heap.

Answer 9

Я только что нашел применение для графиков, задав вопрос на stackoverflow:)

Answer 10

Да, иногда. Проблема, которую я вижу, заключается в том, что некоторые люди, хотя и знают их, но не знают, как их на самом деле применять. Большинство людей возвращаются к спискам, связанным с массивами и т. Д. Они в большинстве случаев выполняют свою работу в виде более продвинутой структуры данных (иногда вам действительно нужно «пнуть это»), они просто менее эффективны. Люди, как правило, делают то, что им легче, но это не обязательно лучший способ что-то сделать. Я не могу винить их, я уверен, что я делаю это тоже, но именно поэтому вы не видите много "продвинутых" концепций в программировании.