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

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

пользуется один и тот же элемент массива. Вот пример необязательного обращения к массиву:

Пример необязательного обращения к массиву внутри цикла (С++)

for ( discountType = 0; discountType < typeCount; discountType++ ) {

for ( discountLevel = 0; discountLevel < levelCount; discountLevel++ ) { rate[ discountLevel ] = rate[ discountLevel ] * discount[ discountType ];

При изменении индекса discountLevel по мере выполнения внутреннего цикла обращение к массиву discountf discountType J остается все тем же. Вы можете вынести его за пределы внутреннего цикла, и тогда у вас будет одно обращение к массиву на одну итерацию внешнего, а не внутреннего цикла. Вот оптимизированный код:

Пример вынесения обращения к массиву за пределы цикла (С++)

for ( discountType = 0; discountType < typeCount; discountType++ ) { thisDiscount = discount[ discountType ];

for ( discountLevel = 0; discountLevel < levelCount; discountLevel++ ) { rate[ discountLevel ] = rate[ discountLevel ] * thisDiscount;

Результаты:

Язык

Время выполнения Время выполнения кода до оптимизации оптимизированного кода

Экономия времени

32,1 34,5

18,3 17,0

Visual Basic

23,2 18,4

Примечание: тестирование выполнено для typeCount = 10 и levelCount =

100.

Как обычно, результаты зависят от конкретного компилятора.

Использование дополнительных индексов

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

Индекс длины строки

Примером использования дополнительного индекса может служить одна из форм представления строк. В языке С строки заканчиваются нулевым байтом. Что касается строк Visual Basic, то их длина хранится в начальном байте. Чтобы определить длину строки С, нужно начать с начала строки и продвигаться по ней, подсчитывая байты, до достижения нулевого байта. Для определения длины строки Visual Basic, нужно просто прочитать байт длины. Байт длины строки Visual Basic



- наглядный пример дополнения типа данных индексом, ускоряющим выполнение определенных операций, таких как вычисление длины строки.

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

Независимая параллельная структура индексации

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

Кэширование

Кэширование - это такой способ хранения нескольких значений, при котором значения, используемые чаще всего, получить легче, чем значения, используемые реже. Так, если программа случайным образом читает записи с диска, метод может хранить в кэше записи, считываемые наиболее часто. Получив запрос записи, метод проверяет, имеется ли запись в кэше. Если да, запись возвращается непосредственно из памяти, а не считьшается с диска.

Кэширование можно применять и в других областях. В программе обработки шрифтов Microsoft Windows узким местом было получение ширины символа при его отображении на экране. Кэширование ширины символа, использованного последним, позволило примерно вдвое ускорить отображение.

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

Пример метода, напрашивающегося на кэширование (Java)

double Hypotenuse( double sideA, double sideB ) {

return Math.sqrt( ( sideA * sideA ) + ( sideB * sideB ) );

Если вы знаете, что те же значения скорее всего будут переданы в метод повторно, их можно кэшировать:



Пример кэширования для предотвращения дорогих вычислений (Java)

private double cachedHypotenuse = 0; private double cachedSideA = 0; private double cachedSideB = 0;

public double Hypotenuse( double sideA, double sideB ) {

Присутствуют ли параметры треугольника в кэше? if ( ( SideA == cachedSideA ) && ( sideB == cachedSideB ) ) { return cachedHypotenuse;

Вычисление новой гипотенузы и ее кэширование.

cachedHypotenuse = Math.sqrt( ( sideA * sideA ) + ( sideB * sideB ) ); cachedSideA = sideA; cachedSideB = sideB;

return cachedHypotenuse;

Вторая версия метода сложнее и объемнее первой, поэтому она должна обосновать свое право на жизнь быстродействием. Многие схемы кэширования предполагают кэширование более одного элемента, и с ними связаны еще большие за-

траты. Вот быстродействие двух версий метода:

Время выполнения

Время выполнения

оптимизированного

Экономия

Соотношение

Язык

кода до оптимизации

кода

времени

быстродействия

4,06

1,05

Java

2,54

1,40

Python

8,16

4,17

Visual Basic

24,0

12,9

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

Польза кэширования зависит от относительной стоимости обращения к кэширо-ванному элементу, создания некэшированного элемента и сохранения нового элемента в кэше. Она также зависит от числа запросов кэшированной информации. Иногда она может зависеть и от аппаратного кэширования. В целом чем дороже генерирование нового элемента и чем чаще запрашивается та же самая информация, тем выгоднее кэширование. Чем дешевле обращение к кэшированно-му элементу и сохранение новых элементов в кэше, тем выгоднее кэширование. Как и другие методики оптимизации, кэширование усложняет код и часто оказывается источником ошибок.



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.0075