Современные структуры данных

Ответ 1

Это действительно зависит от вашего определения "недавно". CLRS содержит большое количество структур данных, но опускает многие из структур, которые были разработаны в это время. Например, к этому времени было разработано дерево Ван Эмде Боас, которое обеспечивает чрезвычайно быстрое хранение и поиск целых чисел, но нигде не упоминалось.

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

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

Распределенные структуры данных имеют большой импорт в эти дни. Google BigTable - отличный пример. Аналогично, параллельные или блокированные структуры данных нашли свой путь во многих языках программирования (см., Например, Java ConcurrentHashMap или CopyOnWriteArrayList).

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

Вероятностные структуры, такие как treap и skip list, обладали большой исследовательской деятельностью и являются прекрасным местом для изучения. В связанном вене мощные хеш-таблицы, такие как хеш-таблица кукушки или динамические идеальные хеш-таблицы, безусловно, заслуживают внимания.

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

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

Многие исследователи приложили усилия к созданию структур данных, которые используют тот факт, что современные машины могут работать на нескольких битах параллельно. Некоторые структуры, такие как дерево слияния, экспоненциальное дерево или y-fast tree, используют эти свойства для сортировки и поиска в массивах целых чисел быстрее, чем барьеры O (n lg n), введенные в наивной модели сравнения.

Также выполняется большая работа над структурами сводных данных, эскизов и синопсисов, которые пытаются дать ответы на вопросы о наборе данных, не сохраняя явно весь набор. Экран Count-Min является отличным примером одной из этих структур данных.

Это всего лишь небольшая выборка новых и классных структур. Надеюсь, это хорошая отправная точка!

Ответ 2

Некоторые из относительно недавних (как и в последние 30 лет) нововведений структуры данных были вероятностными, например Пропустить списки. Я нахожу их особенно интересными, но я не занимаюсь исследованиями. Чтение последних ACM Transactions on Algorithms может помочь вам найти интересные и передовые исследования.

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

Ответ 3

Существует множество сотен специализированных структур данных. http://en.wikipedia.org/wiki/List_of_data_structures - хорошее начало.

Ответ 4

Хэширование кукушки - это схема на компьютере программирование для разрешения хэша столкновения значений хэш-функций в таблице. Сначала было хеширование кукушки описанные Расмусом Пагом и Флеммингсом Фрише Родлер в 2001 году.

http://en.wikipedia.org/wiki/Cuckoo_hashing

Затем свежие: Нечеткие структуры данных