Реализация Trie [закрывается]

Ссылки,

• Статья Реализация Trie с двумя массивами (включает реализацию C )
• TRASH - Динамический LC-дерево и структура хэш-данных - (справочник в формате PDF 2006 г., описывающий динамическое LC-дерево, используемое в ядре Linux для реализации поиска адреса в таблице IP-маршрутизации

Мне повезло с libTrie . Возможно, он не был специально оптимизирован для кеширования, но производительность для моих приложений всегда была достойной.

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

Оптимизация кеша - это то, что вам, вероятно, придется сделать, потому что вам придется поместить данные в одну строку кеша, которая обычно выглядит примерно так: 64 байта (что, вероятно, будет работать, если вы начнете объединять данные, например указатели). Но это'

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

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

Одно явно учитывающее кэширование дерево, о котором я знаю, - это HAT-дерево .

HAT-trie, если он реализован правильно, очень крут. Однако для поиска по префиксу вам понадобится этап сортировки хеш-сегментов, что несколько противоречит идее префиксной структуры.

Несколько более простым деревом является burst-trie , которое, по сути, дает вам интерполяцию между стандартным деревом некоторого вида (например, BST) и деревом . Мне нравится концептуально, и это намного проще реализовать.