Splo1ter
@Splo1ter
.NET Developer (9 years+)

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

Добрый день.
Встала задача по поиску через автокомплит, сделал trie, но сортировка работает очень медленно
150000 слов с приоритетом
10 000 запросов, должно работать не больше 10 секунд.
Приложение консольное, вывод 5 секунд
  • Вопрос задан
  • 413 просмотров
Решения вопроса 1
Splo1ter
@Splo1ter Автор вопроса
.NET Developer (9 years+)
Ответ найден, использовал 2 структуры, trie+red-black trees.

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

Насчет памяти только не эффективно, но там используются классы для ноды, не структуры. Так что в коллекции хранятся только ссылки.
Требования по памяти не было.
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 1
uvelichitel
@uvelichitel
habrahabr.ru/users/uvelichitel
  • Фильтр Блума.
  • Бор Ахо-Корасик.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы