97 этюдов для программистов. Опыт ведущих экспертов

Знай свои возможности Грег Колвин

Ваши ресурсы ограничены. Отведенные на выполнение работы время и деньги определены конкретно, в том числе время и деньги, необходимые для поддержания ваших знаний, навыков и инструментов на современном уровне. Существует предел интенсивности, скорости, изобретательности и длительности для вашей работы. Возможности ваших инструментов ограничены. Мощность машин, для которых вы пишете программы, ограничена. Поэтому вы должны учитывать пределы своих ресурсов.

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

Пространственная и временная сложность задаются в виде функции О(f(n)), где n равно размеру входных данных. Эта функция определяет асимптотическое поведение памяти или времени для n, стремящегося к бесконечности. Важные классы сложности для f(n) — это ln(n), n, n In(n), ne и eⁿ. Как ясно видно из графиков этих функций, когда n растет, O(ln(n)) становится гораздо меньше O(n) и O(n ln(n)), а те, в свою очередь, становятся гораздо меньше O(n^e) и O(eⁿ). В формулировке Шона Пэрента (Sean Parent): для практически достижимых n все классы сложности близки к функциям констант, линейным либо бесконечным.

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

Заметим, что вариативность памяти и скорости составляет несколько порядков. Для компенсации различий на всех уровнях системы интенсивно применяется кэширование и упреждающий просмотр, но они действенны только тогда, когда доступ предсказуем. Если часто происходят кэш-промахи, система будет тормозить. Например, случайное чтение каждого байта на жестком диске может занять 32 года. Даже случайное чтение каждого байта оперативной памяти может занять 11 минут. Случайный доступ непредсказуем. А что предсказуемо? Зависит от системы, но обычно выигрыш приносят повторный доступ к недавно считанным данным и последовательный доступ к элементам данных.

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

• Линейный поиск эффективно использует упреждающий просмотр, но требует O(n) сравнений.

• Двоичный поиск в отсортированном массиве требует всего O(log(n)) сравнений.

• Поиск по дереву ван Эмде Боаса (van Emde Boas) имеет сложность O(log(n)) и нечувствителен к кэшу.

Что выбрать? Для окончательного анализа нужны измерения. В таблице ниже показано время поиска в массивах 64-разрядных целых чисел с помощью этих трех методов. На моем компьютере:

• Линейный поиск составляет конкуренцию другим методам на малых массивах, но проигрывает экспоненциально на больших.

• Поиск ван Эмде Боаса побеждает без вариантов благодаря схеме предсказуемого доступа.