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

Дерево Фенвик. Это структура данных для подсчета суммы всех элементов в векторе между двумя заданными субиндексами i и j. Тривиальное решение, предварительное вычисление суммы, поскольку начало не позволяет обновить элемент (вам нужно выполнить O (n) работу, чтобы не отставать).

Деревья Фенвика позволяют обновлять и запрашивать в O (log n), и как это работает, действительно круто и просто. Это действительно хорошо объяснено в оригинальной статье Фенвика, свободно доступной здесь:

http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol24/issue3/spe884.pdf

Его отец, дерево RQM, также очень круто: оно позволяет хранить информацию о минимальном элементе между двумя индексами вектора, а также работает при обновлении и запросе O (log n). Мне нравится преподавать сначала RQM, а затем - Дерево Фенвика.

Шаровые деревья. Просто потому, что они заставляют людей хихикать.

Шаровое дерево - это структура данных, которая индексирует точки в метрическом пространстве. Вот статья о их создании. Они часто используются для поиска ближайших соседей к точке или ускорения k-средних.

Bootstrapped skew-binomial heaps от Gerth Stølting Brodal и Chris Okasaki:

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

• O(1) size, union, insert, minimum
• O(log n) deleteMin

Обратите внимание, что объединение занимает O(1), а не O(log n) времени, в отличие от более известных куч, которые обычно рассматриваются в учебниках по структурам данных, таких как левые кучи. И в отличие от кучи Фибоначчи, эти асимптотики являются наихудшими, а не амортизированными, даже при постоянном использовании!

Существует несколько реализаций на языке Haskell.

Они были выведены совместно Бродалом и Окасаки, после того как Бродал придумал императивную кучу с такой же асимптотикой.

Смотрите на поперечную "кучу", представленную Donald Knuth.

http://stanford-online.stanford.edu/seminars/knuth/071203-knuth-300.asx

Я люблю суффиксное дерево и массивы для строковой обработки, пропускаю списки для сбалансированных списков и вывихиваю деревья для автоматических деревьев балансировки

Считаемые неотсортированные сбалансированные B-деревья.

Идеально подходящий для буферов текстового редактора.

http://www.chiark.greenend.org.uk/~sgtatham/algorithms/cbtree.html

Списки пропуска действительно хороши: http://en.wikipedia.org/wiki/Skip_list

Если отвлечься от всех этих графических структур, мне просто нравится простой Ring-Buffer .

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

Попытки Fast Compact:

• Массивы Judy : очень быстрые и эффективные с точки зрения памяти упорядоченные разреженные динамические массивы для битов, целых чисел и строк. Массивы Judy быстрее и эффективнее с точки зрения памяти, чем любое дерево двоичного поиска.

• HAT-trie: Trie-ориентированная структура данных для строк с учетом кеширования

• B-попытки для управления строками на основе диска

Вы можете использовать минимальную кучу, чтобы найти минимальный элемент в постоянное время или максимальный куча, чтобы найти максимальный элемент. Но что, если вы хотите сделать обе операции? Вы можете использовать min-Max , чтобы выполнить обе операции в постоянное время. Он работает с использованием min max упорядочения: чередуется между мин и максимальным сравнением кучи между последовательным деревом.

Один известный, но довольно нефтепользовательская структура данных - это дерево Фенвик (также иногда называемое двоичным деревом или бит). Он хранит кумулятивные суммы и поддерживает операции O (log (n)). Хотя совокупные суммы могут не звучать очень захватывать, его можно адаптировать для решения многих проблем, требующих сортировкой / журнала (N) структуры данных.

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

Приоритетная двухсторонняя очередь дешевле, чем необходимость поддерживать 2 отдельные очереди приоритетов с разным порядком. http://www.alexandria.ucsb.edu/middleware/javadoc/edu/ucsb/adl/middleware/PriorityDeque.html http://cphstl.dk/Report/Priority-deque/cphstl-report -2001-14.pdf

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

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

Сбалансированные двоичные деревья (они же деревья AVL) тратят много времени на балансировку после каждой вставки.

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

Деревья козла отпущения остаются сбалансированными, как красно-черные деревья, но не требуют НИКАКОГО дополнительного хранения. Для этого они анализируют дерево после каждой вставки и вносят небольшие коррективы. См. http://en.wikipedia.org/wiki/Scapegoat_tree.

Постоянные структуры данных

Я иногда использую Inversion LIsts для хранения диапазонов, и они часто используются для хранения классов символов в регулярных выражениях. См., Например, http://www.ibm.com/developerworks/linux/library/l-cpinv.html

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

   a => 0.1
   b => 0.5
   c => 0.4

. Затем вы вычисляете текущую сумму всех вероятностей:

  (0.1, 0.6, 1.0)

Это ваш список инверсии. Вы генерируете случайное число от 0 до 1 и находите индекс следующей более высокой записи в списке. Вы можете сделать это с помощью двоичного поиска, потому что он отсортирован. Получив указатель, вы можете найти символ в исходном списке.

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

В одном из вариантов инверсионных списков для обозначения конечной точки диапазонов используются отрицательные числа, что позволяет легко подсчитать, сколько диапазонов перекрываются в определенной точке. См. Пример http://www.perlmonks.org/index.pl?node_id=841368 .

2-3 Finger Trees от Hinze и Paterson - это отличная функциональная структура данных swiss-army knife с отличной асимптотикой для широкого спектра операций. Несмотря на свою сложность, они гораздо проще, чем предшествующие им императивные структуры Постоянные списки с катенацией через рекурсивное замедление Каплана и Тарджана.

Они работают как catenable deque с O(1) доступом к любому концу, O(log min(n,m)) append, и обеспечивают O(log min(n,length - n)) индексацию с прямым доступом к моноидальной префиксной сумме над любой частью последовательности.

Реализации существуют в Haskell, Coq, F#, Scala, Java, C, Clojure, C# и другие языки.

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

У меня также есть несколько слайдов, описывающих их получение и использование.

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

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

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

Хуже всего рассматривать строку как символьный массив в C и полагаться на нулевой байт в целях безопасности.

Лично мне очень интересны разреженные матричные структуры данных. http://www.netlib.org/linalg/html_templates/node90.html

Их используют известные библиотеки BLAS. И когда вы имеете дело с линейными системами, которые содержат 100 000 строк и столбцов, их использование становится критически важным. Некоторые из них также напоминают компактную сетку (в основном, как сетку с сортировкой по ведру), которая является обычной в компьютерной графике. http://www.cs.kuleuven.be/~ares/publications/LD08CFRGRT/LD08CFRGRT.pdf

Также, что касается компьютерной графики, сетки MAC несколько интересны, но только потому, что они умны . http://www.seas.upenn.edu/~cis665/projects/Liquation_665_Report.pdf

Дельта-список / дельта-очередь используются в таких программах, как cron или симуляторы событий, чтобы определить, когда должно сработать следующее событие. http://everything2.com/title/delta+list http://www.cs.iastate.edu/~cs554/lec_notes/delta_clock.pdf

Отслеживание окружающей среды рекурсивными структурами.

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

public class Env
{    
    HashMap<String, Object> map;
    Env                     outer;

    Env()
    {
        outer = null;
        map = new HashMap();
    }

    Env(Env o)
    {
        outer = o;
        map = new HashMap();
    }

    void put(String key, Object value)
    {
        map.put(key, value);
    }

    Object get(String key)
    {
        if (map.containsKey(key))
        {
            return map.get(key);
        }
        if (outer != null)
        {
            return outer.get(key);
        }
        return null;
    }

    Env push()
    {
        return new Env(this);
    }

    Env pop()
    {
        return outer;
    }
}

Я не уверен, что у этой структуры вообще есть название. Я называю это списком наизнанку.

PQ-Trees

Существует умная структура данных, которая использует массивы для сохранения данных Элементы, но массивы связаны друг с другом в связанный список / массив.

Это имеет то преимущество, что итерация по элементам выполняется очень быстро (быстрее, чем подход с использованием чистого связанного списка), а затраты на перемещение массивов с элементами в памяти и / или (де-) выделение не превышают минимум. (Из-за этого эта структура данных полезна для моделирования).

Я знаю об этом отсюда:

http://software.intel.com/en-us/blogs/2010/03/26/linked-list-verses-array/

"... и что дополнительный массив выделяется и связан со списком ячеек массивов частиц. В некоторых отношениях это похоже на то, как TBB реализовал свой параллельный контейнер ». (Речь идет о производительности связанных списков по сравнению с массивами)

Кто-то уже предложил Буркхарда-Келлера -Деревья, но я подумал, что могу упомянуть их еще раз, чтобы добавить свою собственную реализацию. :)

http://well-adjusted.de/mspace.py/index.html

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

Кстати, деревья BK и VP могут использоваться не только для поиска похожих строк. Вы можете выполнять поиск сходства для произвольных объектов, если у вас есть функция расстояния, удовлетворяющая нескольким условиям (положительность, симметрия, неравенство треугольника).

Раньше мне везло с WPL Trees. Вариант дерева, который минимизирует взвешенную длину пути между ветвями. Вес определяется доступом к узлам, так что часто посещаемые узлы мигрируют ближе к корню. Не уверен, как они соотносятся с splay-деревьями, так как никогда их не использовал.

Bucket Brigade

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

Допустим, у вас есть группа сегментов, которые содержат html-документ с одним символом на сегмент. Вы хотите преобразовать все символы < и > в объекты < и > . Группа сегментов позволяет вам вставить дополнительные сегменты в группу, когда вы встречаетесь с символом < или > , чтобы уместить дополнительные символы, необходимые для объекта. Поскольку бригада ковшей находится в кольце, вы можете вставлять их вперед или назад. Это намного проще сделать (на C), чем использовать простой буфер.

Некоторые ссылки на бригады ведра ниже:

Справочник бригады ведра Apache

Введение в ковши и бригады