• 31 Программирование в расчете на стечение обстоятельств
  • Как программировать в расчете на стечение обстоятельств
  • Преднамеренное программирование
  • 32 Скорость алгоритма
  • Что подразумевается под оценкой алгоритмов?
  • Система обозначений О()
  • Оценка с точки зрения здравого смысла
  • Скорость алгоритма на практике
  • 33 Реорганизация
  • Когда осуществлять реорганизацию?
  • Как производится реорганизация?
  • 34 Программа, которую легко тестировать
  • Модульное тестирование
  • Тестирование в рамках контракта
  • Создание модульных тестов
  • Применение тестовых стендов
  • Построение тестового окна
  • Культура тестирования
  • 35 Злые волшебники
  • Глава 6

    Пока вы пишете программу

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

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

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

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

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

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

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

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

    31

    Программирование в расчете на стечение обстоятельств

    Случалось ли вам когда-нибудь смотреть старые черно-белые фильмы о войне? Усталый солдат осторожно выбирается из зарослей кустарника. Впереди него свободное пространство, и солдат задается вопросом: есть ли впереди мины или можно безбоязненно идти дальше? Ничто не говорит о том, что впереди минное поле, – нет ни знаков, ни колючей проволоки, ни воронок. Солдат пробует штыком грунт впереди себя и вздрагивает в ожидании взрыва. Но ничего не происходит. Какое-то время он продолжает осторожно продвигаться но полю, прощупывая грунт. В конце концов, убедившись, что проход безопасен, он распрямляется и начинает гордо маршировать вперед… навстречу смерти.

    Первые поиски мин, проведенные солдатом, были безрезультатны, но ему просто повезло. Он пришел к ложному заключению, которое закончилось катастрофой.

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

    Как программировать в расчете на стечение обстоятельств

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

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

    Впрочем, иногда полагаемся. Порой легко спутать счастливый случай с целенаправленным планированием. Рассмотрим несколько примеров.

    Случайная реализация

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

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

    paint(g);

    invalidate();

    validate();

    revalidate();

    repaint();

    paintImmediately(r);

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

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

    Подобные размышления могут ввести вас в заблуждение. Зачем рисковать, портить то, что работает? Так можно думать по нескольким причинам:

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

    • Граничное условие, на которое вы полагаетесь, может быть лишь частным случаем. В различных обстоятельствах (например, при ином экранном разрешении) программа может вести себя по-разному.

    • Недокументированное поведение может измениться с выпуском новой версии библиотеки.

    • Дополнительные и необязательные вызовы замедляют работу программы.

    • Дополнительные вызовы также увеличивают риск привнесения новых дефектов, связанных с этим вызовами.

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

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

    Случайный контекст

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

    Неявные предположения

    Совпадения могут вводить в заблуждение на всех уровнях – от генерации требований до тестирования. Тестирование особенно чревато наличием ложных причинных связей и случайным совпадением результатов. Легко предположить, что А вызывает У, но, как сказано в разделе «Отладка» не предполагайте это, а доказывайте.

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


    Подсказка 44: Не пишите программы в расчете на стечение обстоятельств


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

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

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

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

    • Действуйте исходя из плана, неважно, где он составлен – у вас в голове, на кухонной салфетке или на огромной «простыне», полученной с помощью 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) в тысячу раз, но из обозначений вы этого не поймете.

    На рисунке 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. Примерами этого являются алгоритмы решения многих известных сложных задач – о коммивояжере, об оптимальной упаковке предметов в контейнер, о разделении набора чисел таким образом, что сумма каждого отдельного набора одинакова и т. д. Во многих случаях для сокращения времени выполнения алгоритмов данного типа в определенных прикладных областях используются эвристические подходы.

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

    Маловероятно, что в своей профессиональной карьере вам придется тратить много времени на написание программ сортировки. Эти программы, входящие в стандартные библиотеки, наверняка без особых усилий превзойдут написанное вами. Но основные типы алгоритмов, описанные выше, будут время от времени всплывать на поверхность. Во всех случаях, когда вы пишете простой цикл, знайте, что имеете дело с алгоритмом О(n). Если же этот цикл содержит внутренний цикл, то речь идет о О(m*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. Арендаторы въезжают в дом и с этого времени живут-поживают, лишь иногда обращаясь в домоуправление с просьбой устранить возникшие неисправности.

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

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

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

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

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

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

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

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

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

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

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

    Осложнения в реальном мире

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

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

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

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


    Подсказка 47: Реорганизация должна проводиться часто и как можно раньше


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

    Как производится реорганизация?

    Реорганизация появилась в среде программистов, работающих с языком Smalltalk, и начала, вкупе с другими модными поветриями (например, шаблоны конструкций), завоевывать все более широкую аудиторию. Но это еще малоизвестная тема, по ней опубликовано не так много работ. Первая большая монография о реорганизации ([FBB+99], а также [URL 47]) вышла одновременно с данной книгой.

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

    Ясно, что реорганизация представляет собой род деятельности, которая должна осуществляться медленно, преднамеренно и осторожно. Мартин Фаулер предлагает ряд простых подсказок – как провести реорганизацию, чтобы это не принесло больше вреда, чем пользы (см. врезку на стр. 30 в книге [FS97]):

    1. Не пытайтесь одновременно производить реорганизацию и добавлять функциональные возможности.

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

    Автоматическая реорганизация

    Исторически сложилось так, что пользователи Smalltalk всегда применяли средство просмотра классов как неотъемлемую часть интегрированной среды разработчика. В отличие от web-браузеров, средства просмотра классов позволяют пользователям перемещаться по иерархиям и методам класса и проверять их.

    Обычно средства просмотра классов позволяют редактировать текст программы, создавать новые методы, классы и т. д. Следующей вариацией на эту тему является браузер реорганизации.

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

    Во время написания данной книги этой технологии еще предстояло выйти за пределы мира Smalltalk, но скорее всего она начнет меняться с той же скоростью, что и язык Java, – быстро. В то же время исторический браузер реорганизации Smalltalk можно отыскать в Интернете [URL 20].


    3. Двигайтесь обдуманно и не спеша: переместите поле из одного класса в другой, объедините два подобных метода в суперкласс. Часто при реорганизации вносится много локальных изменений, которые приводят к серьезным сдвигам. Если вы двигаетесь без спешки и проводите тестирование после каждого шага, вы избежите длительной процедуры отладки.

    На данном уровне тестирование будет обсуждаться в разделе "Программа, которую легко тестировать", тестирование на более высоком уровне – в разделе "Безжалостное тестирование"), но мнение г-на Фаулера о тщательном регрессионном тестировании является ключом к надежной реорганизации.

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

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

    Другие разделы, относящиеся к данной теме:

    • Мой исходный текст съел кот Мурзик

    • Энтропия в программах

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

    • Пороки дублирования

    • Ортогональность

    • Программирование в расчете на стечение обстоятельств

    • Программа, которую легко тестировать

    • Безжалостное тестирование

    Упражнения

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

    if (state==TEXAS) {

    rate=TX.RATE;

    amt=base * TX_RATE;

    calc=2*basis(amt) + extra(amt)*1.05;

    }

    else if ((state==OHIO) || (state==MAINE)) {

    rate=(state==OHIO) ? OH_RATE : MN_RATE;

    amt=base*rate;

    calc=2*basis(amt) + extra(amt)*1.05;

    if (state==OHIO)

       points = 2;

    }

    else {

    rate=1;

    amt=base;

    calc=2*basis(amt) + extra(amt)*1.05;

    }


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

    public class Shape {

    public static final int SQUARE = 1;

    public static final int CIRCLE = 2;

    public static final int RIGHTTRIANGLE = 3;

    private int shapeType;

    private double size;

    public Shape(int shapeType, double size) {

       this.shapeType = shapeType;

       this.size = size;

    }

    //… другие методы…

    public double area() {

     switch (shapeType) {

      case SQUARE: return size*size;

      case CIRCLE: return Math.PI*size*size/4.0;

      case RIGHT TRIANGLE: return size*size/2.0;

    }

    return 0;

    }

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


    public class Window {

      public Window(int width, int height) {…}

      public void setSize(int width, int height) {…}

      public boolean overiaps(Window w) {…}

      public int getArea() {…}

    34

    Программа, которую легко тестировать

    Термин "программная интегральная схема" является метафорой, брошенной в ходе дискуссии о многократном использовании и компонентно-ориентированной разработке [39]. Идея заключается в том, что программные компоненты должны объединяться так же, как это происходит с чипами интегральной схемы. Этот подход срабатывает только в том случае, если известно, что используемые компоненты надежны.

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

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

    Модульное тестирование

    Тестирование аппаратных средств на уровне чипа отдаленно напоминает модульное тестирование программного обеспечения – тестируется каждый модуль по отдельности для проверки его поведения. Мы можем лучше представить себе, какова будет реакция модуля на внешний мир, если проведем его тщательное тестирование в контролируемых (и даже искусственных) условиях.

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

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

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

    Тестирование в рамках контракта

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

    Что это означает на практике? Рассмотрим подпрограмму извлечения квадратного корня, с которой мы впервые встретились в разделе "ППК и аварийное завершение работы программы". Ее контракт довольно прост:

    require:

       argument >=0

    ensure:

      abs((result*result)–argument) < epsilon

    Он указывает на моменты, нуждающиеся в проверке:

    • Передать отрицательный аргумент и удостовериться в том, что он отклонен

    • Передать аргумент, равный нулю, и удостовериться в том, что он принят (это граничное значение)

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

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

    public void testValue(double num, double expected) {

    double result = 0.0;

    try {    // We may throw a

    result = mySqrt(num); // precondition exception

    }

    catch (Throwable e) {

    if (num<0.0) // If input is «0, then

       Return; // we're expecting the

    Else // exception, otherwise

       Assert(false); // force a test failure

    }

    assert(Math.abs(expected-result)<epsilon);

    }

    Затем мы можем вызвать эту подпрограмму, чтобы проверить нашу функцию излечения квадратного корня:

    TestValue(-4.0, 0.0);

    TestValue(0.0, 0.0);

    TestValue(2.0, 1.4142135624);

    TestValue(64.0, 8.0);

    TestValue(1.0e7, 3162.2776602);

    Это весьма простая процедура тестирования; в реальном мире любой нетривиальный модуль скорее всего будет зависеть от ряда других модулей, поэтому, может быть, есть смысл протестировать их сочетание?

    Предположим, есть модуль А, использующий модули LinkedList и Sort. Мы осуществляем тестирование в следующем порядке:

    1. Полностью тестируем контракт модуля LinkedList.

    2. Полностью тестируем контракт модуля Sort.

    3. Тестируем контракт модуля А, который полагается на другие контракты, но не раскрывает их напрямую.

    При этом способе тестирования вы вначале обязаны проводить тестирование подкомпонентов.

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

    Зачем вся эта головная боль? Прежде всего, хотелось бы избежать создания "бомбы замедленного действия", той, что остается незамеченной и позже взрывается в самый неподходящий момент во время работы над проектом. Подчеркивая важность "тестирования в рамках контракта", мы пытаемся, насколько это возможно, избежать катастроф, возникающих в будущем.


    Подсказка 48: Проектируйте с учетом тестирования


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

    Создание модульных тестов

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

    Делая тестовую процедуру доступной, вы наделяете разработчиков, которые могут воспользоваться вашей программой, двумя бесценными ресурсами:

    1. Примерами того, как использовать все функциональные возможности вашего модуля

    2. Средствами построения процедур регрессионного тестирования для проверки правильности любых изменений, которые будут вноситься в программу впоследствии

    Если каждый класс или модуль содержит свой собственный модульный тест, это удобно, но не всегда практично. Например, в языке Java каждый класс содержит собственную подпрограмму main. За исключением файла основного класса приложения, подпрограмма main может использоваться для запуска модульных тестов; она будет игнорироваться во время работы самого приложения. Преимущество состоит в том, что программа, отправляемая заказчику, все еще содержит тесты, которые могут использоваться для диагностики проблем, возникающих "в боевой обстановке".

    При работе с языком С++ вы можете добиться того же эффекта (во время компиляции) используя конструкцию #ifdef для выборочной компиляции программы модульного теста. Ниже представлен очень простой модульный тест на языке С++, внедренный в наш модуль и проверяющий работу функции извлечения квадратного корня с помощью подпрограммы testValue, подобной программе на языке Java, реализованной ранее:

    #ifdef _TEST_

    int main(int argc, char **argv) {

    argc-; argv++; // пропускаем имя программы

     if (argc<2) {   // стандартные тесты, если аргументы не указаны

       TestValue(-4.0, 0.0);

       TestValue(0.0, 0.0);

       TestValue(2.0, 1.4142135624);

       TestValue(64.0, 8.0);

       TestValue(1.0e7, 3162.2776602);

    }

    else {   // в этом случае используем аргументы

      double num, expected;

      while (argc>= 2) {

      num = atof(argv[0]);

      expected = atof(argv[1]);

      testValue(num.expected);

      argc – = 2;

      argv += 2;

     }

    }

    return 0;

    }

    #endif

    Данный модульный тест запускает минимальный набор тестов или же (при наличии аргументов) позволяет использовать внешние данные. Эта возможность могла быть задействована в сценарии запуска более полного набора тестов.

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

    Но разработки одних модульных тестов недостаточно. Вы обязаны выполнять их и выполнять часто. Это также полезно, если класс время от времени проходит процедуру тестирования.

    Применение тестовых стендов

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

    Тестовый стенд может осуществлять универсальные операции, такие как регистрация состояния системы, анализ выходных данных на наличие ожидаемых результатов, а также выбор и запуск конкретных процедур тестирования. Стенды могут управляться при помощи графического интерфейса, могут быть написаны на том же целевом языке, что и весь проект, или реализованы в виде сочетания сборочных файлов и сценариев на языке Perl. Простой тестовый стенд описан в ответе к упражнению 41 (см. Приложение В).

    При работе с объектно-ориентированными языками и средами можно создать базовый класс, содержащий универсальные операции. Отдельные тесты могут создать подкласс и добавить специфические процедуры тестирования. Можно использовать стандартное соглашение об именовании и отражение на языке Java для формирования списка процедур тестирования в автоматическом режиме. Эта методика является прекрасным способом соблюдать принцип DRY – вам не приходится следить за списком доступных тестов. Но перед тем как взлететь и начать писать свой собственный стенд, есть смысл изучить методику xUnit Кента Бека и Эриха Гаммы [URL 22]. Они уже проделали всю сложную подготовительную работу.

    Вне зависимости от выбранной вами технологии тестовый стенд обязан предоставлять следующие возможности:

    • Стандартный способ определения установочной процедуры и завершения работы

    • Метод выбора отдельных тестов или всех доступных тестов

    • Средства анализа выходных данных на наличие ожидаемых (или неожиданных) результатов

    • Стандартизированная форма отчета об обнаруженных неисправностях

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

    Специальное тестирование

    Во время отладки можно прекратить создание определенных тестов "на лету". Это может быть таким же простым делом, как оператор print или ввод фрагмента программы в интерактивной оболочке отладчика или ИСР.

    В конце сеанса отладки необходимо формализовать процедуру специального тестирования. Если программа прервалась один раз, скорее всего она прервется снова. Не стоит просто отбрасывать в сторону созданную процедуру тестирования; добавьте ее к существующему модульному тесту.


    Например, при помощи JUnit (элемент Java из семейства xUnit) можно записать процедуру проверки извлечения квадратного корня следующим образом:

    public class JUnitExample extends TestCase {

    public JUnitExampleffinal String name) {

      super(name);

    }

    protected void setUpQ {

    // Load up test data…

    testData.addElement(new dblPair(-4.0,0.0));

    testData.addElement(new dblPair(0.0,0.0));

    testData.addElement(new dblPair(64.0,8.0));

    testData.addElement(new dblPair(Double.MAX_VALUE, 1.3407807929942597E154));

    }

    public void testMySqrt() {

    double num, expected, result = 0.0;

    Enumeration enum = testData.elements();

    while (enum.hasMoreElements()) {

    dblPair p = (dblPair)enum.nextElement();

    num = p.getNum();

    expected = p.getExpected();

    testValue(num, expected);

    }

    }

    public static Test suite() {

    TestSuite suite= new TestSuite();

    suite.addTest(new JUnitExample("testMySqrt"));

    return suite;

    }

    }

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

    Построение тестового окна

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

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

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

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

    Для более крупных программ, работающих на серверах, существует изящная технология, заключающаяся в том, что для слежения за ходом работы используется встроенный web-сервер. Можно привязать web-браузер к HTTP-порту приложения

    (который обычно имеет нестандартный номер типа 8080) и увидеть внутреннее состояние, журналы и даже нечто вроде панели управления отладкой. Реализация этого может показаться сложным делом, что не соответствует действительности это. Бесплатно внедряемые web-серверы с протоколом HTTP реализованы на различных современных языках программирования. Поиск можно начать с сайта [URL 58].

    Культура тестирования

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

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

    % make test

    В этом отношении сам по себе Perl не является чем-то сверхъестественным. Perl облегчает сопоставление и анализ результатов тестирования для обеспечения соответствия, но его большое преимущество состоит в том, что он является стандартом – тестирование проводится в конкретном месте и имеет предсказуемый результат. Тестирование в большей степени является вопросом культуры, а не техники, независимо от используемого вами языка.


    Подсказка 49: Тестируйте ваши программы, в противном случае это сделают ваши пользователи


    Другие разделы, относящиеся к данной теме:

    • Мой исходный текст съел кот Мурзик

    • Ортогональность

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

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

    • Безжалостное тестирование

    Упражнения

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

    35

    Злые волшебники

    Никто не может отрицать – создавать приложения становится все сложнее и сложнее. В частности, пользовательские интерфейсы становятся все более утонченными. Двадцать лет назад приложение среднего масштаба обошлось бы интерфейсом "стеклянного телетайпа" (а может быть, интерфейса не было бы и вовсе). Асинхронные терминалы обеспечивали интерактивное отображение символов, а устройства ввода (наподобие вездесущей IBM 3270) позволяли набирать целую экранную страницу перед нажатием клавиши SEND. Теперь пользователи требуют графический интерфейс с контекстно-зависимой справкой, средствами типа "вырезать и вставить", "перетащить и отпустить", средством OLE, много- или однодокументным интерфейсом. Пользователям потребна интеграция с web-браузером и поддержка архитектуры с тонким клиентом.

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

    Кажется, мы не сказали о том, что нам это было нужно на прошлой неделе – вес и сразу!

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

    Поэтому производители инструментальных средств и поставщики средств инфраструктуры придумали палочку выручалочку – функцию-мастера. Это замечательное средство. Вам нужно приложение с многодокументным интерфейсом и поддержкой контейнера OLE? Один щелчок мыши, ответ на пару простых вопросов – и функция-мастер автоматически сгенерирует для вас скелет программы. При выполнении данного сценария среда Microsoft Visual С++ автоматически создает программу, содержащую свыше 1200 строк. Функции-мастера хорошо справляются и с другими заданиями. Вы можете воспользоваться мастерами при создании серверных компонентов, реализации Java beans, работе с сетевыми интерфейсами – все это достаточно сложные области, где не обойтись без помощи эксперта.

    Но применение функции-мастера, спроектированной неким компьютерным гуру, не делает автоматически из разработчика Джо компьютерного эксперта. Джо чувствует себя недурно – он ведь сгенерировал большое количество исходного текста и довольно элегантную на вид программу. Ему нужно лишь добавить функциональную возможность, характерную для данного приложения, и программу можно отправлять заказчику. Но покуда Джо реально не осознает сути программы, сгенерированной от его имени, он вводит самого себя в заблуждение. Он программирует в расчете на стечение обстоятельств. Функция-мастер подобна улице с односторонним движением – она лишь «вырезает» программу и затем движется далее. Если сгенерированная программа не совсем правильна (или обстоятельства изменились), а вам необходимо адаптировать ее, вы остаетесь с ней один на один.

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


    Подсказка 50: Не пользуйтесь программой функции-мастера, которую не понимаете


    Некоторые полагают, что это совсем уж экстремистская позиция. Они говорят, что разработчики всегда основывают свою работу на предметах, которые до конца им непонятны, – на квантовой механике в интегральных схемах, схеме прерываний в процессоре, алгоритмах, используемых при диспетчеризации процессов, программах из имеющихся библиотек и т. д. Мы согласны. И мы придерживались бы того же мнения о функциях-мастерах, если бы они представляли собой просто набор библиотечных вызовов или стандартные службы операционной системы, на которые могли положиться разработчики. Но это не так. Функции-мастера генерируют программу, которая становится неотъемлемой частью приложения, написанного разработчиком Джо. Сгенерированная программа не выносится за скобки, прячась за опрятным интерфейсом, она переплетена, строчка за строчкой, с теми функциональными возможностями, которые созданы самим Джо [40]. В конечном итоге она перестает быть программой функции-мастера и становится программой самого Джо. Никто не должен генерировать программу, не понимая ее до конца.

    Другие разделы, относящиеся к данной теме:

    • Ортогональность

    • Генераторы исходных текстов

    Вопросы для обсуждения

    • Если в вашем распоряжении имеется функция-мастер построения графического интерфейса, воспользуйтесь ей для генерирования «скелета» приложения. Внимательно изучите каждую строку сгенерированной программы. Всели в ней вам понятно? Могли бы написать ее сами? Лучше написать ее самому, или же она делает то, что вам не нужно?


    Примечания:



    3

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



    4

    В эру Интернета, многие люди, кажется, забыли о настоящих библиотеках, в которых имеется штат сотрудников и научные материалы.



    37

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



    38

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



    39

    Термин "программная интегральная схема", по-видимому, был введен Коксом и Новобилски (1986) в их книге по языку Objective-C под названием "Object-Oriented Programming" [CN91].



    40

    Тем не менее существуют иные методики, которые помогают управлять сложностью программ. Две из них – Java beans и АОР – обсуждались в разделе "Ортогональность".








    Главная | В избранное | Наш E-MAIL | Прислать материал | Нашёл ошибку | Наверх