#о_большое — Public Fediverse posts

[Перевод] Структуры данных на практике. Глава 1: The Performance Gap

Часть 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/

#оптимизация_кода #микроконтроллеры #кэш_процессора #о_большое

[Перевод] Big O

Нотация Big O ("О" большое) — это способ описания производительности функции без измерения времени ее выполнения. Вместо того, чтобы засекать, сколько секунд выполняется функция от начала до конца, Big O показывает, как меняется время ее выполнения по мере увеличения размера входных данных. Этот подход помогает понять, как программа будет вести себя при разных объемах входящей информации. В этой статье я разберу четыре наиболее часто встречающиеся категории нотации Big O: константную, логарифмическую, линейную и квадратичную. Не переживайте, если эти термины пока ничего вам не говорят — мы подробно рассмотрим каждый из них и наглядно визуализируем в процессе.

https://habr.com/ru/companies/timeweb/articles/942956/

#big_o #о_большое #time_complexity #временная_сложность #алгоритмы #algorithms #timeweb_статьи #timeweb_статьи_перевод #javascript #js