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

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

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

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

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

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

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

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

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

Взгляните на эту библиотеку: 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");