1
Структуры данных на практике. Глава первая. Разрыв в производительности
Теория алгоритмов утверждает, что константное время поиска всегда предпочтительнее логарифмического. Однако при разработке загрузчика для RISC-V замена хэш-таблицы на двоичный поиск по массиву привела к ускорению работы на 40%. Этот случай наглядно демонстрирует разрыв между академическими моделями и поведением реального железа.
Кэш-промахи и накладные расходы на вычисление хэша часто нивелируют теоретические преимущества сложных структур. На малых объёмах данных архитектура процессора диктует свои правила, делая последовательный доступ более эффективным. Оценим влияние специфики аппаратного обеспечения на выбор алгоритмов.