Наибыстрейший автокомплит + сортировка, какую дата структуру выбрать?

Question

[Артур Нуруллин]

Добрый день.
Встала задача по поиску через автокомплит, сделал trie, но сортировка работает очень медленно
150000 слов с приоритетом
10 000 запросов, должно работать не больше 10 секунд.
Приложение консольное, вывод 5 секунд

Answer 1

[Артур Нуруллин]

Ответ найден, использовал 2 структуры, trie+red-black trees.

На каждую ноду есть коллекция SortedSet, она работает как red-black-tree.
Соответственно в коллекцию попадают все ноды которые проходят дерево.
В конечном итоге получаем отсортированную коллекцию.

Насчет памяти только не эффективно, но там используются классы для ноды, не структуры. Так что в коллекции хранятся только ссылки.
Требования по памяти не было.

Answer 2

[uvelichitel]

• Фильтр Блума.
  
• Бор Ахо-Корасик.
  

Comments

[Артур Нуруллин]

Фильтр Блума не работает как автокомплит, он смотрит на содержание по хешу.