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

Ответ 1

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

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

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

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

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

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

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

Ответ 2

B-tree находятся в базах данных.

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

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

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

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

Ответ 3

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

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

Сделайте сортировку, например:

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

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

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

Ответ 4

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

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

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

Ответ 5

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

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

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

Ответ 6

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

Ответ 7

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

Ответ 8

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

Ответ 9

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

Ответ 10

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

Ответ 11

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

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

Ответ 12

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

Ответ 13

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

Ответ 14

Сбалансированные деревья (Red-black и т.д.) обычно используются при реализации абстрактного типа данных.

Существует только относительно небольшое количество абстрактных типов данных, таких как

• список
• Карта
• упорядоченная карта
• multi map
• упорядоченная мульти карта
• приоритетная очередь (которая очень похожа на упорядоченную карту)

Аналогично, набор выглядит как карта, но вам не нужны значения, только ключи.

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

Вы сказали "Словарь", вы, вероятно, имели в виду либо карту, либо упорядоченную карту.

Некоторые карты неупорядочены (обычно реализуются как хэш) - это полезное подмножество упорядоченной карты.