Это звучит как простой вопрос, но я не знаю, как найти на него ответ.
У меня есть реализация trie на С#, которая будет хранить около 80 тысяч слов из файла словаря. Загрузка всех этих слов занимает довольно много времени (более 5 минут). Мне было интересно, как лучше всего «сохранить» эти данные, чтобы мне не приходилось перезагружать все слова каждый раз, когда я запускаю приложение?
Спасибо.
Как и все другие проблемы с производительностью, идеальное решение будет получено из профилирования вашего текущего решения и других возможных решений, которые вы придумаете. Где узкое место? Ввод/вывод? Лексировать текст? Формирование ссылок в дереве? Будет трудно сделать конкретное предложение, не зная ваших целей по производительности, характера использования trie и существующих узких мест.
Вопросы для рассмотрения:
Одна из возможных стратегий: создать и поддерживать словарь «самых распространенных слов» с 1000 (или около того) наиболее часто используемых слов. Загружайте эти слова в trie при запуске и инициируйте загрузку полного словаря в другом потоке; постепенно добавляя к созданному дереву по мере чтения новых слов.
Недавно я рефакторил аналогичную структуру данных из-за низкой производительности и медленной сериализации/десериализации.
Мое решение состояло в том, чтобы полностью отказаться от этой попытки и перейти к собственным коллекциям .NET - словарям и поискам.
Я работаю примерно с 400 тыс. слов. Из памяти требуется около 5 секунд, чтобы построить структуру данных, которая представляет собой список объектов, проиндексированных рядом словарей и поисковых запросов.
Dictionary<int, var>, где ключом является n — количество букв в поисковом запросе.Lookup<string,
string>, где ключ — это строка из n букв, а значение — это все строки, начинающиеся с этой строки. например, для ключа «st» значения могут быть «начало», «стоп» и «строка».Чтобы создать структуру данных, я просто перебираю весь список слов от i = 1 до maxlength, чтобы создать поиск всех отдельных строк «начинается с» для каждого i. Вставьте их в словарь верхнего уровня, и все готово.
Это устраняет необходимость в пользовательском построении trie. Я обнаружил, что разница в производительности (время поиска) незначительна, но скорость загрузки чрезвычайно благоприятствует моему дизайну (не говоря уже о простоте и удобстве использования простых типов .NET).
Я бы просто сериализовал его в старом бинарном стиле MFC. По сути, чтение/запись должны быть максимально быстрыми, и единственное, что вам остается, это выделение и инициализация структуры на входе, что вам все равно нужно сделать.
То есть, чтобы сериализовать узел дерева, вы делаете следующее:
Read/Write number N of subnodes
For each subnode
If reading, allocate a subnode in this node
Read/Write the character for the subnode
Serialize the subnode
End
Редактировать: просто перечитайте свой вопрос, и вы хотите построить тройку с нуля из списка слов? Как говорили другие, профилируйте, но не только с помощью любого старого профилировщика. Они не все находят вашу проблему. Вот что я делаю. Время, необходимое для этого, не должно быть намного больше, чем время, необходимое для чтения файла, плюс время, необходимое для создания структуры.
