Эффективная реализация Trie для .net - PullRequest
Новая
       15

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

1 голос
/ 17 января 2012

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

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

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

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

Спасибо,

Ответы [ 2 ]

1 голос
/ 31 августа 2017

Посмотрите на эту библиотеку: 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");
0 голосов
/ 17 января 2012

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

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

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

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

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

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

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

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

...