Страница:
Фред не знает, почему программа сбоит, потому что не знает, почему она работала вначале. Она лишь казалась работающей в условиях ограниченного «тестирования», которое проводил Фред, но это было лишь стечением обстоятельств. Находясь в плену ложной уверенности, Фред впал в забытье. Большинству интеллектуалов знаком этот образ Фреда, но мы знаем его лучше. Мы ведь не полагаемся на стечение обстоятельств, не так ли?
Впрочем, иногда полагаемся. Порой легко спутать счастливый случай с целенаправленным планированием. Рассмотрим несколько примеров.
Предположим, что вы вызываете подпрограмму с неверными данными. Подпрограмма откликается определенным образом, и ваша программа основывается на этом отклике. Но у автора даже и в мыслях не было, что программа будет работать подобным образом, – это даже не рассматривалось. Если подпрограмма «исправляется», то основная программа может нарушиться. В самом крайнем случае вызываемая подпрограмма даже не предназначена для того, чего вы от нее ждете, но вроде бы она работает нормально. Вызов каких-либо элементов неправильным образом или в неверном контексте является связанной проблемой.
paint(g);
invalidate();
validate();
revalidate();
repaint();
paintImmediately(r);
Похоже, что Фред предпринимает отчаянные попытки вывести что-то на экран. Но эти подпрограммы не предназначены для того, чтобы к ним обращались таким способом; хотя они кажутся работающими, в действительности это лишь стечение обстоятельств.
Чтобы не получить новых ударов, когда компонент все-таки нарисован, Фред не пытается вернуться назад и устранить поддельные запросы. "Сейчас она работает, оставим все как есть…".
Подобные размышления могут ввести вас в заблуждение. Зачем рисковать, портить то, что работает? Так можно думать по нескольким причинам:
• Программа действительно может не работать, она может лишь казаться работающей.
• Граничное условие, на которое вы полагаетесь, может быть лишь частным случаем. В различных обстоятельствах (например, при ином экранном разрешении) программа может вести себя по-разному.
• Недокументированное поведение может измениться с выпуском новой версии библиотеки.
• Дополнительные и необязательные вызовы замедляют работу программы.
• Дополнительные вызовы также увеличивают риск привнесения новых дефектов, связанных с этим вызовами.
При написании программы, вызываемой другими разработчиками, полезными могут оказаться базовые принципы четкой модуляризации и скрытия реализации за несложными, четко документированными интерфейсами. Четко определенный контракт (см. "Проектирование по контракту") может устранить недоразумения.
Для вызываемых вами подпрограмм полагайтесь только на документированное поведение. Если по какой-то причине вы не можете сделать этого, то четко документируйте ваше предположение.
На всех уровнях люди работают, держа многие предположения в голове, но они редко документируются и часто вызывают противоречия между разработчиками. Предположения, не основанные на известных фактах, способны отравить любые проекты.
Преднамеренное программирование
32
Что подразумевается под оценкой алгоритмов?
Система обозначений О()
Оценка с точки зрения здравого смысла
Скорость алгоритма на практике
33
Впрочем, иногда полагаемся. Порой легко спутать счастливый случай с целенаправленным планированием. Рассмотрим несколько примеров.
Случайная реализация
Случайная реализация – это то, что происходит просто потому, что программа написана именно так, как она написана. Вы перестаете полагаться на недокументированную ошибку или граничные условия.Предположим, что вы вызываете подпрограмму с неверными данными. Подпрограмма откликается определенным образом, и ваша программа основывается на этом отклике. Но у автора даже и в мыслях не было, что программа будет работать подобным образом, – это даже не рассматривалось. Если подпрограмма «исправляется», то основная программа может нарушиться. В самом крайнем случае вызываемая подпрограмма даже не предназначена для того, чего вы от нее ждете, но вроде бы она работает нормально. Вызов каких-либо элементов неправильным образом или в неверном контексте является связанной проблемой.
paint(g);
invalidate();
validate();
revalidate();
repaint();
paintImmediately(r);
Похоже, что Фред предпринимает отчаянные попытки вывести что-то на экран. Но эти подпрограммы не предназначены для того, чтобы к ним обращались таким способом; хотя они кажутся работающими, в действительности это лишь стечение обстоятельств.
Чтобы не получить новых ударов, когда компонент все-таки нарисован, Фред не пытается вернуться назад и устранить поддельные запросы. "Сейчас она работает, оставим все как есть…".
Подобные размышления могут ввести вас в заблуждение. Зачем рисковать, портить то, что работает? Так можно думать по нескольким причинам:
• Программа действительно может не работать, она может лишь казаться работающей.
• Граничное условие, на которое вы полагаетесь, может быть лишь частным случаем. В различных обстоятельствах (например, при ином экранном разрешении) программа может вести себя по-разному.
• Недокументированное поведение может измениться с выпуском новой версии библиотеки.
• Дополнительные и необязательные вызовы замедляют работу программы.
• Дополнительные вызовы также увеличивают риск привнесения новых дефектов, связанных с этим вызовами.
При написании программы, вызываемой другими разработчиками, полезными могут оказаться базовые принципы четкой модуляризации и скрытия реализации за несложными, четко документированными интерфейсами. Четко определенный контракт (см. "Проектирование по контракту") может устранить недоразумения.
Для вызываемых вами подпрограмм полагайтесь только на документированное поведение. Если по какой-то причине вы не можете сделать этого, то четко документируйте ваше предположение.
Случайный контекст
Вы также можете встретиться со "случайным контекстом". Предположим, вы пишете сервисный модуль. Поскольку в данное время вы пишете программу для графической среды, должен ли модуль полагаться на существующий графический интерфейс? Полагаетесь ли вы на англоязычных пользователей? На грамотных пользователей? Полагаетесь ли вы еще на какой-то контекст, наличие которого не гарантируется?Неявные предположения
Совпадения могут вводить в заблуждение на всех уровнях – от генерации требований до тестирования. Тестирование особенно чревато наличием ложных причинных связей и случайным совпадением результатов. Легко предположить, что А вызывает У, но, как сказано в разделе «Отладка» не предполагайте это, а доказывайте.На всех уровнях люди работают, держа многие предположения в голове, но они редко документируются и часто вызывают противоречия между разработчиками. Предположения, не основанные на известных фактах, способны отравить любые проекты.
Подсказка 44: Не пишите программы в расчете на стечение обстоятельств
Преднамеренное программирование
Мы хотели бы тратить меньше времени на придание нашим программам компактности, как можно раньше перехватывая и устраняя ошибки, возникающие в ходе разработки, а для начала допускать меньшее число ошибок. Этот принцип приносит пользу, если мы способны программировать преднамеренно:
• Всегда отдавайте себе отчет в том, что вы делаете. Программист Фред постепенно терял контроль над происходящим, пока не сварился сам, подобно лягушке из раздела "Суп из камней и сварившиеся лягушки".
• Не пишите программ вслепую. Попытка написать приложение, которое вы до конца не понимаете, или использовать технологию, с которой вы не знакомы, становится поводом к тому, что вы будете введены в заблуждение случайными совпадениями.
• Действуйте исходя из плана, неважно, где он составлен – у вас в голове, на кухонной салфетке или на огромной «простыне», полученной с помощью CASE-средств.
• Полагайтесь только на надежные предметы. Не вводите себя в зависимость от случаев или предположений. Если вы не можете понять, в чем состоит различие при специфических обстоятельствах, предполагайте худшее.
• Документируйте ваши предположения. Раздел "Проектирование по контракту" поможет прояснить ваши предположения в вашей же голове, а также передать их другим людям.
• Тестируйте не только вашу программу, но и ваши предположения. Не гадайте, попробуйте осуществить это на деле. Напишите программу контроля для проверки ваших предположений (см. "Программирование утверждений"). Если ваше предположение верно, то вы улучшили документирование вашей программы. Если вы обнаружили, что предположение ошибочно, тогда считайте, что вам повезло.
• Определите приоритеты в своей работе. Уделите время аспектам, представляющим важность; скорее всего, они окажутся непростыми. При отсутствии надлежащих фундаментальных принципов или инфраструктуры все блестящие «бантики» будут просто неуместны.
• Не будьте рабами прошлого. Не позволяйте существующей программе диктовать свою волю той программе, за которой будущее. Если программа устаревает, она может быть полностью заменена. И даже в пределах одной программы не позволяйте уже сделанному сдерживать то, что идет за ним, – будьте готовы к реорганизации (см. "Реорганизация"). Это решение может повлиять на график выполнения проекта. Мы полагаем, что это воздействие будет меньше той цены, которую придется платить за отсутствие изменений [37].
Поэтому, если в следующий раз что-то начинает работать, но вы не знаете, почему это происходит, убедитесь, что это не является стечением обстоятельств
• Отладка
• Проектирование по контракту
• Программирование утверждений
• Временное связывание
• Реорганизация
• Все эти сочинения
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();
}
• Всегда отдавайте себе отчет в том, что вы делаете. Программист Фред постепенно терял контроль над происходящим, пока не сварился сам, подобно лягушке из раздела "Суп из камней и сварившиеся лягушки".
• Не пишите программ вслепую. Попытка написать приложение, которое вы до конца не понимаете, или использовать технологию, с которой вы не знакомы, становится поводом к тому, что вы будете введены в заблуждение случайными совпадениями.
• Действуйте исходя из плана, неважно, где он составлен – у вас в голове, на кухонной салфетке или на огромной «простыне», полученной с помощью 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 записей? Какая часть программы нуждается в оптимизации?
Оказывается, что во многих случаях на подобные вопросы можно ответить, пользуясь здравым смыслом, некоторым анализом и методикой записи приближений, которая называется "О-большое".
Зачастую этот вид оценки является решающим. Если вы можете сделать что-либо двумя способами, то какой из них стоит выбрать? Если вам известно время выполнения программы при наличии 1000 записей, то как оно изменится при наличии 1000000 записей? Какая часть программы нуждается в оптимизации?
Оказывается, что во многих случаях на подобные вопросы можно ответить, пользуясь здравым смыслом, некоторым анализом и методикой записи приближений, которая называется "О-большое".
Что подразумевается под оценкой алгоритмов?
Большинство нетривиальных алгоритмов обрабатывают некий вид переменных входных массивов, они выполняют сортировку n строк, обращение матрицы размером m*n или расшифровку сообщения с n-битовым ключом. Обычно объем входных данных оказывает влияние на алгоритм: чем больше этот объем, тем больше время выполнения алгоритма или объем используемой памяти.
Если бы эта зависимость всегда была линейной (т. е. время возрастало бы прямо пропорционально значению n), то этот раздел можно было бы и пропустить. Однако наиболее важные алгоритмы не являются линейными. Хорошая новость: многие алгоритмы являются сублинейными. Например, в алгоритме двоичного поиска при нахождении соответствия вовсе не обязательно рассматривать подряд всех кандидатов. А теперь плохая новость: другие алгоритмы отличаются существенно худшими линейными свойствами; время их выполнения или требования к объему памяти возрастают намного быстрее, чем значение n. Если для обработки десяти элементов алгоритму требуется минута, то для обработки ста элементов потребуется целая жизнь.
При написании любых программ, содержащих циклы или рекурсивные вызовы, мы подсознательно проверяем требования, предъявляемые ко времени выполнения и объему памяти. Это редко является формальным процессом, скорее, оперативным подтверждением наличия здравого смысла в том, что мы делаем в определенных обстоятельствах. Но иногда мы оказываемся в ситуации, когда нам приходится проводить более детальный анализ. В этом случае весьма полезной оказывается система обозначений "O()" ("O-большое").
Если бы эта зависимость всегда была линейной (т. е. время возрастало бы прямо пропорционально значению 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) в тысячу раз, но из обозначений вы этого не поймете.
На рисунке 6.1 показано несколько общих обозначений O(), с которым вы можете встретиться, и график, на котором сравнивается время выполнения алгоритмов в каждой категории. Из него ясно, что все начинает быстро выходить из-под контроля, как только мы переходим через O(n^2).
Рис. 6.1. Время выполнения различных алгоритмов
Некоторые универсальные обозначения О-большое
O(1) Постоянная зависимость (обращение к элементу массива, простые операторы)
O(lg(n)) Логарифмическая зависимость (двоичный поиск) [lg(n) – краткое обозначение log2(n)]
O(n) Линейная зависимость (последовательный поиск)
O(n lg(n)) Эта зависимость линейной, но не намного (среднее время быстрой сортировки, пирамидальной сортировки)
O(n^2) Квадратичная зависимость (выборочная сортировка и сортировка включения)
O(n^3) Кубическая зависимость (перемножение двух матриц размером n*n)
O(C^n) Экспоненциальная зависимость (задача о коммивояжере, разбиение набора)
Предположим, что у вас есть программа, обрабатывающая 100 записей за 1 сек. Сколько времени ей потребуется для обработки 1000 записей? Если ваша программа является O(1), то это время остается равным 1 сек. Если она является O(lg(n)), то для обработки потребуется около 3 сек. При O(n) время обработки линейно возрастает до 10 сек., а при O(nlg(n)) составит примерно 33 сек. Если вам не повезло и ваша программа является O(n^2), то можете отдохнуть в течение 100 сек., пока она не сделает свое дело. Ну а в том случае, если вы используете экспоненциальный алгоритм O(2^n), можете заварить чашечку кофе – программа завершит свою работу примерно через 10263 года. В общем, хотелось бы знать, как происходит конец света.
Система обозначений O() не применяется только к временным параметрам; ее можно использовать для представления других ресурсов, требуемых неким алгоритмом. Например, она часто является полезной при моделировании расхода памяти (см. упражнение 35).
На рисунке 6.1 показано несколько общих обозначений O(), с которым вы можете встретиться, и график, на котором сравнивается время выполнения алгоритмов в каждой категории. Из него ясно, что все начинает быстро выходить из-под контроля, как только мы переходим через O(n^2).
Рис. 6.1. Время выполнения различных алгоритмов
Некоторые универсальные обозначения О-большое
O(1) Постоянная зависимость (обращение к элементу массива, простые операторы)
O(lg(n)) Логарифмическая зависимость (двоичный поиск) [lg(n) – краткое обозначение log2(n)]
O(n) Линейная зависимость (последовательный поиск)
O(n lg(n)) Эта зависимость линейной, но не намного (среднее время быстрой сортировки, пирамидальной сортировки)
O(n^2) Квадратичная зависимость (выборочная сортировка и сортировка включения)
O(n^3) Кубическая зависимость (перемножение двух матриц размером n*n)
O(C^n) Экспоненциальная зависимость (задача о коммивояжере, разбиение набора)
Предположим, что у вас есть программа, обрабатывающая 100 записей за 1 сек. Сколько времени ей потребуется для обработки 1000 записей? Если ваша программа является O(1), то это время остается равным 1 сек. Если она является O(lg(n)), то для обработки потребуется около 3 сек. При O(n) время обработки линейно возрастает до 10 сек., а при O(nlg(n)) составит примерно 33 сек. Если вам не повезло и ваша программа является O(n^2), то можете отдохнуть в течение 100 сек., пока она не сделает свое дело. Ну а в том случае, если вы используете экспоненциальный алгоритм O(2^n), можете заварить чашечку кофе – программа завершит свою работу примерно через 10263 года. В общем, хотелось бы знать, как происходит конец света.
Система обозначений O() не применяется только к временным параметрам; ее можно использовать для представления других ресурсов, требуемых неким алгоритмом. Например, она часто является полезной при моделировании расхода памяти (см. упражнение 35).
Оценка с точки зрения здравого смысла
Можно оценить порядок многих базовых алгоритмов с точки зрения здравого смысла.
• Простые циклы.Если простой цикл выполняется от 1 до n, то алгоритм, скорее всего, является O(n) – время находится в линейной зависимости от n. Примерами этого являются исчерпывающий поиск, поиск максимального элемента в массиве и генерация контрольной суммы.
• Вложенные циклы.Если вы помещаете один цикл в другой, то ваш алгоритм становится O(m*n), где m и n – пределы этих двух циклов. Обычно это свойственно простым алгоритмам сортировки, типа пузырьковой сортировки, где внешний цикл поочередно просматривает каждый элемент массива, а внутренний цикл определяет местонахождение этого элемента в результирующем массиве. Подобные алгоритмы сортировки чаще всего стремятся к O(n^2).
• Алгоритм двоичного поиска.Если алгоритм делит пополам набор элементов, который он рассматривает всякий раз в цикле, то скорее всего он логарифмический O(lg(n)) (см. упражнение 37). Двоичный поиск в упорядоченном списке, обход двоичного дерева и поиск первого установленного бита в машинном слове могут быть O(lg(n)).
• Разделяй и властвуй.Алгоритмы, разбивающие входные данные на разделы, работающие независимо с двумя половинами и затем комбинирующие конечный результат, могут представлять собой O(nlg(n)). Классическим примером является алгоритм быстрой сортировки, который делит входной массив пополам и затем проводит рекурсивную сортировку в каждой из половин. Хотя технически он и является O(n^2), поскольку его поведение ухудшается при обработке упорядоченных данных, но среднее время быстрой сортировки составляет O(nlg(n)).
• Комбинаторика.При использовании алгоритмов в решении любых задач, связанных с перестановкой, время их выполнения может выйти из-под контроля.
Это происходит потому, что задачи о перестановке включают вычисления факториалов (существует 5! = 5*4*3*2*1 = 120 перестановок цифр от 1 до 5). Возьмем за основу время выполнения комбинаторного алгоритма для пяти элементов; для шести элементов времени потребуется в шесть раз больше, а для семи – в 42. Примерами этого являются алгоритмы решения многих известных сложных задач – о коммивояжере, об оптимальной упаковке предметов в контейнер, о разделении набора чисел таким образом, что сумма каждого отдельного набора одинакова и т. д. Во многих случаях для сокращения времени выполнения алгоритмов данного типа в определенных прикладных областях используются эвристические подходы.
• Простые циклы.Если простой цикл выполняется от 1 до n, то алгоритм, скорее всего, является O(n) – время находится в линейной зависимости от n. Примерами этого являются исчерпывающий поиск, поиск максимального элемента в массиве и генерация контрольной суммы.
• Вложенные циклы.Если вы помещаете один цикл в другой, то ваш алгоритм становится O(m*n), где m и n – пределы этих двух циклов. Обычно это свойственно простым алгоритмам сортировки, типа пузырьковой сортировки, где внешний цикл поочередно просматривает каждый элемент массива, а внутренний цикл определяет местонахождение этого элемента в результирующем массиве. Подобные алгоритмы сортировки чаще всего стремятся к O(n^2).
• Алгоритм двоичного поиска.Если алгоритм делит пополам набор элементов, который он рассматривает всякий раз в цикле, то скорее всего он логарифмический O(lg(n)) (см. упражнение 37). Двоичный поиск в упорядоченном списке, обход двоичного дерева и поиск первого установленного бита в машинном слове могут быть O(lg(n)).
• Разделяй и властвуй.Алгоритмы, разбивающие входные данные на разделы, работающие независимо с двумя половинами и затем комбинирующие конечный результат, могут представлять собой O(nlg(n)). Классическим примером является алгоритм быстрой сортировки, который делит входной массив пополам и затем проводит рекурсивную сортировку в каждой из половин. Хотя технически он и является O(n^2), поскольку его поведение ухудшается при обработке упорядоченных данных, но среднее время быстрой сортировки составляет O(nlg(n)).
• Комбинаторика.При использовании алгоритмов в решении любых задач, связанных с перестановкой, время их выполнения может выйти из-под контроля.
Это происходит потому, что задачи о перестановке включают вычисления факториалов (существует 5! = 5*4*3*2*1 = 120 перестановок цифр от 1 до 5). Возьмем за основу время выполнения комбинаторного алгоритма для пяти элементов; для шести элементов времени потребуется в шесть раз больше, а для семи – в 42. Примерами этого являются алгоритмы решения многих известных сложных задач – о коммивояжере, об оптимальной упаковке предметов в контейнер, о разделении набора чисел таким образом, что сумма каждого отдельного набора одинакова и т. д. Во многих случаях для сокращения времени выполнения алгоритмов данного типа в определенных прикладных областях используются эвристические подходы.
Скорость алгоритма на практике
Маловероятно, что в своей профессиональной карьере вам придется тратить много времени на написание программ сортировки. Эти программы, входящие в стандартные библиотеки, наверняка без особых усилий превзойдут написанное вами. Но основные типы алгоритмов, описанные выше, будут время от времени всплывать на поверхность. Во всех случаях, когда вы пишете простой цикл, знайте, что имеете дело с алгоритмом О(n). Если же этот цикл содержит внутренний цикл, то речь идет о О(m*n). Вы обязаны задаться вопросом: а насколько велики эти значения? Если эти значения ограничены сверху, то вы можете представить, сколько времени потребуется на выполнение программы. Если эти цифры зависят от внешних факторов (наподобие количества записей в запускаемом на ночь пакете программ или количества фамилий в списке персоналий), то стоит остановиться и изучить влияние больших чисел на время выполнения программы или объемы необходимой памяти.
Существует несколько подходов, которыми вы можете воспользоваться при решении потенциально возникающих проблем. Если есть алгоритм, являющийся O(n^2), попробуйте действовать по принципу "разделяй и властвуй", что может уменьшить время выполнения до O(nlg(n)).
Если вы не уверены в том, что ваша программа будет выполняться в течение определенного времени, или в том, что она затребует определенный объем памяти, попытайтесь запустить ее, варьируя количество обрабатываемых записей или другие параметры, способные оказать воздействие на время выполнения программы. На основе полученных результатов постройте график и получите представление о форме кривой. Изгибается ли она кверху, представляет ли собой прямую линию или сглаживается с увеличением размера входного массива данных? Представление об этом можно получить, исходя из трех или четырех точек.
Стоит рассмотреть и то, что происходит в самой программе. При малых значениях n простой цикл O(n^2) может работать намного лучше, чем сложный О(nlg(n)), особенно если последний содержит ресурсоемкий внутренний цикл.
Говоря о теории, не стоит забывать и о практических соображениях. При работе с небольшими массивами входных данных может показаться, что время выполнения возрастает линейно. Но если программа обрабатывает миллионы записей, то внезапно время выполнения резко увеличивается, по мере того как система начинает «буксовать». При проведении тестирования программы сортировки со случайными входными ключами вы можете удивиться ее работе с упорядоченным входным массивом. Прагматики стараются обеспечивать как теоретическую, так и практическую базу. После всех проведенных оценок единственной определяемой временной характеристикой является скорость выполнения вашей программы в реальных условиях эксплуатации и с реальными данными [38]. Из этого следует следующая подсказка.
Если сложно точно определить время, воспользуйтесь программами оптимизации, чтобы подсчитать, сколько раз выполнялся алгоритм, и постройте зависимость этого количества от размера входного массива данных.
Кроме того, необходимо опасаться преждевременной оптимизации. Перед тем как потратить ваше драгоценное время на улучшение алгоритма, всегда есть смысл убедиться, что он действительно является "узким местом".
• Те, кто интересуется данным предметом более глубоко (по сравнению с его подачей в книге Седжвика), могут прочесть каноническую серию книг Дональда Кнута "Искусство программирования", в которых анализируются разнообразные алгоритмы [Knu97a, Knu97b, Ктш98].
• В упражнении 34 рассматривается сортировка массивов, состоящих из чисел типа "длинное целое". Как скажутся на сортировке усложнение ключей и издержки на их сравнение? Оказывает ли структура ключей влияние на эффективность работы алгоритмов сортировки, словом, является ли самый быстрый алгоритм сортировки таковым во всех случаях?
35. Приведенная ниже подпрограмма выводит на печать содержимое двоичного дерева. Предполагая, что дерево сбалансировано, какой (примерно) объем стека будет использоваться подпрограммой для вывода на печать дерева, состоящего из 1000000 элементов? (Предполагается, что вызовы подпрограммы не оказывают существенной нагрузки на стек). (Ответ см. в Приложении В.)
void printTree(const Node *node) {
char buffer[1000];
if (node) {
printTree(node->left);
getNodeAsString(node, buffer);
puts(buffer);
printTree(node->right);
}
}
36. Существует ли способ уменьшить потребность подпрограммы, описанной в упражнении 35, в ресурсах стека (помимо уменьшения размера буфера)? (Ответ см. в Приложении В.)
37. В разделе "Оценка с точки зрения здравого смысла" утверждается, что алгоритм двоичного поиска является O(lg(n)). Можно ли это доказать? (Ответ см. в Приложении В.)
Подсказка 45: Оцените порядок ваших алгоритмов
Существует несколько подходов, которыми вы можете воспользоваться при решении потенциально возникающих проблем. Если есть алгоритм, являющийся O(n^2), попробуйте действовать по принципу "разделяй и властвуй", что может уменьшить время выполнения до O(nlg(n)).
Если вы не уверены в том, что ваша программа будет выполняться в течение определенного времени, или в том, что она затребует определенный объем памяти, попытайтесь запустить ее, варьируя количество обрабатываемых записей или другие параметры, способные оказать воздействие на время выполнения программы. На основе полученных результатов постройте график и получите представление о форме кривой. Изгибается ли она кверху, представляет ли собой прямую линию или сглаживается с увеличением размера входного массива данных? Представление об этом можно получить, исходя из трех или четырех точек.
Стоит рассмотреть и то, что происходит в самой программе. При малых значениях n простой цикл O(n^2) может работать намного лучше, чем сложный О(nlg(n)), особенно если последний содержит ресурсоемкий внутренний цикл.
Говоря о теории, не стоит забывать и о практических соображениях. При работе с небольшими массивами входных данных может показаться, что время выполнения возрастает линейно. Но если программа обрабатывает миллионы записей, то внезапно время выполнения резко увеличивается, по мере того как система начинает «буксовать». При проведении тестирования программы сортировки со случайными входными ключами вы можете удивиться ее работе с упорядоченным входным массивом. Прагматики стараются обеспечивать как теоретическую, так и практическую базу. После всех проведенных оценок единственной определяемой временной характеристикой является скорость выполнения вашей программы в реальных условиях эксплуатации и с реальными данными [38]. Из этого следует следующая подсказка.
Подсказка 46: Проверяйте ваши оценки
Если сложно точно определить время, воспользуйтесь программами оптимизации, чтобы подсчитать, сколько раз выполнялся алгоритм, и постройте зависимость этого количества от размера входного массива данных.
Лучшее – враг хорошего
При выборе подходящего алгоритма также необходимо придерживаться прагматического подхода – самые быстрые алгоритмы не обязательно являются наилучшими для конкретного случая. При небольшом входном массиве «прямолинейная» сортировка со вставкой будет работать так же хорошо, как и алгоритм быстрой сортировки, и потребует меньше времени на написание и отладку. Необходимо соблюдать осторожность, если выбранный вами алгоритм отличается высокими затратами на установку. При работе с небольшими массивами эта дорогостоящая установка может свести на нет преимущество в скорости выполнения и сделать алгоритм нерентабельным.Кроме того, необходимо опасаться преждевременной оптимизации. Перед тем как потратить ваше драгоценное время на улучшение алгоритма, всегда есть смысл убедиться, что он действительно является "узким местом".
Другие разделы, относящиеся к данной теме:
• ОценкаВопросы для обсуждения
• Каждый разработчик должен обладать чутьем на проектирование и анализ алгоритмов. По данному предмету Роберт Седжвик написал серию доступных книг ([Sed83, SF96, Sed92]и др.). Мы рекомендуем пополнить вашу библиотеку одной из этих книг и обязательно прочесть ее.• Те, кто интересуется данным предметом более глубоко (по сравнению с его подачей в книге Седжвика), могут прочесть каноническую серию книг Дональда Кнута "Искусство программирования", в которых анализируются разнообразные алгоритмы [Knu97a, Knu97b, Ктш98].
• В упражнении 34 рассматривается сортировка массивов, состоящих из чисел типа "длинное целое". Как скажутся на сортировке усложнение ключей и издержки на их сравнение? Оказывает ли структура ключей влияние на эффективность работы алгоритмов сортировки, словом, является ли самый быстрый алгоритм сортировки таковым во всех случаях?
Упражнения
34. Авторы книги составили набор простых программ сортировки, которые можно загрузить с их Интернет-сайта (www.pragmaticprogrammer.com). Прогоните эти программы на разных компьютерах, имеющихся в вашем распоряжении. Соответствуют ли полученные вами данные ожидаемым кривым? Какие заключения можно сделать об относительных скоростях ваших машин? Каково влияние различных установочных параметров компиляторов? Является ли поразрядная сортировка действительно линейной? (Ответ см. в Приложении В.)35. Приведенная ниже подпрограмма выводит на печать содержимое двоичного дерева. Предполагая, что дерево сбалансировано, какой (примерно) объем стека будет использоваться подпрограммой для вывода на печать дерева, состоящего из 1000000 элементов? (Предполагается, что вызовы подпрограммы не оказывают существенной нагрузки на стек). (Ответ см. в Приложении В.)
void printTree(const Node *node) {
char buffer[1000];
if (node) {
printTree(node->left);
getNodeAsString(node, buffer);
puts(buffer);
printTree(node->right);
}
}
36. Существует ли способ уменьшить потребность подпрограммы, описанной в упражнении 35, в ресурсах стека (помимо уменьшения размера буфера)? (Ответ см. в Приложении В.)
37. В разделе "Оценка с точки зрения здравого смысла" утверждается, что алгоритм двоичного поиска является O(lg(n)). Можно ли это доказать? (Ответ см. в Приложении В.)
33
Реорганизация
Как изменилось и увяло все, что окружает меня…
Г.Ф. Лайт, Пребудь со мной
По мере развития программы возникает необходимость в переосмыслении ранее принятых решений и переработки отдельных фрагментов текста программы. Этот процесс абсолютно естественен. Программа нуждается в эволюции, она не является статическим объектом.
К сожалению, наиболее распространенной метафорой разработки программного обеспечения является строительство здания (Б. Мейер [Меу97Ь] использует термин "Software Construction" – букв.: строительство программ – Прим. пер.). Но использование термина «строительство» в качестве определяющей метафоры подразумевает наличие следующих стадий:
1. Архитектор готовит чертежи на кальке.
2. Фирмы-подрядчики роют котлован под фундамент, возводят наземную часть, проводят электричество, монтируют водопровод и канализацию и осуществляют отделочные работы.
3. Арендаторы въезжают в дом и с этого времени живут-поживают, лишь иногда обращаясь в домоуправление с просьбой устранить возникшие неисправности.
Программное обеспечение работает несколько по-иному. В отличие от строительства, написание программ ближе к садоводству, оно ближе к живой природе, чем к бетонным конструкциям. Вы высаживаете в саду множество растений согласно первоначальному плану и условиям. Некоторые растения разрастаются, другим же уготована компостная яма. Вы можете пересаживать растения друг относительно друга, чтобы извлечь пользу из взаимодействия света и тени, ветра и дождя. Переросшие растения разрубают или обрезают, растения определенного цвета пересаживают на другие участки, где они становятся более приятными глазу с точки зрения эстетики. Вы выпалываете сорняки и подкармливаете растения, которые нуждаются в дополнительном питании. Вы постоянно следите за состоянием сада и при необходимости вносите изменения (в почву, растения, общий план).
Для бизнесменов понятнее метафора строительства здания, она более научна по сравнению с садоводством, она воспроизводима, в управлении есть жесткая иерархия подотчетности и т. д. Но мы не занимаемся строительством небоскребов – можем выйти за рамки физики и реального мира.
К сожалению, наиболее распространенной метафорой разработки программного обеспечения является строительство здания (Б. Мейер [Меу97Ь] использует термин "Software Construction" – букв.: строительство программ – Прим. пер.). Но использование термина «строительство» в качестве определяющей метафоры подразумевает наличие следующих стадий:
1. Архитектор готовит чертежи на кальке.
2. Фирмы-подрядчики роют котлован под фундамент, возводят наземную часть, проводят электричество, монтируют водопровод и канализацию и осуществляют отделочные работы.
3. Арендаторы въезжают в дом и с этого времени живут-поживают, лишь иногда обращаясь в домоуправление с просьбой устранить возникшие неисправности.
Программное обеспечение работает несколько по-иному. В отличие от строительства, написание программ ближе к садоводству, оно ближе к живой природе, чем к бетонным конструкциям. Вы высаживаете в саду множество растений согласно первоначальному плану и условиям. Некоторые растения разрастаются, другим же уготована компостная яма. Вы можете пересаживать растения друг относительно друга, чтобы извлечь пользу из взаимодействия света и тени, ветра и дождя. Переросшие растения разрубают или обрезают, растения определенного цвета пересаживают на другие участки, где они становятся более приятными глазу с точки зрения эстетики. Вы выпалываете сорняки и подкармливаете растения, которые нуждаются в дополнительном питании. Вы постоянно следите за состоянием сада и при необходимости вносите изменения (в почву, растения, общий план).
Для бизнесменов понятнее метафора строительства здания, она более научна по сравнению с садоводством, она воспроизводима, в управлении есть жесткая иерархия подотчетности и т. д. Но мы не занимаемся строительством небоскребов – можем выйти за рамки физики и реального мира.