Операция выполнена!
Закрыть
Хабы: Программирование микроконтроллеров, Программирование, Клиентская оптимизация, Процессоры

Миф про O(1)

Говорят, что хэш-таблицы обеспечивают поиск за O(1) — константное время, вне зависимости от размера. В теории они идеальны.

На практике я сталкивался с тем, что производительность хэш-таблиц оказывалась ниже, чем у линейного поиска по массиву.

Я оптимизировал таблицу символов для компилятора. Таблица символов использовала хэш-таблицу с 1024 бакетами, и у нас было примерно 500 символов. Расчёты выглядели отлично: средний размер бакета = 500/1024 ≈ 0,5, поэтому большинство операций поиска должно выполняться за один запрос.

Но профилировщик рассказал иную историю...

Читать далее
Читайте также
НОВОСТИ

ПИШИТЕ

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

info@vsetut.pro