Как учесть эти границы? Нужно знать себя, своих сотрудников, свой бюджет и свою технику. Инженеру-программисту нужно знать пространственно-временную сложность своих структур данных и алгоритмов, архитектуру и показатели производительности своих систем. Ваша задача — создать оптимальное сочетание программного обеспечения и систем.
Пространственная и временная сложность задаются в виде функции О(f(n)), где n равно размеру входных данных. Эта функция определяет асимптотическое поведение памяти или времени для n, стремящегося к бесконечности. Важные классы сложности для f(n) — это ln(n), n, n In(n), ne и en. Как ясно видно из графиков этих функций, когда n растет, O(ln(n)) становится гораздо меньше O(n) и O(n ln(n)), а те, в свою очередь, становятся гораздо меньше O(ne) и O(en). В формулировке Шона Пэрента (Sean Parent): для практически достижимых n все классы сложности близки к функциям констант, линейным либо бесконечным.
Анализ сложности осуществляется в терминах некой абстрактной машины, но программы работают на реальных компьютерах. Современные компьютерные системы образуют целые иерархии физических и виртуальных машин, включающие библиотеки времени выполнения для языков программирования, операционные системы, процессоры, кэш-память, оперативную память, жесткие диски и сети. В приведенной таблице показаны пределы времени произвольного доступа к данным и пределы емкости памяти для типичного сервера, подключенного к сети.
Заметим, что вариативность памяти и скорости составляет несколько порядков. Для компенсации различий на всех уровнях системы интенсивно применяется кэширование и упреждающий просмотр, но они действенны только тогда, когда доступ предсказуем. Если часто происходят кэш-промахи, система будет тормозить. Например, случайное чтение каждого байта на жестком диске может занять 32 года. Даже случайное чтение каждого байта оперативной памяти может занять 11 минут. Случайный доступ непредсказуем. А что предсказуемо? Зависит от системы, но обычно выигрыш приносят повторный доступ к недавно считанным данным и последовательный доступ к элементам данных.
Алгоритмы и структуры данных различаются эффективностью использования кэша. Например:
• Линейный поиск эффективно использует упреждающий просмотр, но требует O(n) сравнений.
• Двоичный поиск в отсортированном массиве требует всего O(log(n)) сравнений.
• Поиск по дереву ван Эмде Боаса (van Emde Boas) имеет сложность O(log(n)) и нечувствителен к кэшу.
Что выбрать? Для окончательного анализа нужны измерения. В таблице ниже показано время поиска в массивах 64-разрядных целых чисел с помощью этих трех методов. На моем компьютере:
• Линейный поиск составляет конкуренцию другим методам на малых массивах, но проигрывает экспоненциально на больших.
• Поиск ван Эмде Боаса побеждает без вариантов благодаря схеме предсказуемого доступа.
Каждый сам решает, что для него лучше.
Знай, что сохранишь в репозиторий
Дэн Берг Джонссон
Я похлопал трех программистов по плечу и поинтересовался, чем они заняты. «Я провожу рефакторинг этих методов», — был ответ первого. «Я добавляю кое-какие параметры в эту веб-операцию», — отвечал второй. Третий сказал: «Я работаю над этим сценарием использования».
Может показаться, что первые двое были поглощены деталями своей работы, и только третий видел картину шире, и его подход лучше. Я поинтересовался, когда и что они собираются поместить в репозиторий, и тут картина резко изменилась. Первые два вполне ясно представляли, какие это будут файлы, и собирались закончить работу примерно в течение часа. Третий сказал: «Предполагаю, что закончу через несколько дней. Наверное, я добавлю некоторые классы и как-то модифицирую службы».
Дело не в том, что два программиста не обладали цельной картиной происходящего. Они просто выбрали задачи, которые, по их мнению, вели в нужном направлении и могли быть выполнены за пару часов. Покончив с этими задачами, они выберут новую функцию или рефакторинг для работы. Таким образом, они писали свой код, исходя из четко обозначенных задач и имея небольшую, но реалистичную цель.