#radix_tree — Public Fediverse posts
Live and recent posts from across the Fediverse tagged #radix_tree, aggregated by home.social.
-
[Перевод] Структуры данных на практике. Глава 11: Префиксные деревья и базисные деревья
Кошмар с автозавершением Наше префиксное дерево было в 8 раз медленнее хэш-таблицы. И оно потребляло 128 МБ памяти, в отличие от хэш-таблицы с 24 МБ. Такого не должно было произойти. Префиксные деревья — стандартное решение для автозавершения: поиск за O(k), где k — длина строки вне зависимости от размера датасета. Идеально подходит для сопоставления префиксов. Обычно всегда используется для автозавершения, проверки правописания и таблиц IP-маршрутизации. Мой коллега предложил использовать префиксное дерево для функции автозавершения в нашем инструменте командной строки. Поиск в нём должен был выполняться по 50 тысячам команд и опций. Учебники говорили, что это правильный выбор. Поэтому мы реализовали префиксное дерево. Результаты бенчмарка оказались ужасными: Префиксное дерево было в 8 раз медленнее простой хэш-таблицы. И оно использовало 128 МБ памяти , в то время как хэш-таблица — всего 24 МБ. Где мы ошиблись?