Изучите ограничения

(В оригинале - Know Your Limits)

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

Как же учитывать эти ограничения? Узнайте себя, узнайте своих людей, узнайте бюджет и узнайте все остальное. Будучи программистом, вам особенно важно знать о сложности ваших структур данных и алгоритмов, а также архитектуру и производительность ваших систем. Ваша задача – создать оптимальное сочетание программ с аппаратными системами.

Сложность определяется функцией O(f(n)), являющейся для n, равного размеру входных данных, приближенным значением требуемого объема памяти или времени по мере приближения n к бесконечности. Важные классы сложности включают ln(n), n, n ln(n), ne, and en

Графическое представление наглядно показывает, что по мере роста n O(ln(n)) значительно меньше, чем O(n) и O(n ln(n)), а n в свою очередь значительно меньше O(ne) и O(en). Для доступных значений n можно выделить три класса сложности – константная, линейная и бесконечная.

Анализ сложности делается в терминах абстрактного компьютера, однако программы работают на реальных компьютерах. Современные компьютеры – это иерархия физических и виртуальных машин, включая исполняемые языки, операционные системы, процессоры, кэш, память, диски и сети. В таблице ниже приведены примерные ограничения на скорость доступа и размеры определенных структур.

access time capacity
register < 1 ns 64b
cache line 64B
L1 cache 1 ns 64 KB
L2 cache 4 ns 8 MB
RAM 20 ns 32 GB
disk 10 ms 10 TB
LAN 20 ms > 1 PB
internet 100 ms > 1 ZB

Заметьте, что объемы и быстродействие отличаются на несколько порядков. Кэширование используется практически на всех уровнях, чтобы скрыть эти различия, однако оно работает лишь для предсказуемого доступа. При частых «промахах кэша» система может замедлиться в разы. Например, чтобы в случайном порядке прочитать все байты жесткого диска, может понадобиться 32 года. А чтобы случайно просмотреть всю оперативную память – 11 минут. Случайный доступ непредсказуем. Исходя из этого, следует помнить, что повторный доступ к уже использовавшимся элементам и последовательный доступ практически всегда работают эффективно.

Алгоритмы и структуры данных значительно отличаются по эффективности использования кэша. Например:

  • Линейный поиск выполняет последовательный перебор, но требует O(n) сравнений
  • Бинарный поиск в отсортированном массиве требует лишь O(log(n)) сравнений
  • Поиск по дереву van Emde Boas также требует O(log(n)) сравнений и при этом эффективно использует кэш (cache-oblivious)
Элементы Время поиска (нс)
линейный бинарный vEB
8 50 90 40
64 180 150 70
512 1200 230 100
4096 17000 320 160

И как же сделать выбор? Измеряя. В таблице показано время, требуемое для поиска 64-битного целого числа тремя методами в массивах различного размера. На моем компьютере линейный поиск наиболее выгоден для небольших массивов, однако существенно проигрывает при увеличении размера. Алгоритм van Emde Boas выигрывает всегда благодаря предсказуемому доступу к данным.

Автор оригинала - Greg Colvin

results matching ""

    No results matching ""