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

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

09.01.2026 06:58:02 | Хабр
Хабы: Программирование, Клиентская оптимизация, Процессоры, Программирование микроконтроллеров

Часть I: Основы

«В теории теория и практика одинаковы. На практике это не так». — авторство приписывается разными специалистам по computer science

Загадка

Два часа утра. Я смотрю на совершенно нелогичные данные профилирования.

В процессе работы над загрузчиком для SoC RISC-V у нас возникла проблема с производительностью. Загрузчик должен был искать конфигурации устройств в таблице: примерно пятьсот элементов, каждый с 32-битным ID устройства и указателем на данные конфигурации. Всё просто.

Мой коллега реализовал эту систему с помощью хэш-таблицы. «Поиск за O(1), — сказал он уверенно, — лучше уже некуда».

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

Я попробовал использовать очевидную оптимизацию: заменить хэш-таблицу двоичным поиском по отсортированному массиву. Двоичный поиск занимает O(log n), что теоретически хуже, чем O(1). Так написано в учебниках. Мой преподаватель алгоритмов был бы разочарован.

Но в результате загрузчик оказался на 40% быстрее.

Как O(log n) смогло победить O(1)? Что происходит?

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

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

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

info@vsetut.pro

Copyright © 2026 - vsetut.pro