Tries - все еще хорошая идея на современных архитектурах?

Question

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

Для сравнения, сбалансированное дерево будет равно O (log N) по количеству элементов набора плюс все, что вы платите за сравнения. Хеш-таблица будет включать в себя вычисление, сравнение и т. Д.

Поэтому меня удивляет, что нет реализации Trie в стандартной библиотеке большинства языков .

Единственной причиной, по которой я смог придумать, была возможность того, что стоимость доступа к памяти делает ее слишком дорогой. Вместо того, чтобы исследовать O (log N) местоположений при выполнении поиска по дереву, вы не делаете O (| length |) разных местоположений со всеми вытекающими последствиями. Если строки длинные, это может оказаться слишком много.

Так что мне интересно: сколько стоит то, о чем я только что описал? Что вы делаете, когда вам нужно хранить большой набор или карту строк?

Answer 1

Раньше я не думал об этом как о проблемной области, но теперь, когда вы упомянули об этом, бывают ситуации, когда стандартная реализация Trie может оказаться полезной. С другой стороны, насколько я знаю, Tries используются Python, Perl и другими языками со здравым смыслом, которые я использую сейчас.

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

Answer 2

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

Answer 3

Я провел некоторое тестирование производительности в C # с помощью Trie и Dictionary (строго типизированная хеш-таблица). Я обнаружил, что словарь был в 5-10 раз быстрее, чем Trie. Возможно, моя реализация Trie могла бы быть немного оптимизирована, но вряд ли достаточно, чтобы быть намного быстрее, чем (или, возможно, даже так же быстро), как словарь.

Метод ContainsKey в словаре близок к операции O (1) (в зависимости от того, насколько хорош алгоритм хеширования), поэтому нелегко создать коллекцию, которая побеждает, если алгоритм хеширования достаточно быстр.

С пользовательским IEqualityComparer вы можете использовать практически все что угодно в качестве ключа в словаре, что делает его довольно гибким. Trie немного более ограничен в том, что вы можете использовать в качестве ключа, так что это несколько ограничивает полезность.