Инвариантные фрагменты кода Оптимизация инвариантных фрагментов кода тесно связана с проблемой оптимального программирования циклов. Внутри цикла могут встречаться выражения, фрагменты которых никак не зависят от управляющей переменной цикла. Их называют инвариантными фрагментами кода. Современные компиляторы часто определяют наличие таких фрагментов и выполняют их автоматическую оптимизацию. Такое возможно не всегда, и иногда производительность программы зависит целиком от того, как запрограммирован цикл. В качестве примера рассмотрим следующий фрагмент программы (язык Turbo Pascal): for i := 1 to n do begin ... for k := 1 to p do for m := 1 to q do begin a[k, m] := Sqrt(x * k * m - i) + Abs(u * i - x * m + k); b[k, m] := Sin(x * k * i) + Abs(u * i * m + k); end; ... am := 0; bm := 0; for k := 1 to p do for m := 1 to q do begin am := am + a[k, m] / c[k]; bm := bm + b[k, m] / c[k]; end; end; Здесь инвариантными фрагментами кода являются слагаемое Sin(x * k * i) в первом цикле по переменной m и операция деления на элемент массива c[k] во втором цикле по m. Значения синуса и элемента массива не изменяются в цикле по переменной m, следовательно, в первом случае можно вычислить значение синуса и присвоить его вс переменной, которая будет использоваться в выражении, находящемся внутри цикла. Во втором случае можно выполнить деление после завершения цикла по m. Таким образом, можно существенно сократить количество трудоёмких арифметических операций. [править] Приоритеты оптимизации
#include <stdio.h> int binaryFounder(int*,int,int,int,int*);
int main(void) {int ar[100],n,res=-1,i,j,buf,val,arind[100]; scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&ar[i]); printf("Enter searching value:"); scanf("%d",&val); for(i=0;i<n;i++) arind[i]=i; for(i=0;i<n-1;i++) for(j=i+1;j<n;j++) if(ar[i]>ar[j]) {buf=ar[i]; ar[i]=ar[j]; ar[j]=buf; buf=arind[i]; arind[i]=arind[j]; arind[j]=buf;} binaryFounder(ar,0,n-1,val,&res); if (res==-1) printf("Not found"); else printf("Found in position %d",arind[res]); return 0;}
int binaryFounder(int ar[],int left,int right,int val,int* res) {int kar=(left+right)/2; if (*res!=-1) return 0; if (left>right) return 0; if (ar[kar]==val) *res=kar; if (ar[kar]<val) binaryFounder(ar,kar+1,right,val,res); if (ar[kar]>val) binaryFounder(ar,left,kar-1,val,res);}
Пример ввода: 5 1 2 3 4 5 4 Пример вывода: Found in position 3 //считаем с 0
Оптимизация инвариантных фрагментов кода тесно связана с проблемой оптимального программирования циклов. Внутри цикла могут встречаться выражения, фрагменты которых никак не зависят от управляющей переменной цикла. Их называют инвариантными фрагментами кода. Современные компиляторы часто определяют наличие таких фрагментов и выполняют их автоматическую оптимизацию. Такое возможно не всегда, и иногда производительность программы зависит целиком от того, как запрограммирован цикл. В качестве примера рассмотрим следующий фрагмент программы (язык Turbo Pascal):
for i := 1 to n do
begin
...
for k := 1 to p do
for m := 1 to q do
begin
a[k, m] := Sqrt(x * k * m - i) + Abs(u * i - x * m + k);
b[k, m] := Sin(x * k * i) + Abs(u * i * m + k);
end;
...
am := 0;
bm := 0;
for k := 1 to p do
for m := 1 to q do
begin
am := am + a[k, m] / c[k];
bm := bm + b[k, m] / c[k];
end;
end;
Здесь инвариантными фрагментами кода являются слагаемое Sin(x * k * i) в первом цикле по переменной m и операция деления на элемент массива c[k] во втором цикле по m. Значения синуса и элемента массива не изменяются в цикле по переменной m, следовательно, в первом случае можно вычислить значение синуса и присвоить его вс переменной, которая будет использоваться в выражении, находящемся внутри цикла. Во втором случае можно выполнить деление после завершения цикла по m. Таким образом, можно существенно сократить количество трудоёмких арифметических операций.
[править] Приоритеты оптимизации
#include <stdio.h>
int binaryFounder(int*,int,int,int,int*);
int main(void)
{int ar[100],n,res=-1,i,j,buf,val,arind[100];
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&ar[i]);
printf("Enter searching value:");
scanf("%d",&val);
for(i=0;i<n;i++)
arind[i]=i;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(ar[i]>ar[j])
{buf=ar[i];
ar[i]=ar[j];
ar[j]=buf;
buf=arind[i];
arind[i]=arind[j];
arind[j]=buf;}
binaryFounder(ar,0,n-1,val,&res);
if (res==-1)
printf("Not found");
else
printf("Found in position %d",arind[res]);
return 0;}
int binaryFounder(int ar[],int left,int right,int val,int* res)
{int kar=(left+right)/2;
if (*res!=-1)
return 0;
if (left>right)
return 0;
if (ar[kar]==val)
*res=kar;
if (ar[kar]<val)
binaryFounder(ar,kar+1,right,val,res);
if (ar[kar]>val)
binaryFounder(ar,left,kar-1,val,res);}
Пример ввода:
5
1
2
3
4
5
4
Пример вывода:
Found in position 3 //считаем с 0