# [Перевод] Структуры данных на практике. Глава 1: The Performance Gap
BotHabr (tgi,2) → All – 07:35:03 2026-01-09
Опубликовано: Fri, 09 Jan 2026 06:58:02 GMT
Канал: Все статьи подряд / Программирование микроконтроллеров / Хабр
Часть I: Основы«В теории теория и практика одинаковы. На практике это не так». — авторство приписывается разными специалистам по computer scienceЗагадкаДва часа утра. Я смотрю на совершенно нелогичные данные профилирования.В процессе работы над загрузчиком для SoC RISC-V у нас возникла проблема с производительностью. Загрузчик должен был искать конфигурации устройств в таблице: примерно пятьсот элементов, каждый с 32-битным ID устройства и указателем на данные конфигурации. Всё просто.Мой коллега реализовал эту систему с помощью хэш-таблицы. «Поиск за O(1), — сказал он уверенно, — лучше уже некуда».Но загрузчик работал медленно. Недопустимо медленно. Время загрузки должно было находиться в пределах 100 мс, но превышало это значение на три порядка.Я попробовал использовать очевидную оптимизацию: заменить хэш-таблицу двоичным поиском по отсортированному массиву. Двоичный поиск занимает O(log n), что теоретически хуже, чем O(1). Так написано в учебниках. Мой преподаватель алгоритмов был бы разочарован.Но в результате загрузчик оказался на 40% быстрее.Как O(log n) смогло победить O(1)? Что происходит? Читать далее]]>
https://habr.com/ru/articles/982784/
BotHabr (tgi,2) → All – 07:35:03 2026-01-09
Опубликовано: Fri, 09 Jan 2026 06:58:02 GMT
Канал: Все статьи подряд / Программирование микроконтроллеров / Хабр
Часть I: Основы«В теории теория и практика одинаковы. На практике это не так». — авторство приписывается разными специалистам по computer scienceЗагадкаДва часа утра. Я смотрю на совершенно нелогичные данные профилирования.В процессе работы над загрузчиком для SoC RISC-V у нас возникла проблема с производительностью. Загрузчик должен был искать конфигурации устройств в таблице: примерно пятьсот элементов, каждый с 32-битным ID устройства и указателем на данные конфигурации. Всё просто.Мой коллега реализовал эту систему с помощью хэш-таблицы. «Поиск за O(1), — сказал он уверенно, — лучше уже некуда».Но загрузчик работал медленно. Недопустимо медленно. Время загрузки должно было находиться в пределах 100 мс, но превышало это значение на три порядка.Я попробовал использовать очевидную оптимизацию: заменить хэш-таблицу двоичным поиском по отсортированному массиву. Двоичный поиск занимает O(log n), что теоретически хуже, чем O(1). Так написано в учебниках. Мой преподаватель алгоритмов был бы разочарован.Но в результате загрузчик оказался на 40% быстрее.Как O(log n) смогло победить O(1)? Что происходит? Читать далее]]>
https://habr.com/ru/articles/982784/