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

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

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

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

Экономия

Язык

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

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

времен и

9,66

5,97

Java

17,0

12,3

2,45

1,50

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

Недостатки системных методов

Системные методы дороги и часто обеспечивают избыточную точность. Например, большинство системных математических методов написаны с тем расчетом, чтобы космонавт, отправившийся на Луну, прилунился с точностью ±2 фута. Если вам не нужна такая точность, нет смысла тратить на нее время.

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

Пример метода, возвращающего примерное значение двоичного логарифма (С+ч-)

unsigned int Log2( unsigned int x ) {

if ( X < 2 ) return 0

if ( x < 4 ) return 1

if ( X < 8 ) return 2

if ( X < 16 ) return 3

if ( X < 32 ) return 4

if ( X < 64 ) return 5

if ( X < 128 ) return 6

if ( X < 256 ) return 7

if ( X < 512 ) return 8

if ( X < 1024 ) return 9

if ( X < 2147483648 ) return 30; return 31 ;

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

Язык

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

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

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

кода

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

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

9,66

0,662

15:1

Java

17,0

0,882

20:1

2,45

3,45

-41%



Большинство так называемых «трансцендентных» функций разработано для наихудшего случая, т. е, внутри себя они даже целочисленный аргумент преобразуют в число с плавающей запятой с удвоенной точностью. Обнаружив вызов такой функции в проблемном фрагменте кода, уделите ей самое пристальное внимание, если, конечно, вам не нужна подобная точность.

Но вернемся к нашему методу. Еще один вариант его оптимизации основан на том факте, что деление на 2 аналогично операции сдвига вправо. Двоичный логарифм числа равен количеству операций деления на 2, которое можно выполнить над этим числом до получения нулевого значения. Вот как выглядит соответствующий код:

Пример альтернативного метода, определяющего примерное значение двоичного логарифма с использованием оператора сдвига вправо (С++)

unsigned int Log2( unsigned int x ) { unsigned int i = 0; while ( ( X = ( x » 1 ) ) != 0 ) { i++;

return i ;

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

Этот метод выполняется примерно на 350% дольше, чем более длинная предыдущая версия (2,4 и 0,66 секунды соответственно), но он быстрее, чем первый оптимизированный метод, и легко адаптируется к 32-, 64-разрядным и другим средам.

Этот пример ясно показывает, насколько полезно продолжать поиск после нахождения первого успешного вида оптимизации. Первый вид оптимизации привел к приличному повышению быстродействия на 30-40%, но это не идет ни в какое сравнение с результатами второго и третьего видов оптимизации.

Использование констант корректного типа

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

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

X = 5 i = 3.14



и требует преобразований типов. Во втором случае преобразования типов не нужны:

X = 3.14 i = 5

Результаты в очередной раз указывают на большие различия между компиляторами:

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

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

оптимизированного Экономия Соотношение

Язык

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

кода

времени

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

1,11

0,000

100%

Не поддается

измерению

1,49

1,48

<1%

Java

1,66

1,11

1,5:1

Visual Basic

0,721

0,000

100%

Не поддается

измерению

0,872

0,847

Предварительное вычисление результатов

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

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

Например, работая над игрой «звездные войны», програм-мисты сначала вычисляли коэффициенты гравитации для щщт разных расстояний от Солнца. Эти вычисления были ресур- ттт0. соемкими и снижали производительность программы. Однако число разных расстояний, используемых в игре, было небольшим, поэтому разработчики в итоге вычислили коэффициенты гравитации предварительно и сохранили их в массиве из 10 элементов. Получение коэффициентов из массива оказалось гораздо более быстрым, чем их вычисление.

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

Пример сложного выражения, которое можно вычислить предварительно (Java)

double ComputePayment( long loanAmount, int months,



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