Совершенный код. Совершенный код. Мастер-класс. Стив Макконнелл. Руководство по стилю программирования и конструированию по
 Скачать 5.88 Mb.
|
|
ГЛАВА 18 Табличные методы 415 напечатать метку поля, напечатать значение флажка. вариант: ( битовое поле ) прочитать битовое поле, напечатать метку поля, напечатать битовое поле. Конец Выбора Конец цикла Пока Нужно признать, что этот метод с шестью вариантами выбора длиннее, чем от# дельный метод для печати температуры. Но это единственный метод, который вам необходим. Вам не нужны остальные 19 функций для остальных 19 типов сооб# щений. Данный метод обрабатывает шесть типов полей, и обслуживает все виды сообщений. Этот метод также иллюстрирует наиболее сложный способ реализации таблич# ного поиска, так как использует оператор case. Другой подход — создание абст# рактного класса AbstractField и последующее наследование от него подклассов для каждого типа поля. Тогда вам не понадобится оператор case, вы сможете вызы# вать метод#член соответствующего объектного типа. Вот как можно создать такие объекты на C++: Пример создания объектных типов (C++) class AbstractField { public: virtual void ReadAndPrint( string, FileStatus & ) = 0; } class FloatingPointField : public AbstractField { public: virtual void ReadAndPrint( string, FileStatus & ) { } } class IntegerField ... class StringField ... Этот фрагмент объявляет во всех классах метод, принимающий строковый пара# метр и параметр типа FileStatus. Следующий шаг — объявление массива для хранения набора объектов. Этот мас# сив и есть таблица для поиска. Вот как она выглядит: Пример создания таблицы для хранения объектов каждого типа (C++) AbstractField* field[ Field_Last ]; Последний шаг в настройке таблицы объектов — заполнение массива Field кон# кретными объектами: 416 ЧАСТЬ IV Операторы Пример заполнения списка объектов (C++) field[ Field_FloatingPoint ] = new FloatingPointField(); field[ Field_Integer ] = new IntegerField(); field[ Field_String ] = new StringField(); field[ Field_TimeOfDay ] = new TimeOfDayField(); field[ Field_Boolean ] = new BooleanField(); field[ Field_BitField ] = new BitFieldField(); В этом коде предполагается, что FloatingPointField и другие идентификаторы с правой стороны выражений присваивания — это имена объектов, унаследован# ных от AbstractField. Присваивание объектов элементам массива означает, что вы сможете вызвать правильную версию метода ReadAndPrint(), обращаясь к элементу массива, а не используя конкретный тип объекта напрямую. Подготовив таблицу методов, можно обрабатывать поле сообщения с помощью простого обращения к таблице объектов и вызова одного из методов#членов этих объектов. Код может выглядеть так: Пример выбора объектов и их методов из таблицы (C++) Это строки — служебный код, необходимый для обработки каждого поля в сообщении. fieldIdx = 1; while ( ( fieldIdx <= numFieldsInMessage ) and ( fileStatus == OK ) ) { fieldType = fieldDescription[ fieldIdx ].FieldType; fieldName = fieldDescription[ fieldIdx ].FieldName; Это — обращение к таблице, в результате которого будет вызван метод, зависящий от типа поля: он просто выбирается в таблице объектов. field[ fieldType ].ReadAndPrint( fieldName, fileStatus ); } Помните первоначальные 34 строки псевдокода табличного поиска, содержаще# го оператор case? Если вы замените оператор case таблицей объектов, то это весь код, который вам нужен для обеспечения той же функциональности. Невероят# но, но это также весь код, необходимый для замены всех 20 отдельных методов, применяемых при логическом подходе. Более того, если описания сообщений читаются из файла, то новые типы сообщений не потребуют изменений кода, если только не будут содержать новых типов полей. Вы можете использовать такой подход в любом объектно#ориентированном язы# ке. Он менее подвержен ошибкам, легче в сопровождении и эффективнее длин# ных выражений if, операторов case или огромного количества подклассов. Сам факт, что проект использует наследование и полиморфизм, не делает его хорошим проектом. Механический объектно#ориентированный дизайн, описан# ный в разделе «Объектно#ориентированный подход», потребовал бы такого же большого объема кода, как и механический функциональный дизайн, а может, и больше. Такой подход скорее усложнил бы решение, чем упростил. В данном слу# чае основная суть проектного решения не в объектной и не в функциональной ориентации, а в использовании хорошо продуманной таблицы поиска. > > ГЛАВА 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. |