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

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

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

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

С++ 3,69 2,97 19%

С* 2,27 1,97 13%

Java 4,13 2,35 43%

Примечание: тестирование выполнено для случая rateCount = 100.

За исключением компилятора Java экономия времени не так уж и велика, поэтому при первоначальном кодировании вы можете применить любую методику, улучшающую удобочитаемость кода, и отложить работу над быстродействием на потом.

Сигнальные значения

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

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

Пример проверки сложного условия цикла (С#)

found = FALSE; i = 0;

- Проверка сложного условия.

->while ( ( !found ) && ( i < count ) ) { if ( item[ i ] testValue ) { found = TRUE;

else { i++;

if ( found ) {

При каждой итерации этого цикла проверяются два условия: Ifound и i < count. Проверка Ifound служит для определения того, найден ли нужный элемент. Проверка i < count нужна для предотвращения выхода за пределы массива. Кроме того, внутри цикла проверяются отдельные значения массива itemfj, так что на самом деле при каждой итерации цикла выполняются три проверки.



Этот вид циклов поиска позволяет объединить три проверки и выполнять при каждой итерации только одну проверку: для этого нужно поместить в конце диапазона поиска «сигнальное значение», завершающее цикл. В нашем случае можно просто присвоить искомое значение элементу, располагающемуся сразу после окончания диапазона поиска (объявляя массив, не забудьте выделить место для этого элемента). Далее вы проверяете по очереди каждый элемент: если вы достигаете сигнального значения, значит, нужного вам значения в массиве нет. Вот соответствующий код:

Пример использования сигнального значения для ускорения цикла (С#)

Установка сигнального значения с сохранением начальных значений. initialValue = item[ count ];

- Не забудьте зарезервировать в конце массива место для сигнального значения.

->item[ count ] = testValue;

i - 0;

while ( item[ i ] != testValue ) { i++;

Обнаружено ли значение? if ( i < count ) {

Если item содержит целые числа, выгода может быть весьма существенной:

Время выполнения Время выполнения оптимизированного Экономия Соотношение Язык кода до оптимизации кода времени быстродействия

С* 0,771 0,590 23% 1,3:1

Java 1,63 0,912 44% 2:1

Visual Basic 1,34 0,470 65% 3:1

Примечание: поиск выполнялся в массиве из 100 целых чисел.

Результаты, полученные для Visual Basic, особенно впечатляют, но и остальные тоже очень неплохи. Однако при изменении типа массива результаты также изменяются. Если item включает числа с плавающей запятой, результаты таковы:

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

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

С* 1,351 1,021 24%

Java 1,923 1,282 33%

Visual Basic 1,752 1,011 42%

Примечание: поиск выполнялся в массиве из 100 четырехбайтовых чисел с плавающей запятой.



Как обычно, многое зависит от языка.

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

Вложение более ресурсоемкого цикла В менее ресурсоемкий

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

Пример вложенного цикла, который можно улучшить (Java)

for ( column = 0; column < 100; column++ ) { for ( row = 0; row < 5; row++ ) { sum = sum + table[ row ][ column ];

Ключ к улучшению цикла в том, что внешний цикл состоит из гораздо большего числа итераций, чем внутренний. С выполнением любого цикла связаны накладные расходы: в начале цикла индекс должен быть инициализирован, а при каждой итерации - увеличен и проверен. Общее число итераций равно 100 для внешнего цикла и 100 * 5 = 500 для внутреннего цикла, что дает в сумме 600 итераций. Просто поменяв местами внешний и внутренний циклы, вы можете снизить число итераций внешнего цикла до 5, тогда как число итераций внутреннего цикла останется тем же. В итоге вместо 600 итераций будут выполнены только 505. Можно ожидать, что перемена циклов местами приведет примерно к 16%-ому улучшению: (600 - 505) / 600 = 16%. На самом деле результаты таковы:

Язык

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

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

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

4,75

3,19

Java

5,39

3,56

4,16

3,65

Python

3,48

3,33

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

Снижение стоимости операций

Под снижением стоимости (strength reduction) понимают замену дорогой операции на более дешевую, например, умножения на сложение. Иногда внутри цикла выполняется умножение индекса на какие-то другие значения. Сложение обычно выполняется быстрее, чем умножение, и, если вы можете вычислить то же число.



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