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

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

• Оценка

• Каждый разработчик должен обладать чутьем на проектирование и анализ алгоритмов. По данному предмету Роберт Седжвик написал серию доступных книг ([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. Арендаторы въезжают в дом и с этого времени живут-поживают, лишь иногда обращаясь в домоуправление с просьбой устранить возникшие неисправности.

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

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

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

Переписывание, переработка и перепланирование текста программы описывается общим термином "реорганизация".

Когда осуществлять реорганизацию?

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

• Дублирование. Вы обнаружили нарушение принципа DRY (см. "Пороки дублирования").

• Неортогональность конструкции. Вы обнаружили некий фрагмент программы или конструкцию, которой можно придать большую ортогональность (см. "Ортогональность").

• Устаревшие знания. Все изменяется, требования варьируются, и ваши знания о проблеме расширяются. Программа должна соответствовать новому уровню знаний.

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

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

Итак, вы идете к вашему шефу или заказчику и говорите: "Эта программа работает, но для ее реорганизации мне нужна еще неделя".

Они скажут вам… впрочем, это непечатное выражение.

На жесткие временные рамки часто ссылаются, оправдывая отсутствие реорганизации. Но это оправдание не должно становиться нормой: если вы не сможете провести реорганизацию сейчас, то позже (когда придется принимать во внимание большее число зависимостей) на устранение возникшей проблемы потребуется намного больше времени. А будет ли у вас это время? У нас – точно не будет.