Файл: Руководство по стилю программирования и конструированию по.pdf

ГЛАВА 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()
Перекрестная ссылка Еще луч- ший подход к выполнению тех же проверок можно найти в сле- дующем примере кода.