Каковы некоторые менее известные структуры данных и алгоритмы, о которых нужно знать?
Недавно я столкнулся со структурой данных SkipList. Это действительно помогло мне решить в других отношениях трудно решаемую проблему. Я изо всех сил пытался решить его с помощью Сбалансированного Двоичного дерева, но это стало очень сложным, поскольку дерево должно всегда балансироваться, и я хотел знать существование не только конкретное значение, но и значения в определенном диапазоне. SkipList помог мне решить ту проблему эффективно.
Я задаюсь вопросом, о чем других структурах данных я должен знать? Я знаю о - Массив, Список, Стек, Очередь, Связанный список, хеш-таблица, дерево и его различные формы как B-дерево, Trie и т.д. Хотел бы знать, находите ли Вы некоторую другую структуру данных / понятием интересный, а также полезный в регулярном цикле разработки.
2 ответа
Вы не упомянули о графах, которые являются очень мощным инструментом, и если вы не знаете о них, вам определенно следует прочитать о них. Поищите алгоритм Дейкстры и алгоритм поиска A*, а также общие алгоритмы поиска в глубину и в ширину.
Вы также не упомянули кучи, которые часто используются в качестве базовой структуры для очереди приоритетов. Бинарные кучи - самые простые, но можно также рассмотреть кучи min-max-median, биномиальные кучи (быстрое объединение) и кучи Фибоначчи (быстрый ключ уменьшения - полезно для некоторых графовых алгоритмов).
Другие интересные структуры данных включают Patricia tries, которые являются экономичными в пространстве попытками (ключ на подстроках вместо символов), splay trees, которые являются сбалансированными и могут быть запрограммированы на постоянство. Также посмотрите фильтры Блума - это вероятностная структура данных, которая позволяет определить, является ли элемент членом множества. Она может иметь ложноположительные, но не ложноотрицательные результаты и эффективна в отношении пространства и времени.
Наконец, можно пойти по функциональному пути и рассмотреть неизменяемые и постоянные структуры данных. Многие из них - это просто функциональные версии уже известных вам структур данных. Если вас это интересует, то я рекомендую ознакомиться с Чисто функциональными структурами данных Окасаки.
У вас есть и "List", и "Linked List", и совершенно не ясно, какую разницу (если она вообще есть) вы подразумеваете между ними. В любом случае, одна очевидная структура, которую вы пропустили - это куча (которую вы, возможно, классифицируете как тип дерева, но это в лучшем случае весьма неопределенно). В конечном счете, деревья являются подмножеством графов, так что если вы не изучали графы (в целом), это, вероятно, область для изучения.
Я бы отметил, что ни одна из этих структур не является особенно "недавней" - все они известны уже несколько десятилетий. Большинство из этих действительно общих структур были известны уже довольно давно. Недавно открытые, как правило, относятся к более конкретным предметным областям.