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

Question

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

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

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

Answer 1

Я использовал круговой список для кэширования.

Шаблон класса C ++ предоставляет интерфейс для получения объектов (Cache<Obj, Len>). Несколько его экземпляров возвращают разные типы «экранов», как в разных представлениях графического интерфейса. За кулисами, если запрошенный «экран» недоступен, он создается (дорогая операция) и помещается в верхнюю часть кольцевого буфера, выталкивая самую старую (выгружая ее текстуры и т. Д.).

Таким образом, достигается компромисс между чтением множества файлов изображений с жесткого диска и простой загрузкой всех изображений в ОЗУ и сохранением их навсегда. Компромисс контролируется длиной различных буферов.

Answer 2

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

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

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

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

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

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

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

Answer 3

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

Answer 4

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

Answer 5

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

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