Преднамеренное программирование

Мы хотели бы тратить меньше времени на придание нашим программам компактности, как можно раньше перехватывая и устраняя ошибки, возникающие в ходе разработки, а для начала допускать меньшее число ошибок. Этот принцип приносит пользу, если мы способны программировать преднамеренно:

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

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

• Действуйте исходя из плана, неважно, где он составлен – у вас в голове, на кухонной салфетке или на огромной «простыне», полученной с помощью CASE-средств.

• Полагайтесь только на надежные предметы. Не вводите себя в зависимость от случаев или предположений. Если вы не можете понять, в чем состоит различие при специфических обстоятельствах, предполагайте худшее.

• Документируйте ваши предположения. Раздел "Проектирование по контракту" поможет прояснить ваши предположения в вашей же голове, а также передать их другим людям.

• Тестируйте не только вашу программу, но и ваши предположения. Не гадайте, попробуйте осуществить это на деле. Напишите программу контроля для проверки ваших предположений (см. "Программирование утверждений"). Если ваше предположение верно, то вы улучшили документирование вашей программы. Если вы обнаружили, что предположение ошибочно, тогда считайте, что вам повезло.

• Определите приоритеты в своей работе. Уделите время аспектам, представляющим важность; скорее всего, они окажутся непростыми. При отсутствии надлежащих фундаментальных принципов или инфраструктуры все блестящие «бантики» будут просто неуместны.

• Не будьте рабами прошлого. Не позволяйте существующей программе диктовать свою волю той программе, за которой будущее. Если программа устаревает, она может быть полностью заменена. И даже в пределах одной программы не позволяйте уже сделанному сдерживать то, что идет за ним, – будьте готовы к реорганизации (см. "Реорганизация"). Это решение может повлиять на график выполнения проекта. Мы полагаем, что это воздействие будет меньше той цены, которую придется платить за отсутствие изменений [37] .

Поэтому, если в следующий раз что-то начинает работать, но вы не знаете, почему это происходит, убедитесь, что это не является стечением обстоятельств

• Суп из камней и сварившиеся лягушки

• Отладка

• Проектирование по контракту

• Программирование утверждений

• Временное связывание

• Реорганизация

• Все эти сочинения

31. Найдите совпадения в представленном фрагменте программы на языке С. Предположим, что этот фрагмент находится глубоко в недрах библиотечной подпрограммы. (Ответ см. в Приложении В.)

fprintf(stderr, "Error, continue?");

gets(buf);

32. Этот фрагмент программы на языке С мог работать в течение какого-то времени на некоторых машинах. Затем он переставал работать. В чем ошибка? (Ответ см. в Приложении В.)

/* Truncate string to its iast maxlen chars */

void string_tail(char *string, int maxlen) {

  int len = strlen(string);

  if (len > maxlen) {

    strcpy(string, string+(len – maxlen));

  }

}

33. Эта программа входит в состав универсального пакета трассировки Java. Функция записывает строки в файл журнала. Она проходит модульное тестирование, но дает сбой при попытке ее применения одним из разработчиков программ для сети Интернет. На какое стечение обстоятельств полагается эта программа? (Ответ см. в Приложении В.)

public static void debug(String s) throws IOException {

FileWriter fw = new FileWriter("debug.log");

fw.write(s);

fw.flush();

fw.close();

}

32

Скорость алгоритма

В разделе «Оценка» говорилось об оценке того, сколько времени потребуется, чтобы пройти несколько городских кварталов, и сколько времени нужно для завершения проекта. Однако существует и другой вид оценок, который прагматики применяют практически ежедневно: оценка ресурсов, используемых алгоритмами, – времени, работы процессора, объема памяти и т. д.

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

Оказывается, что во многих случаях на подобные вопросы можно ответить, пользуясь здравым смыслом, некоторым анализом и методикой записи приближений, которая называется "О-большое".

Что подразумевается под оценкой алгоритмов?

Большинство нетривиальных алгоритмов обрабатывают некий вид переменных входных массивов, они выполняют сортировку n строк, обращение матрицы размером m*n или расшифровку сообщения с n-битовым ключом. Обычно объем входных данных оказывает влияние на алгоритм: чем больше этот объем, тем больше время выполнения алгоритма или объем используемой памяти.

Если бы эта зависимость всегда была линейной (т. е. время возрастало бы прямо пропорционально значению n), то этот раздел можно было бы и пропустить. Однако наиболее важные алгоритмы не являются линейными. Хорошая новость: многие алгоритмы являются сублинейными. Например, в алгоритме двоичного поиска при нахождении соответствия вовсе не обязательно рассматривать подряд всех кандидатов. А теперь плохая новость: другие алгоритмы отличаются существенно худшими линейными свойствами; время их выполнения или требования к объему памяти возрастают намного быстрее, чем значение n. Если для обработки десяти элементов алгоритму требуется минута, то для обработки ста элементов потребуется целая жизнь.

При написании любых программ, содержащих циклы или рекурсивные вызовы, мы подсознательно проверяем требования, предъявляемые ко времени выполнения и объему памяти. Это редко является формальным процессом, скорее, оперативным подтверждением наличия здравого смысла в том, что мы делаем в определенных обстоятельствах. Но иногда мы оказываемся в ситуации, когда нам приходится проводить более детальный анализ. В этом случае весьма полезной оказывается система обозначений "O()" ("O-большое").

Система обозначений О()

Система O() представляет собой математический способ обозначения приближений. Если мы указываем, что некая программа осуществляет сортировку n записей за время O(n^2), то это просто означает, что максимальное время выполнения программы будет изменяться пропорционально n^2. При удвоении числа записей время возрастет примерно в четыре раза. O() можно рассматривать как порядок величины. Система обозначений O() определяет верхнюю границу величины измеряемого параметра (время, объем памяти, и т. д.). Если мы говорим, что некая функция занимает время O(n^2), то под этим понимается, что верхняя граница интервала времени, необходимого для ее выполнения, возрастает не быстрее n^2. Иногда мы встречаемся с довольно сложными функциями O(), и поскольку именно член высшего порядка будет определять значение с ростом n, то обычно все члены низшего порядка удаляются, чтобы не мешать постоянным коэффициентам умножения. O(n^2/2+Зn) означает то же самое, что и O(n^2/2), которое, в свою очередь, является эквивалентом O(n^2). В этом и состоит недостаток системы обозначений O() – один алгоритм O(n^2) может быть быстрее другого алгоритма O(n^2) в тысячу раз, но из обозначений вы этого не поймете.