Совершенный код. Совершенный код. Мастер-класс. Стив Макконнелл. Руководство по стилю программирования и конструированию по
 Скачать 5.88 Mb.
|
|
ГЛАВА 16 Циклы 379 полагает, что census — это структура, содержащая сведения о людях из рассчиты# ваемой группы. Следующий шаг — построение цикла вокруг существующих выражений. Поскольку цикл должен вычислять ставки для каждого человека из группы, индекс должен перечислять всех членов группы. Шаг 4: Создание цикла изнутри наружу (псевдокод) For person = firstPerson to lastPerson rate = table[ census.Age, census.Gender ] totalRate = totalRate + rate End For Все, что вы должны сделать, — это поместить цикл for вокруг существующего кода и добавить к нему пару begin%end. Напоследок убедитесь, что переменные, исполь# зующие индекс цикла person, написаны правильно. В данном случае переменная census изменяется вместе с person, поэтому ее следует корректно проиндексировать. Шаг 5: Создание цикла изнутри наружу (псевдокод) For person = firstPerson to lastPerson rate = table[ census[ person ].Age, census[ person ].Gender ] totalRate = totalRate + rate End For И, наконец, напишите необходимую инициализацию. В этом примере нужно ини# циализировать переменную totalRate. Последний шаг: Создание цикла изнутри наружу (псевдокод) totalRate = 0 For person = firstPerson to lastPerson rate = table[ census[ person ].Age, census[ person ].Gender ] totalRate = totalRate + rate End For Если вы хотите добавить еще один цикл вокруг цикла person, продолжайте таким же образом. Вы не должны жестко придерживаться этого порядка. Идея в том, чтобы начать с чего#то определенного, думать только об одной задаче в каждый момент времени и строить цикл из простых компонентов. Предпринимайте маленькие, понятные шаги, постепенно обобщая и усложняя цикл. Таким образом, вы мини# мизируете количество кода, на котором необходимо одновременно сосредоточи# ваться и, следовательно, уменьшите вероятность ошибки. 16.4. Соответствие между циклами и массивами Циклы и массивы часто связаны друг с другом. Зачастую цикл создается для манипуляций с массивами, и счетчики цикла один к одному соответствуют индексам массива. Так, следу# ющие индексы циклов for соответствуют индексам массива: Перекрестная ссылка О соответ- ствии между циклами и масси- вами см. также раздел 10.7. 380 ЧАСТЬ IV Операторы Пример умножения массивов (Java) for ( int row = 0; row < maxRows; row++ ) { for ( int column = 0; column < maxCols; column++ ) { product[ row ][ column ] = a[ row ][ column ] * b[ row ][ column ]; } } В языке Java цикл для таких операций с массивами необходим. Но стоит заметить, что циклические структуры и массивы не обязательно должны использоваться вместе. Некоторые языки, особенно APL и Fortran 90 и более поздние, предостав# ляют операции с массивами, исключающие необходимость применять такие циклы, как только что продемонстрированные. Вот так выглядит фрагмент кода на APL, выполняющий ту же операцию: Пример умножения массивов (APL) product < a x b Вариант на APL проще и менее подвержен ошибкам. Он использует только три операнда, тогда как фрагмент на Java — 17. Он не содержит переменных цикла, индексов массива или управляющих структур, которые можно некорректно зако# дировать. Из этих примеров следует, что частично программирование направлено на ре# шение задачи, а частично — на решение этой задачи на определенном языке. Выбранный вами язык существенно влияет на получаемый результат. Контрольный список: циклы Выбор и создание цикла Используется ли цикл while вместо цикла for, если он больше подходит? Создавался ли цикл изнутри наружу? Вход в цикл Выполняется ли вход в цикл сверху? Расположен ли код инициализации непосредственно перед циклом? Если необходим бесконечный или событийный цикл, конструируется ли он явно, или сделан такой ляп, как for i = 1 to 9999? В цикле for в C++, C или Java резервируется ли заголовок цикла только для управляющего кода? Тело цикла Использует ли цикл скобки { и } или их эквиваленты для обрамления тела цикла и предотвращения проблем, связанных с неправильной модификацией? Содержит ли тело цикла хоть что-то? Не пустое ли оно? Сгруппированы ли служебные операции в начале или конце цикла? Выполняет ли цикл одну и только одну функцию, как это делает хорошо спроектированный метод? Достаточно ли цикл короткий, чтобы его можно было сразу увидеть целиком? Не превышает ли вложенность цикла трех уровней? http://cc2e.com/1616 ГЛАВА 16 Циклы 381 Вынесено ли содержимое длинного цикла в отдельный метод? Если цикл достаточно длинный, написан ли он особенно ясно? Индексы цикла Если это цикл for, не выполняются ли манипуляции с индексом цикла внут- ри самого цикла? Используется ли для сохранения важных значений индекса цикла вне этого цикла специальная переменная, а не сам индекс цикла? Является ли индекс цикла порядковым или перечислимым типом, но не типом с плавающей запятой? Имеет ли индекс цикла смысловое имя? Не содержит ли цикл пересечения индексов? Завершение цикла Завершается ли цикл при всех возможных условиях? Использует ли цикл счетчики безопасности, если они приняты на уровне стандарта? Очевидно ли условие завершения цикла? Если используются операторы break или continue, корректны ли они? Ключевые моменты Циклы сложны для понимания. Сохраняя их простыми, вы помогаете читате# лям вашего кода. К способам упрощения циклов относятся: избегание экзотических видов цик# лов, минимизация вложенности, создание очевидных входов и выходов цикла и хранение служебного кода в одном месте. Индексы цикла часто употребляются неправильно. Называйте их понятно и используйте только с одной целью. Аккуратно продумайте весь цикл, чтобы убедиться, что он работает правиль# но во всех случаях и завершается при любых возможных обстоятельствах. 382 ЧАСТЬ IV Операторы Г Л А В А 1 7 Нестандартные управляющие структуры Содержание 17.1. Множественные возвраты из метода 17.2. Рекурсия 17.3. Оператор goto 17.4. Перспективы нестандартных управляющих структур Связанные темы Общие вопросы управления: глава 19 Последовательный код: глава 14 Код с условными операторами: глава 15 Код с циклами: глава 16 Обработка исключений: раздел 8.4 Несколько управляющих структур существует в сумрачной зоне между передовым краем технологии и полной дискредитацией и несостоятельностью, и часто в одно и то же время! Эти конструкции доступны не во всех языках, но там, где они есть, они могут быть полезны при аккуратном применении. 17.1. Множественные возвраты из метода Большинство языков поддерживает некоторые способы возврата управления после частичного выполнения метода. Операторы return и exit — управляющие струк# туры, которые позволяют программе при желании завершить работу метода. В результате функция завершается через нормальный канал выхода, возвращая уп# равление вызывающему методу. Слово return здесь используется как общий тер# мин, обозначающий return в C++ и Java, Exit Sub и Exit Function в Visual Basic и аналогичные конструкции. Далее перечислены некоторые принципы использо# вания оператора return. http://cc2e.com/1778 ГЛАВА 17 Нестандартные управляющие структуры 383 Используйте return, если это повышает читабельность В неко# торых методах при получении ответа хочется сразу вернуть управление вызывающей стороне. Если метод определен так, что обнаружение ошибки не требует никакой дополнительной очистки ресурсов, то отсутствие немедлен# ного возврата означает необходимость писать лишний код. Вот хороший пример ситуации, когда возврат из нескольких частей метода име# ет смысл: Пример правильного множественного возврата из метода (C++) Этот метод возвращает перечислимый тип Comparison. Comparison Compare( int value1, int value2 ) { if ( value1 < value2 ) { return Comparison_LessThan; } else if ( value1 > value2 ) { return Comparison_GreaterThan; } return Comparison_Equal; } Другие примеры не настолько однозначны, что будет проиллюстрировано ниже. Упрощайте сложную обработку ошибок с помощью сторожевых опера' торов (досрочных return или exit) Если программа вынуждена проверять боль# шое количество ошибочных ситуаций перед выполнением номинальных действий, это может привести к коду очень большой вложенности и замаскировать номи# нальный вариант. Вот пример такого кода: Код, скрывающий номинальный вариант (Visual Basic) If file.validName() Then If file.Open() Then If encryptionKey.valid() Then If file.Decrypt( encryptionKey ) Then Здесь код номинального варианта. ‘ Много кода. End If End If End If End If Отступ основного кода метода внутри четырех условий if выглядит неэстетично, особенно если этот код в самом внутреннем блоке if состоит из множества строк. В таких случаях часто можно упростить логику, если все ошибочные ситуации проверять сначала, расчистив дорогу для номинального хода алгоритма. Вот как это может выглядеть: > > 384 ЧАСТЬ IV Операторы Простой код, использующий сторожевые операторы для прояснения номинального варианта (Visual Basic) ‘ Выполняем инициализацию. При обнаружении ошибок завершаем работу. If Not file.validName() Then Exit Sub If Not file.Open() Then Exit Sub If Not encryptionKey.valid() Then Exit Sub If Not file.Decrypt( encryptionKey ) Then Exit Sub ’ Много кода. В таком простом примере описанный способ выглядит аккуратным решением, но промышленный код при обнаружении ошибки часто требует большего количе# ства служебных операций или действий по очистке ресурсов. Вот более реалис# тичный пример: Более реалистичный код, использующий сторожевые операторы для прояснения номинального варианта (Visual Basic) ‘ Выполняем инициализацию. При обнаружении ошибок завершаем работу. If Not file.validName() Then errorStatus = FileError_InvalidFileName Exit Sub End If If Not file.Open() Then errorStatus = FileError_CantOpenFile Exit Sub End If If Not encryptionKey.valid() Then errorStatus = FileError_InvalidEncryptionKey Exit Sub End If If Not file.Decrypt( encryptionKey ) Then errorStatus = FileError_CantDecryptFile Exit Sub End If Здесь код номинального варианта. ‘ Много кода. В коде промышленного масштаба использование Exit Sub приводит к написанию довольно большого количества кода до обработки номинального варианта. Од# нако Exit Sub позволяет избежать глубокой вложенности, присущей первому при# меру, и если код первого примера расширить с целью установки значений пере# менной errorStatus, то вариант с Exit Sub покажется лучшим с точки зрения груп# пировки взаимосвязанных выражений. Когда вся пыль осядет, подход с Exit Sub покажется более удобным для чтения и сопровождения, и за небольшую цену. > ГЛАВА 17 Нестандартные управляющие структуры 385 Минимизируйте число возвратов из каждого метода Тяжело понять ло# гику метода, если при чтении его последних строк вы не подозреваете о возмож# ности выхода из него где#то вверху. По этой причине используйте операторы воз# врата благоразумно — только если они улучшают читабельность. 17.2. Рекурсия При рекурсии метод решает небольшую часть задачи, разбивает задачу на мень# шие порции и вызывает сам себя для решения каждой из этих порций. Обычно рекурсию применяют, когда небольшую часть задачи легко решить, а саму задачу просто разложить на составные части. Рекурсия не часто бывает необходима, но при аккуратном использова# нии она позволяет создавать элегантные решения, как в этом примере, где алгоритм сортировки иллюстрирует отличное применение рекурсии: Пример алгоритма сортировки, использующего рекурсию (Java) void QuickSort( int firstIndex, int lastIndex, String [] names ) { if ( lastIndex > firstIndex ) { int midPoint = Partition( firstIndex, lastIndex, names ); Здесь выполняются рекурсивные вызовы. QuickSort( firstIndex, midPoint1, names ); QuickSort( midPoint+1, lastIndex, names ) } } В этом фрагменте алгоритм сортировки разрезает массив на две части и затем вызывает сам себя для сортировки каждой половины массива. Когда ему будет передан участок массива, слишком короткий для сортировки, т. е. когда ( lastIndex <= firstIndex ), он перестанет вызывать сам себя. Для малой группы задач рекурсия позволяет создать простые, элегантные реше# ния. Для несколько большей группы задач она позволяет создать простые, элегант# ные, трудные для понимания решения. Для большинства задач она создает исклю# чительно запутанные решения — в таких случаях использование простых итера# ций обычно более понятно. Поэтому применяйте рекурсию выборочно. Примеры рекурсии Допустим, у вас есть тип данных, представляющий лабиринт. Лабиринт — это обычно некая сетка, в узлах которой вы можете повернуть направо, налево, пере# меститься вверх или вниз. Часто существует возможность двигаться в нескольких направлениях. Как вы будете разрабатывать программу для поиска пути через лабиринт (рис. 17#1)? Если вы используете рекурсию, ответ довольно прост. Вы начинаете от входа и пробуете все возможные повороты, пока не найдете выхода. Попадая в точку в первый раз, вы пробуете повернуть налево, если это невозможно, то пробуете пойти вверх или вниз. В конце концов вы пытаетесь пойти направо. Вам не надо боять# > 386 ЧАСТЬ IV Операторы ся заблудиться, потому что на каждом перекрестке вы оставляете несколько хлебных крошек и не поворачиваете в одну и ту же сторону дважды. Рис. 17'1. Рекурсия может быть мощным оружием в борьбе со сложностью, если используется по назначению Рекурсивный код может выглядеть, например, так: Пример рекурсивного перемещения по лабиринту (C++) bool FindPathThroughMaze( Maze maze, Point position ) { // Если это место уже исследовано, не надо снова его проверять. if ( AlreadyTried( maze, position ) ) { return false; } // Если это место и есть выход, объявляем успешное завершение. if ( ThisIsTheExit( maze, position ) ) { return true; } // Запоминаем, что это место исследовано. RememberPosition( maze, position ); // Проверяем пути налево, вверх, направо, вниз; // если один из путей приводит к успеху, прекращаем поиск. if ( MoveLeft( maze, position, &newPosition ) ) { if ( FindPathThroughMaze( maze, newPosition ) ) { return true; } } if ( MoveUp( maze, position, &newPosition ) ) { if ( FindPathThroughMaze( maze, newPosition ) ) { return true; } } ГЛАВА 17 Нестандартные управляющие структуры 387 if ( MoveDown( maze, position, &newPosition ) ) { if ( FindPathThroughMaze( maze, newPosition ) ) { return true; } } if ( MoveRight( maze, position, &newPosition ) ) { if ( FindPathThroughMaze( maze, newPosition ) ) { return true; } } return false; } Первая строка кода проверяет, исследована ли уже данная точка. Одна из ключе# вых задач рекурсивного метода — предотвращение бесконечной рекурсии. В дан# ном случае, если вы не будете проверять, что эта развилка уже исследовалась, вы можете бесконечно обследовать ее. Второе выражение проверяет, не является ли эта позиция выходом из лабиринта. Если ThisIsTheExit() возвращает true, метод тоже возвращает true. Третье выражение запоминает, что вы посетили данную точку. Это предотвраща# ет бесконечную рекурсию, которая может возникнуть в результате замкнутого пути. Остальные строки пытаются найти выход при движении налево, вверх, вниз и направо. Рекурсия прекратится, если метод когда#нибудь вернет true, т. е. будет найден выход из лабиринта. Логика, используемая в этом примере, довольно прямолинейна. Большинство людей испытывают некоторый дискомфорт при виде рекурсивных методов, ссылающихся сами на себя. Однако в данном случае альтернативное решение было бы гораздо более трудоемким, и поэтому рекурсия отлично подходит. Советы по использованию рекурсии При применении рекурсии имейте в виду эти советы. Убедитесь, что рекурсия остановится Проверьте метод, чтобы убедиться, что он включает нерекурсивный путь. Обычно это значит, что в методе присут# ствует проверка, останавливающая дальнейшую рекурсию, когда в ней отпадает необходимость. В примере с лабиринтом условия для AlreadyTried() и ThisIsTheExit() гарантируют, что рекурсия остановится. Предотвращайте бесконечную рекурсию с помощью счетчиков безопасности Если вы применяете рекурсию в ситуации, не позволяющей сделать простую проверку вро# де описанной выше, добавьте счетчики безопасности, дабы избежать бесконечной рекурсии. Счетчиком должна быть такая переменная, которая не будет создаваться при каждом вызове метода. Используйте переменную#член класса или передавайте счетчик бе# зопасности в виде параметра. Приведем пример: Рекурсивная процедура должна иметь возможность изменять значение safetyCounter, поэтому в Visual Basic она объявляется как ByRef-параметр. 388 ЧАСТЬ IV Операторы Пример использования счетчика безопасности для предотвращения бесконечной рекурсии (Visual Basic) Public Sub RecursiveProc( ByRef safetyCounter As Integer ) If ( safetyCounter > SAFETY_LIMIT ) Then Exit Sub End If safetyCounter = safetyCounter + 1 RecursiveProc( safetyCounter ) End Sub В данном случае, если вложенность превысит предел счетчика безопасности, ре# курсия прекратится. Если вы не хотите передавать счетчик безопасности в виде отдельного парамет# ра, можно использовать классовую переменную в C++, Java, Visual Basic или соот# ветствующий эквивалент в других языках. Ограничьте рекурсию одним методом Циклическая рекурсия (A вызывает B вызывает C вызывает A) представляет опасность, потому что ее сложно обнару# жить. Осмысление рекурсии в одном методе — достаточно трудоемкое занятие, а понимание рекурсии, охватывающей несколько методов, — это уже слишком. Если возникла циклическая рекурсия, обычно можно так перепроектировать методы, что рекурсия будет ограничена одним из них. Если это не получается, а вы все равно считаете, что рекурсия — это лучший подход, используйте счетчики безо# пасности в качестве страховки. Следите за стеком При использовании рекурсии вы точно не знаете, сколько места в стеке будет занимать ваша программа. Кроме того, тяжело заранее пред# сказать, как будет вести себя программа во время выполнения. Однако вы можете предпринять некоторые усилия для контроля ее поведения. Во#первых, если вы добавили счетчик безопасности, одним из принципов уста# новки его предела является возможный размер используемого стека. Сделайте этот предел достаточно низким, чтобы предотвратить переполнение стека. Во#вторых, следите за выделением памяти для локальных переменных в рекурсив# ных функциях, особенно если эти переменные достаточно объемны. Иначе го# воря, лучше использовать new для создания объектов в куче, чем позволять ком# пилятору генерировать автоматические объекты в стеке. Не используйте рекурсию для факториалов и чисел Фибоначчи Одна из проблем с учебниками по вычислительной технике в том, что они предлагают глупые примеры рекурсии. Типичными примерами являются вычисление факто# риала или последовательности Фибоначчи. Рекурсия — мощный инструмент, и очень глупо использовать ее в этих двух случаях. Если бы программист, работаю# щий у меня, применял рекурсию для вычисления факториала, я бы нанял кого#то другого. Вот рекурсивная версия вычисления факториала: |