97 этюдов для программистов. Опыт ведущих экспертов - Пит Гудлиф
Мы ожидаем, что посетивший нас сантехник умеет пользоваться паяльной лампой. Давайте же потратим немного времени и поучимся более эффективно работать со своими IDE.
Знай свои возможности
Грег Колвин
Нужно знать предел своих возможностей.
«Грязный Гарри»
Ваши ресурсы ограничены. Отведенные на выполнение работы время и деньги определены конкретно, в том числе время и деньги, необходимые для поддержания ваших знаний, навыков и инструментов на современном уровне. Существует предел интенсивности, скорости, изобретательности и длительности для вашей работы. Возможности ваших инструментов ограничены. Мощность машин, для которых вы пишете программы, ограничена. Поэтому вы должны учитывать пределы своих ресурсов.
Как учесть эти границы? Нужно знать себя, своих сотрудников, свой бюджет и свою технику. Инженеру-программисту нужно знать пространственно-временную сложность своих структур данных и алгоритмов, архитектуру и показатели производительности своих систем. Ваша задача — создать оптимальное сочетание программного обеспечения и систем.
Пространственная и временная сложность задаются в виде функции О(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-разрядных целых чисел с помощью этих трех методов. На моем компьютере:
• Линейный поиск составляет конкуренцию другим методам на малых массивах, но проигрывает экспоненциально на больших.
• Поиск ван Эмде Боаса побеждает без вариантов благодаря схеме предсказуемого доступа.
Каждый сам решает, что для него лучше.
— Punch
Знай, что сохранишь в репозиторий
Дэн Берг Джонссон
Я похлопал трех программистов по плечу и поинтересовался, чем они заняты. «Я провожу рефакторинг этих методов», — был ответ первого. «Я добавляю кое-какие параметры в эту веб-операцию», — отвечал второй. Третий сказал: «Я работаю над этим сценарием использования».
Может показаться, что первые двое были поглощены деталями своей работы, и только третий видел картину шире, и его подход лучше. Я поинтересовался, когда и что они собираются поместить в репозиторий, и тут картина резко изменилась. Первые два вполне ясно представляли, какие это будут файлы, и собирались закончить работу примерно в течение часа. Третий сказал: «Предполагаю, что закончу через несколько дней. Наверное, я добавлю некоторые классы и как-то модифицирую службы».
Дело не в том, что два программиста не обладали цельной картиной происходящего. Они просто выбрали задачи, которые, по их мнению, вели в нужном направлении и могли быть выполнены за пару часов. Покончив с этими задачами, они выберут новую функцию или рефакторинг для работы. Таким образом, они писали свой код, исходя из четко обозначенных задач и имея небольшую, но реалистичную цель.
Третий программист оказался неспособен провести декомпозицию задачи и работал сразу по всем направлениям. Он не имел представления о том, во что это выльется, и в принципе занимался рискованной работой в надежде, что в какой-то момент у него появится код для записи в репозиторий. Вероятнее всего, написанный на старте этого долгого предприятия код оказался малопригодным для того решения, которое получилось в итоге.
Как поступили бы первые два программиста, потребуй их задачи более двух часов работы каждая? Поняв, что не рассчитали свои силы, они, скорее всего, отказались бы от внесенных изменений, выбрали задачи помельче и начали все сначала. Продолжай они работу, произошла бы расфокусировка, а в репозиторий попал бы сомнительный код. Лучше отбросить сделанные изменения, но сохранить понимание сути.
Третий программист, возможно, продолжил бы свои гадания и в отчаянии старался бы сшить из своих заплаток код, который можно сохранить в репозиторий. В конце концов, как же можно выбрасывать внесенные изменения — ведь это будет означать, что вы напрасно трудились! К сожалению, если не выбрасывать такой код, в репозиторий попадает слегка странноватый код, не решающий определенную задачу.
Бывают моменты, когда даже программисты, которые ориентированы на частое сохранение кода в репозиторий, не могут найти ничего полезного, с чем бы они могли справиться за пару часов. Тогда они переходят в режим написания ненадежного кода и балуются с кодом, но, конечно, выкидывают свои изменения, когда некое озарение возвращает их на путь истинный. Даже такие бессмысленные, на первый взгляд, периоды работы имеют цель: лучше изучить код, чтобы суметь выявить задачу, решение которой принесет немедленную пользу.
Определите, что сдадите в репозиторий на сей раз. Если не удается завершить задачу, удалите свои изменения и определите новую задачу на основе приобретенного понимания. Займитесь рискованными экспериментами, если это необходимо, но следите за тем, чтобы случайно и незаметно не соскользнуть в режим написания сомнительного кода. Не помещайте
