Эффективная реализация trie для .net

Question

Я ищу реализацию trie для .net.

Я планирую использовать его в качестве структуры индекса для моего пула объектов в памяти. Он не должен быть потокобезопасным (поскольку только один поток будет его обновлять), но он должен иметь возможность не менее 20 миллионов элементов изящно и с постоянной производительностью.

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

PS: Я выбрал попытки, поскольку, похоже, реализация хэш-таблиц, которые я видел, использует слишком много памяти и, как правило, вызывает фрагментацию памяти, поскольку они основаны на массивах. Любой такой контейнер с характеристиками поиска O (1) и полезными характеристиками памяти для большого количества элементов также может быть в порядке.

Спасибо,

Answer 1

По моему личному мнению, пытающегося предугадывать собственное управление памятью .NET не является практикой я рекомендую. Вы просто не можете обеспечить уровень управления распределением памяти, который вы можете в собственном сценарии, но в равной степени вам не нужно. Я был одержим желанием сделать это, когда я впервые перешел с C++ (где я регулярно работал со своими собственными кучами и записывал процедуры локализации памяти и т. Д.), Но быстро стало очевидно, что мне просто не нужно, или может I.

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

Это означает, что вместо этого используется тип значения, но они просто не подходят для использования в объединенном сценарии, потому что пользовательские типы значений должны быть неизменными (я могу сказать, что безопасно, не оправдывая его - просто google 'неизменяемый' и ' struct 'targetpage site: stackoverflow.com, чтобы увидеть больше), и поэтому не следует относиться к объектам многократного использования.

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

Если у вас слишком много объектов, чтобы поместиться в памяти, то либо:

1) Получить больше памяти

2) использовать базу данных и кэш локальных сегментов ней

Или как: Вы могли бы рассмотрите вопрос о AppFabric and its cache features, таким образом вы можете построить ферму машин, предназначенную для работы в кэшах в памяти миллионов объектов. Стоимость аппаратных средств, вероятно, будет меньше, чем стоимость разработки собственного решения для управления памятью для .Net :)

Answer 2

Взгляните на эту библиотеку: TrieNet

using Gma.DataStructures.StringSearch; 

... 

var trie = new SuffixTrie<int>(3); 

trie.Add("hello", 1); 
trie.Add("world", 2); 
trie.Add("hell", 3); 

var result = trie.Retrieve("hel");