Настройка кода
Существует большое количество различных способов уменьшить время исполнения, – естественно, после того как критическое место в программе найдено. Ниже мы приводим ряд рекомендаций в этой области, однако надо всегда помнить, что применять что бы то ни было надо с осторожностью и после каждого изменения непременно выполнять возвратные тесты, чтобы быть уверенными в корректности работы кода. Помните, что хорошие компиляторы сами выполняют некоторые из описываемых усовершенствований, и вы можете только запутать программу. Что бы вы ни применяли, после каждого изменения выполняйте замеры времени.
Объединяйте общие выражения.
Если некоторое сложное вычисление встречается в вашем коде несколько раз, выполните его единожды и запомните результат. Например, в главе 1 мы показали вам макрос, который вычислял расстояние, дважды подряд вызывая sqrtс одинаковыми значениями; в результате вычисление выглядело так:
? sqrt(dx*dx + dy*dy) + ((sqrt(dx*dx + dy*dy) > 0)?…)
Вычислите корень один раз, а дальше используйте полученное значение. Если вычисление выполняется в цикле, но при этом не зависит ни от каких параметров, изменяющихся в этом цикле, вынесите его из цикла и подставляйте далее его значение:
for (i = 0; i < nstarting[cj;
Можно заменить на:
n = nstarting[c];
for (i = 0; i < n; i++) {
Заменяйте дорогостоящие операции на более дешевые.
Термин понижение мощности (reduction of strength) относится к такому виду оптимизации, как замена дорогостоящей операции на более дешевую. Когда-то давно этот термин обозначал в основном замену умножения сложениями или сдвигами, правда, сейчас непосредственно на этом вы вряд ли что-то выгадаете. Однако деление и взятие остатка гораздо медленнее умножения, так что код можно несколько улучшить, заменив деление умножением на обратное значение, а взятие остатка при делителе, являющемся степенью двойки, можно заменить использованием битовой маски.
Замена индексации массивов указателями в С или C++ может ускорить код, правда, большинство компиляторов выполняет это автоматически. Может быть вполне выгодной и замена вызова функции простым непосредственным вычислением. Расстояние на плоскости определяется по формуле sqrt(dx*dx+dy*dy), так что для выяснения того, какая из двух точек находится дальше, в принципе надо вычислить два квадратных корня. Но это решение можно принять и сравнивая квадраты расстояний, то есть:
if (dx1*dx1+dy1*dy1 < dx2*dx2+dy2*dy2) ….
Даст тот же результат, но без вычисления корней.
Другой пример дают сравнения строк с текстовыми образцами, вроде нашего спам-фильтра или grep. Если образец начинается с буквы, то по всему введенному тексту осуществляется быстрый поиск этой буквы, и если вхождений не обнаружено, то более сложные механизмы поиска вообще не вступают в дело.
Избавьтесь от циклов или упростите их. Организация и исполнение цикла требуют некоторых временных затрат, так что, если тело цикла не слишком длинно и выполняется не слишком много раз, может оказаться более эффективным избавиться от цикла вообще и выписать все действия последовательно. Таким образом, например:
for (i =0; i < 3; i++) [i] + cfi];
Станет выглядеть так:
При этом мы избавляемся от затрат на организацию цикла, особенно от ветвления, которое может существенно замедлять современные процессоры, прерывая поток исполнения.