Руководство по стилю программирования и конструированию по
 Скачать 7.6 Mb.
|
|
ГЛАВА 18 Табличные методы 417 Подгонка значений ключа Во всех трех предыдущих примерах вы могли использовать данные в качестве ключа для прямого обращения к таблице. То есть можно было указать перемен- ную messageID как ключ без всяких изменений, переменную month в примере количества дней в месяцах, а также gender, maritalStatus и smokingStatus в приме- ре ставок страхования. Было бы хорошо всегда обращаться к таблице напрямую, потому что это просто и быстро. Однако не всегда данные для этого годятся. В примере со ставками стра- хования переменная age не очень удобна в качестве ключа. Первоначальная ло- гика определяла одну ставку для лиц моложе 18 лет, индивидуальные ставки для возрастов от 18 до 65 и одну ставку для людей старше 65. Это означает, что для возрастов от 0 до 17 и от 66 и выше нельзя использовать возраст как ключ напря- мую, если таблица хранит только один набор ставок для нескольких лет. Это приводит к обсуждению вопроса подгонки значений ключа в таблице поис- ка. Подогнать ключ можно несколькими способами. Продублировать информацию, чтобы использовать ключ напрямую Один прямолинейный способ заставить age работать ключом в таблице ставок — продублировать все ставки для лиц, моложе 18, для каждого возраста от 0 до 17, а затем использовать возраст для прямого обращения к таблице. То же самое мож- но сделать и для возрастов от 66 лет и старше. Преимущество этого подхода в том, что структура таблицы остается простой и доступ к данным так же прост. Если нужно добавить специальное значение ставки для некоторого возраста, меньше- го 17, вы можете просто изменить табличное значение. Недостаток этого метода в том, что дублирование приведет к напрасным затратам на хранение избыточ- ной информации, а также увеличит вероятность появления ошибок в таблице хотя бы потому, что таблица будет содержать избыточные данные. Преобразовать ключ, чтобы использовать его напрямую Второй способ задействовать Age в качестве прямого ключа — применить к переменной Age неко- торую функцию, которая позволит это делать. В данном случае такая функция дол- жна преобразовывать все возрасты от 0 до 17 к какому-то одному значению, ска- жем, 17, а возрасты старше 66 — к другому, например, 66. В данном случае такое преобразование легко выполнить с помощью функций min() и max(). Так, для со- здания табличного ключа в диапазоне от 17 до 66 можно использовать выражение: max( min( 66, Age ), 17 ) Реализация функции трансформации требует хорошего понимания структуры данных, которые вы хотите применить как ключ, и это не всегда так просто, как использование функций min() и max(). Допустим, в этом примере ставки меня- ются через интервалы не в 5 лет, а в 1 год. Если только вы не хотите дублировать все данные по пять раз, вам придется написать функцию, которая делит Age на 5 и использует методы min() и max(). Изолируйте преобразование ключа в собственном методе Если вам нуж- но подгонять данные для использования в качестве табличного ключа, помести- те операции, трансформирующие данные в ключ, в отдельный метод. Его исполь- зование исключает возможность применения разных преобразований в разных 418 ЧАСТЬ IV Операторы местах. Это упростит модификацию при изменении функции преобразования. Хорошее имя процедуры, такое как KeyFromAge(), также прояснит и задокументи- рует назначение математических махинаций. Если ваша среда предоставляет готовые варианты преобразования ключа, исполь- зуйте их. Например, класс HashMap в языке Java позволяет создавать пары «ключ- значение». 18.3. Таблицы с индексированным доступом Иногда простого математического преобразования недостаточно для перехода от таких данных, как Age к значению ключа. Некоторые из таких случаев подходят для схем с индексным доступом. Применяя индексы, вы используете исходные данные для поиска ключа в индексной таблице, а затем значение из этой таблицы служит для поиска интересующих вас данных. Допустим, вы заведуете складом, и у вас около 100 наименований товара. Далее предположим, что каждый товар имеет четырехзначный номер в диапазоне от 0000 до 9999. В этом случае, если вы захотите задействовать номер товара в качестве ключа для прямого доступа к таблице, описывающей какой-то признак каждого товара, вам придется создать индексный массив с 10 000 записей (от 0 до 9999). Этот массив в основном будет пустым за исключением 100 элементов, соответ- ствующих номерам товаров на вашем складе. Как показано на рис. 18-4, эти эле- менты указывают на таблицу с описанием товаров, содержащую гораздо менее 10 000 записей. Рис. 18-4. В отличие от таблиц с прямым доступом для обращения к таблице с индексным доступом используется промежуточный индекс ГЛАВА 18 Табличные методы 419 У схем с индексным доступом два главных преимущества. Во-первых, если каж- дый элемент главной таблицы поиска имеет большой размер, создание индекс- ного массива с большим количеством пустых ячеек потребует гораздо меньше места, чем создание самой таблицы поиска с большим количеством пустых яче- ек. Пусть, например, элемент основной таблицы занимает 100 байт, а элемент индексной таблицы — 2 байта. Далее предположим, что главная таблица содер- жит 100 записей, а данные, необходимые для обращения к ней, могут принимать 10 000 возможных значений. В этом случае выбор осуществляется между исполь- зованием индексной таблицы с 10 000 записей или только одной главной табли- цы с 10 000 записей. Если вы используете индекс, общий объем требуемой памя- ти равен 30 000 байт. Если вы откажетесь от индекса и будете попусту тратить память в основной таблице, то общий объем используемой памяти составит 1 000 000 байт. Вторым преимуществом индексного доступа (даже если вам не удастся сэкономить память с его помощью) является то, что иногда дешевле манипулировать элемен- тами индекса, чем элементами основной таблицы. Так, если у вас есть таблица с именами работников, датами их приема на работу и окладами, вы можете создать один индекс для доступа к таблице по имени работника, второй — для доступа на основе даты приема, и третий — для доступа на основе размера зарплаты. И последнее преимущество индексной схемы доступа — общее для всех таблиц поиска удобство сопровождения. Данные, закодированные в таблицах, легче со- провождать, чем внедренные в код. Для увеличения гибкости поместите код ин- дексного доступа в отдельный метод и вызывайте его, когда вам нужно получить значение ключа на основе номера товара. Когда понадобится изменить таблицу, вы можете решить изменить схему индексного доступа или даже перейти к дру- гому способу доступа к таблице поиска. Схему доступа будет легче поменять, если код доступа по индексу не разбросан по всей программе. 18.4. Таблицы со ступенчатым доступом Еще один способ табличного доступа — ступенчатый метод. Этот метод не такой прямой, как индексная структура, но позволяет не терять такого большого объе- ма памяти. Основная идея ступенчатой структуры в том, что записи в таблице соответству- ют некоторому диапазону данных, а не отдельным элементам (рис. 18-5). Рис. 18-5. Ступенчатый подход классифицирует каждый элемент, определяя уровень, на котором он наталкивается на «лестницу». «Ступенька», в которую этот элемент упирается, определяет его категорию 420 ЧАСТЬ IV Операторы Например, если вы пишете аттестационную программу, диапазон оценки «B» мо- жет быть в пределах 75–90%. Вот список оценок, которые вам однажды, возмож- но, придется запрограммировать: ≥ 90.0% A < 90.0% B < 75.0% C < 65.0% D < 50.0% F Это ужасный диапазон для табличного поиска, потому что вы не можете напи- сать простую функцию преобразования данных для соответствия буквам от A до F. Индексная схема неудобна, так как используются числа с плавающей запятой. Вы можете предложить конвертировать числа с плавающей запятой в целые, что для данного случая вполне допустимо, однако в целях иллюстрации этот пример будет придерживаться чисел с плавающей запятой. Применяя ступенчатый метод, вы помещаете верхнюю границу каждого диапазо- на в таблицу, а затем пишете цикл для сравнения количества баллов с этой верх- ней границей. Обнаружив точку, в которой сумма баллов в первый раз превысит заданный предел, вы узнаете оценку. Применяя ступенчатую методику, надо сле- дить за правильной обработкой граничных точек диапазона. Вот пример кода Visual Basic, присваивающей оценки группе студентов, основываясь на данных этого примера: Пример ступенчатого поиска в таблице (Visual Basic) ‘ Подготавливаем данные для таблицы оценок. Dim rangeLimit() As Double = { 50.0, 65.0, 75.0, 90.0, 100.0 } Dim grade() As String = { ”F”, “D”, “C”, “B”, “A” } maxGradeLevel = grade.Length – 1 ’ Присваиваем оценки, основываясь на количестве баллов, набранных студентом. gradeLevel = 0 studentGrade = “A” While ( ( studentGrade = “A” ) and ( gradeLevel < maxGradeLevel ) ) If ( studentScore < rangeLimit( gradeLevel ) ) Then studentGrade = grade( gradeLevel ) End If gradeLevel = gradeLevel + 1 Wend Хотя это и простой пример, вы легко можете его обобщить для работы с несколь- кими студентами или несколькими системами оценок (например, введя разные оценки для различных уровней сложности выполняемых заданий), а также для изменения системы оценок. Преимущество этого подхода перед другими табличными методами в том, что он хорошо работает с нестандартными данными. Пример с оценками прост с той точки зрения, что, хотя оценки и присваиваются через неодинаковые промежут- ГЛАВА 18 Табличные методы 421 ки, сами рассматриваемые числа — «круглые», оканчивающиеся на 5 или 0. Сту- пенчатый способ столь же хорошо подходит и для данных, не заканчивающихся на 5 или 0. Вы можете применять эту методику и в статистических задачах для работы с такими примерами вероятностных распределений, как этот: Вероятность Сумма страхового иска 0,458747 $0,00 0,547651 $254,32 0,627764 $514,77 0,776883 $747,82 0,893211 $1 042,65 0,957665 $5 887,55 0,976544 $12 836,98 0,987889 $27 234,12 Такие ужасные числа сводят на нет все попытки создать функцию для их точного преобразования в табличные ключи. В этом случае следует использовать ступен- чатый метод. Этот подход также позволяет оценить главные преимущества табличных методов: гибкость и модифицируемость. Если диапазоны баллов в примере с оценками надо изменить, программу легко исправить, изменив элементы массива RangeLimit. Вы легко можете обобщить метод выставления отметок так, чтобы он принимал из- вне таблицы с отметками и соответствующими граничными значениями баллов. При выставлении оценок не обязательно использовать баллы, выраженные в про- центах, их можно поменять на обычные единицы, и это не потребует больших изменений в программе. Вот несколько тонкостей, которые надо принимать во внимание, применяя сту- пенчатый метод. Следите за граничными точкамиУбедитесь, что вы учитываете верхнюю гра- ницу каждого диапазона. Выполните ступенчатый поиск так, чтобы он находил значения, соответствующие любому интервалу, кроме самого верхнего, а затем за- дайте несколько элементов, попадающих в этот верхний интервал. Иногда требу- ется создать искусственное значение для верхней границы последнего интервала. Не ошибитесь с операциями < или <=! Убедитесь, что при значениях, попадаю- щих в верхний диапазон, цикл корректно завершается, а также что границы ин- тервалов обрабатываются правильно. Рассмотрите вопрос использования бинарного поиска вместо последова- тельногоВ примере с оценками цикл, присваивающий отметки, последователь- но проходит по списку предельных значений баллов. Если у вас будет более длин- ный список, затраты на последовательный поиск могут чрезмерно возрасти. В этом случае можно воспользоваться квази-бинарным поиском. «Квази» он потому, что цель большинства бинарных поисков — нахождение значения. В данном случае вы не намерены найти значение — вы ищете правильную категорию для этого значения. Алгоритм бинарного поиска должен корректно определить, куда это 422 ЧАСТЬ IV Операторы значение попадает. Не забывайте также рассматривать граничные точки как спе- циальный случай. Рассмотрите вопрос использования индексного доступа вместо ступен- чатого методаСхема с индексным доступом (см. раздел 18.3) может быть хо- рошей альтернативой ступенчатому подходу. Поиск, выполняющийся в ступенча- том методе, может увеличить накладные расходы, и если, скорость выполнения имеет значение, вы, возможно, захотите пожертвовать объемом памяти и затра- тами на дополнительную индексную структуру, чтобы получить преимущество в скорости, обусловленное более прямым методом доступа. Очевидно, эта альтернатива во всех случаях не годится. В примере с оценками вы, возможно, захотите ее использовать. Если у вас всего 100 дискретных процент- ных значений, расходы на дополнительную память для индексного массива не будут чрезмерными. С другой стороны, если вы работаете с данными вероятностного распределения, приведенными выше, вы не сможете применить индексную схе- му, потому что не сможете задействовать в качестве ключей к таблице данных такие числа, как 0,458747 и 0,547651. В некоторых случаях подойдет любой из нескольких вари- антов. И задачей проектирования является выбор одного из нескольких хороших вариантов для этого конкретного слу- чая. Не слишком волнуйтесь по поводу выбора наилучше- го. Как говорит Батлер Лемпсон, выдающийся инженер из Microsoft, лучше стремиться к хорошему решению и избегать неудач, чем пытать- ся найти наилучшее решение (Lampson, 1984). Поместите ступенчатый поиск в таблице в отдельный методКогда вы создаете функцию преобразования, которая трансформирует такое значение, как StudentGrade, в табличный ключ, поместите ее в отдельный метод. 18.5. Другие примеры табличного поиска Несколько примеров табличного поиска встречаются в других разделах этой книги. Они используются в процессе обсуждения других методик, и поэтому в контек- сте не подчеркивается их принадлежность к табличному поиску. Вот где вы мо- жете их найти: 쐽 поиск ставок в таблице страхования: раздел 16.3; 쐽 применение таблиц решения для замены сложной логики: подраздел «Исполь- зуйте таблицы решений для замены сложных условий» раздела 19.1; 쐽 расходы на страничную организацию памяти при табличном поиске: раздел 25.3; 쐽 комбинации логических значений (A или B или C): подраздел «Замена слож- ных выражений на обращение к таблице» раздела 26.1; 쐽 предварительное вычисление значения в таблице погашения ссуд: раздел 26.4. Перекрестная ссылка О пра- вильных подходах к выбору альтернативных способов про- ектирования см. главу 5. ГЛАВА 18 Табличные методы 423 Контрольный список: табличные методы Рассмотрены ли табличные методы в качестве альтерна- тивы сложной логике? Рассмотрены ли табличные методы в качестве альтернативы сложным струк- турам с наследованием? Рассмотрен ли вопрос размещения табличных данных отдельно от программы и их чтения во время выполнения, чтобы позволить обновлять данные без изменения кода? Если доступ к таблице нельзя осуществить напрямую с помощью простого индекса массива (как в примере с возрастами), помещены ли вычисления ключа доступа в отдельный метод, а не разбросаны по всему коду? Ключевые моменты 쐽 Таблицы представляют собой альтернативу сложной логике и структурам с наследованием. Если вы понимаете, что сбиты с толку логикой программы или деревом наследования, спросите себя, не проще ли использовать таблицу по- иска. 쐽 Основной вопрос при использовании таблиц состоит в выборе способа до- ступа к таблице. Вы можете использовать прямой, индексный или ступенча- тый доступ. 쐽 Другой основной вопрос состоит в выборе того, что конкретно будет поме- щено в таблицу. http://cc2e.com/1872 424 ЧАСТЬ IV Операторы Г Л А В А 1 9 Общие вопросы управления Содержание 쐽 19.1. Логические выражения 쐽 19.2. Составные операторы (блоки) 쐽 19.3. Пустые выражения 쐽 19.4. Укрощение опасно глубокой вложенности 쐽 19.5. Основа программирования: структурное програм- мирование 쐽 19.6. Управляющие структуры и сложность Связанные темы 쐽 Последовательный код: глава 14 쐽 Код с условными операторами: глава 15 쐽 Код с циклами: глава 16 쐽 Нестандартные управляющие структуры: глава 17 쐽 Сложность в разработке ПО: подраздел «Главный Технический Императив Раз- работки ПО: управление сложностью» раздела 5.2 Обсуждение способов управления было бы неполным без углубления в несколь- ко общих вопросов, касающихся управляющих структур. Большая часть этой гла- вы посвящена подробностям их практического применения. Если вам интерес- ней читать о теории управляющих структур, а не о мелких деталях, сосредоточь- тесь на исторической перспективе структурного программирования (раздел 19.5), а затем на взаимодействии управляющих структур (раздел 19.6). 19.1. Логические выражения Кроме простейших случаев, таких, в которых происходит последовательное вы- полнение операторов, все управляющие структуры зависят от вычисления логи- ческих выражений. http://cc2e.com/1978 ГЛАВА 19 Общие вопросы управления 425 Использование true и false в логических проверках В логических выражениях следует использовать идентификаторы true и false, а не значения 0 и 1. Большинство современных языков реализует логический тип дан- ных и предоставляет предопределенные идентификаторы для значений «истина» и «ложь». В таких языках все просто: они даже не позволят вам присвоить логиче- ским переменным другие значения, кроме true или false. В языках, не содержащих встроенного логического типа, от вас требуется большая дисциплинированность, чтобы сделать логические выражения читабельными. Приведем пример: Примеры использования неоднозначных флажков для логических значений (Visual Basic) Dim printerError As Integer Dim reportSelected As Integer Dim summarySelected As Integer If printerError = 0 Then InitializePrinter() If printerError = 1 Then NotifyUserOfError() If reportSelected = 1 Then PrintReport() If summarySelected = 1 Then PrintSummary() If printerError = 0 Then CleanupPrinter() Если использование флажков 0 и 1 — общая практика, то чем она плоха? При чте- нии кода неочевидно, когда выполняются вызовы функций: когда проверки усло- вия истинны или когда они ложны. Ничего в этом фрагменте не говорит о том, представляет ли 1 «истину», а 0 — «ложь» или же все наоборот. Нельзя даже утвер- ждать, что 1 и 0 служат в качестве значений «истина» и «ложь». Например, в строке If reportSelected = 1 число 1 может легко обозначать первый отчет, 2 — второй, 3 — третий; ничто в коде не наводит на мысль, что 1 означает либо «истину», либо «ложь». Кроме того, легко можно написать 0, имея в виду 1, и наоборот. Используйте термины true и false для проверки логических выражений. Если ваш язык не поддерживает их напрямую, создайте их с помощью макросов препроцес- сора или глобальных переменных. Вот как можно переписать предыдущий пример, используя встроенные идентификаторы True и False языка Visual Basic: Хорошие, но не превосходные примеры использования True и False вместо числовых значений для проверок условий (Visual Basic) Dim printerError As Boolean Dim reportSelected As ReportType Dim summarySelected As Boolean If ( printerError = False ) Then InitializePrinter() If ( printerError = True ) Then NotifyUserOfError() If ( reportSelected = ReportType_First ) Then PrintReport() If ( summarySelected = True ) Then PrintSummary() Перекрестная ссылка Еще луч- ший подход к выполнению тех же проверок можно найти в сле- дующем примере кода. 426 ЧАСТЬ IV Операторы If ( printerError = False ) Then CleanupPrinter() Применение констант True и False проясняет назначение кода. Вам не нужно по- мнить, что обозначают 1 и 0, и вы не сможете их случайно перепутать. Более того, в переписанном коде стало понятно, что в некоторых случаях 1 и 0 в исходном примере на Visual Basic не являлись логическими флагами. Выражение If report- Selected = 1 было не проверкой логического значения, а проверкой того, выбран ли первый отчет. Этот подход сообщает читателю, что вы выполняете логическую проверку. Кро- ме того, сложнее написать true, подразумевая false, чем 1, подразумевая 0. Также вы избежите распространения магических чисел 0 и 1 по всему коду. Далее при- ведены советы по использованию true и false в логических проверках. Используйте неявное сравнение логических величин с true или false Вы сможете сделать проверку условия более понятной, если будете рассматривать про- веряемые выражения как логические. Например, пишите: while ( not done ) ... while ( a > b ) ... вместо: while ( done = false ) ... while ( (a > b) = true ) ... Использование неявных сравнений уменьшает число элементов, которые придется помнить при чтении кода, и приближает получаемое выражение к разговорному английскому. Вот как улучшить стиль предыдущего примера: Улучшенные примеры неявных проверок True или False (Visual Basic) Dim printerError As Boolean Dim reportSelected As ReportType Dim summarySelected As Boolean If ( Not printerError ) Then InitializePrinter() If ( printerError ) Then NotifyUserOfError() If ( reportSelected = ReportType_First ) Then PrintReport() If ( summarySelected ) Then PrintSummary() If ( Not printerError ) Then CleanupPrinter() Если ваш язык не поддерживает логические переменные и вам приходится их эмулировать, то, вероятно, вы не смо- жете использовать эту технологию, поскольку искусствен- ные true и false не всегда могут проверяться в таких выра- жениях, как while ( not done ). Перекрестная ссылка О логи- ческих переменных см. раздел 12.5. |