Наибыстрейший автокомплит + сортировка, какую дата структуру выбрать?
Добрый день.
Встала задача по поиску через автокомплит, сделал trie, но сортировка работает очень медленно
150000 слов с приоритетом
10 000 запросов, должно работать не больше 10 секунд.
Приложение консольное, вывод 5 секунд
Ответ найден, использовал 2 структуры, trie+red-black trees.
На каждую ноду есть коллекция SortedSet, она работает как red-black-tree.
Соответственно в коллекцию попадают все ноды которые проходят дерево.
В конечном итоге получаем отсортированную коллекцию.
Насчет памяти только не эффективно, но там используются классы для ноды, не структуры. Так что в коллекции хранятся только ссылки.
Требования по памяти не было.
