Главная - Литература

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 [139] 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294

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

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

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

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

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



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

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

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

В некоторых случаях подойдет любой из нескольких вари-

втъных подходах к выбору задачей проектирования является выбор одного из

альтернативных способов про- нескольких хороших вариантов для этого конкретного слу-ектирования см. главу 5. чая. Не слишком волнуйтесь по поводу выбора наилучше-

го. Как говорит Батлер Лемпсон, выдающийся инженер из Microsoft, лучше стремиться к хорошему решению и избегать неудач, чем пытаться найти наилучшее решение (Lampson, 1984).

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

18.5. Другие примеры табличного поиска

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

поиск ставок в таблице страхования: раздел 16.3;

применение таблиц решения для замены сложной логики: подраздел «Используйте таблицы решений для замены сложных условий» раздела 19.1;

расходы на страничную организацию памяти при табличном поиске: раздел 25.3;

комбинации логических значений (А или В или С): подраздел «Замена сложных выражений на обращение к таблице» раздела 26.1;

предварительное вычисление значения в таблице погашения ссуд: раздел 26.4.



Контрольный список: табличные методы

□ Рассмотрены ли табличные методы в качестве альтерна- Шр:Ш2ьмт/\Ш тивы сложной логике?

□ Рассмотрены ли табличные методы в качестве альтернативы сложным структурам с наследованием?

□ Рассмотрен ли вопрос размещения табличных данных отдельно от программы и их чтения во время выполнения, чтобы позволить обновлять данные без изменения кода?

□ Если доступ к таблице нельзя осуществить напрямую с помощью простого индекса массива (как в примере с возрастами), помещены ли вычисления ключа доступа в отдельный метод, а не разбросаны по всему коду?

Ключевые моменты

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

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

Другой основной вопрос состоит в выборе того, что конкретно будет помещено в таблицу.



0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 [139] 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294



0.0118