[Перевод] Структуры данных на практике. Глава 11: Префиксные деревья и базисные деревья

Кошмар с автозавершениемНаше префиксное дерево было в 8 раз медленнее хэш-таблицы. И оно потребляло 128 МБ памяти, в отличие от хэш-таблицы с 24 МБ.Такого не должно было произойти. Префиксные деревья — стандартное решение для автозавершения: поиск за O(k), где k — длина строки вне зависимости от размера датасета. Идеально подходит для сопоставления префиксов. Обычно всегда используется для автозавершения, проверки правописания и таблиц IP-маршрутизации.Мой коллега предложил использовать префиксное дерево для функции автозавершения в нашем инструменте командной строки. Поиск в нём должен был выполняться по 50 тысячам команд и опций. Учебники говорили, что это правильный выбор.Поэтому мы реализовали префиксное дерево. Результаты бенчмарка оказались ужасными:Префиксное дерево было в 8 раз медленнее простой хэш-таблицы. И оно использовало 128 МБ памяти, в то время как хэш-таблица — всего 24 МБ.Где мы ошиблись?