97 Вещей, Которые Должен Знать Каждый Программист
46. Знайте Свои Пределы
Ваши ресурсы ограничены. У вас есть только определённое количество времени и денег, чтобы выполнять свою работу, включая время и деньги, необходимые для обновления ваших знаний, навыков и инструментов. Вы можете работать только с определённым усердием, скоростью и не бесконечно. Ваши инструменты ограничены по мощности. Машины ваших пользователей тем более ограничены по мощности. Таким образом, вы должны знать ограничения своих ресурсов.
Как соблюдать эти ограничения? Знайте свои способности, знайте способности коллег, знайте свой бюджет и знайте свои инструменты. Особенно, как инженер-программист, вы должны знать пространственно-временную сложность ваших структур данных и алгоритмов, а также архитектуру и характеристики производительности ваших систем. Ваша задача - создать оптимальное сочетание программного обеспечения и систем.
Пространственно-временная сложность задается как функция
O(f(n)), которая для n, определяющего объём входных данных, определяет объём затрачиваемых пространства или времени, при росте n. Основные уровни сложности для f(n) включают 1, log(n), n, nlog(n), n^2, 2^n и n!. Как видно из графика этих функций ниже, при росте n: O(log(n)) растёт намного медленнее, чем O(n) или O(nlog(n)), а они - намного медленнее, чем O(n^2) или O(2^n). Как говорит Шон Перент, для доступных значений n можно выделить три класса сложности: константная, линейная и бесконечная.Анализ сложности измеряется в терминах абстрактной машины, но программное обеспечение работает на реальных машинах. Современные компьютерные системы организованы в виде иерархий физических и виртуальных машин, включая языковые среды выполнения, операционные системы, процессоры, кэш-память, оперативную память, диски и сети.
Ёмкость и скорость обращения к различным хранилищам варьируются на несколько порядков. Кэширование и последовательный доступ интенсивно используются на каждом уровне наших систем, чтобы скрыть эту разницу, но они работают только тогда, когда доступ предсказуем. При частых «промахах кэша» система будет тормозить. Например, чтобы в случайном порядке прочитать все байты жесткого диска, может понадобиться 32 года. А чтобы случайно просмотреть всю оперативную память – 11 минут. Случайный доступ непредсказуем. Исходя из этого, следует помнить, что повторный доступ к уже использовавшимся элементам и последовательный доступ практически всегда работают эффективно.
Алгоритмы и структуры данных различаются по тому, насколько эффективно они используют кэш. Например:
- Линейный поиск хорошо использует последовательный доступ, но требует
O(n) сравнений.- Двоичный поиск отсортированного массива требует только
O(log(n)) сравнений.- Поиск по дереву van Emde Boas также требует
O(log(n)) сравнений и при этом эффективно использует кэш.Как выбрать? Только измеряя. Линейный поиск наиболее выгоден для небольших массивов, однако существенно проигрывает при увеличении размера. Алгоритм van Emde Boas выигрывает благодаря предсказуемому доступу к данным.
Источники:
- https://www.oreilly.com/library/view/97-things-every/9780596809515/ Автор оригинала – Greg Colvin
- https://habr.com/ru/post/188010/