Методы оптимизации. Исключение лишних вычислений

Андрей Петров

© ООО ПАРСЕР

parserplus.com

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

Как правило, включение в цикл лишних вычислений происходит на первом этапе написания программного кода и является следствием недостаточной предварительной проработки алгоритма. Такая ошибка свойственна начинающим программистам или тем, кто не занимался ранее анализом и повышением производительности кода. Лишние вычисления – одна из наиболее существенных причин потери производительности. Казалось бы, что может быть проще, найти и исключить лишние вычисления? Действительно, несложно. Только не все программисты это делают. Почему? Наверное, потому, что стоит программисту убедиться в том, что его детище работает устойчиво и, может быть даже правильно, как он сразу считает процесс разработки законченным и думает о другом проекте. В некоторых случаях, когда время разработки критично и надо срочно выпускать продукт на рынок, отсутствие оптимизации оправдано. Но в долгосрочной перспективе неоптимизированные приложения скорее будут характеризовать разработчика скорее отрицательно, несмотря, возможно, на полезность и богатую функциональность приложения. Но… функциональность достаточно быстро устаревает, о неоптимизированность запоминается надолго, особенно, если есть с чем сравнивать.

Приведём простой пример.

#include "stdafx.h"

#include <math.h>

#include <time.h>

#include <sys/timeb.h>

int _tmain(int argc, _TCHAR* argv[])

{

clock_t start, finish;

double duration;

int N=10000;

int M=10000;

double PIM=3.1415926/10000.0;

double sum=0;

start = clock();

for(int i=0; i<N; i++)

{

for(int j=0;j<M;j++)

{

int index=i*M+j;

double res=sin(PIM*i)*sin(PIM*j);

sum+=res;

}

}

finish=clock();

duration = (double)(finish - start) / CLOCKS_PER_SEC;

printf( "\nProgram takes %10.4f seconds.\n", duration );

printf("sum = %f \n",sum);

return 0;

}

Эта программа выполняется за 5.7 секунд на компьютере с конфигурацией: Intel Core 2 Duo T6600 2200 ГГц, оперативная память 4 Гбb и 64-разрядной операционной системой Microsoft Windows 7.

В коде присутствуют лишние вычисления: неоправданно много лишних вычислений функции «синус» и много лишних умножений I на М при вычислении индекса матрицы. Избавитья от лишних вычислений можно запоминанием один раз посчитанного значения:

#include "stdafx.h"

#include <math.h>

#include <time.h>

#include <sys/timeb.h>

int _tmain(int argc, _TCHAR* argv[])

{

clock_t start, finish;

double duration;

int N=10000;

int M=10000;

double PIM=3.1415926/10000.0;

double sum=0;

start = clock();

for(int i=0; i<N; i++)

{

int index_i=i*M;

double sin_i=sin(PIM*i);

for(int j=0;j<M;j++)

{

int index=index_i+j;

double res=sin_i*sin(PIM*j);

sum+=res;

}

}

finish=clock();

duration = (double)(finish - start) / CLOCKS_PER_SEC;

printf( "\nProgram takes %10.4f seconds.\n", duration );

printf("sum = %f \n",sum);

return 0;

}

Оптимизированный вариант выполняется за 5.2 секунды.

Но и в этом коде еще много лишних вычислений. Действительно, при каждом значении переменной внешнего цикла i происходит вычисление всего набора значений синуса. Избавиться от лишних вычислений можно, сохраняя уже вычисленные значения функции «синус»:

#include "stdafx.h"

#include <math.h>

#include <time.h>

#include <sys/timeb.h>

int _tmain(int argc, _TCHAR* argv[])

{

clock_t start, finish;

double duration;

int N=10000;

int M=10000;

double PIM=3.1415926/10000.0;

double sum=0;

double all_sin[10000];

start = clock();

for(int i=0; i<N; i++)

{

all_sin[i]=sin(PIM*i);

}

for(int i=0; i<N; i++)

{

int index_i=i*M;

for(int j=0;j<M;j++)

{

int index=index_i+j;

double res=all_sin[i]*all_sin[j];

sum+=res;

}

}

finish=clock();

duration = (double)(finish - start) / CLOCKS_PER_SEC;

printf( "\nProgram takes %10.4f seconds.\n", duration );

printf("sum = %f \n",sum);

return 0;

}

Время выполнения этого варианта программы 0.2 секунды! Выигрыш составил более чем порядок величины!

Подведём итоги. За все приходится платить! В данном случае за увеличение быстродействие пришлось заплатить введением дополнительных переменных. Что в каждом конкретном случае выгодно – решать программисту.

Оставить комментарий.
Подпись
Код на картинке
© 2010-2016, ООО ПАРСЕР , Все права защищены.
Деловая сеть Санкт-Петербург и Ленинградская область. Жёлтые страницы, телефонный справочник и каталог компаний, товаров и услуг.
top.dp.ru