Операция выполнена!
Закрыть
info@vsetut.pro
Стать автором
Вернуться

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

30.03.2026 07:33:49 | Хабр
Хабы: Программирование микроконтроллеров, Программирование, Клиентская оптимизация, Отладка

Кошмар с автозавершением

Наше префиксное дерево было в 8 раз медленнее хэш-таблицы. И оно потребляло 128 МБ памяти, в отличие от хэш-таблицы с 24 МБ.

Такого не должно было произойти. Префиксные деревья — стандартное решение для автозавершения: поиск за O(k), где k — длина строки вне зависимости от размера датасета. Идеально подходит для сопоставления префиксов. Обычно всегда используется для автозавершения, проверки правописания и таблиц IP-маршрутизации.

Мой коллега предложил использовать префиксное дерево для функции автозавершения в нашем инструменте командной строки. Поиск в нём должен был выполняться по 50 тысячам команд и опций. Учебники говорили, что это правильный выбор.

Поэтому мы реализовали префиксное дерево. Результаты бенчмарка оказались ужасными:

Префиксное дерево было в 8 раз медленнее простой хэш-таблицы. И оно использовало 128 МБ памяти, в то время как хэш-таблица — всего 24 МБ.

Где мы ошиблись?

Читать далее
Подробнее
Читайте также
НОВОСТИ

ВСЕ НОВОСТИ
ПИШИТЕ

Техническая поддержка проекта ВсеТут

info@vsetut.pro

Copyright © 2026 - vsetut.pro