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

Question

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

Мне интересно, о каких других структурах данных мне нужно знать? Я знаю о - массиве, списке, стеке, очереди, связанном списке, хэш-таблице, дереве и его различных формах, таких как B-дерево, Trie и т. Д. Хотелось бы узнать, считаете ли вы какую-либо другую структуру данных / концепцию интересной и полезной в обычном цикле разработки.

Answer 1

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

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

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

Наконец, вы можете пойти функциональным путем и посмотреть на неизменные и постоянные структуры данных.Многие из них являются просто функциональными версиями структур данных, которые вы уже знаете.Если вы заинтересованы в этом, то я рекомендую проверить чисто функциональные структуры данных Окасаки .

Answer 2

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

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