對演算法感興趣的我，一直想知道自己寫的程式的效能如何，所以這一次特別來瞭解演算法執行時間 (Algorithm Time of Execution)。同一流程可以由不同的演算法來達到同一效果，可是在效能方面或多或少就有差別了～
剛好寫了一個暴力法演算法，是一個RGB色彩空間，由256*256*256組成，我任意取了色彩空間中的一點(a, b, c)，想求出距離這點為r的點有哪些～
直接來看程式碼就可以瞭解：
/**
Theme: Algorithm Time of Execution
compiler: Dev C++ 4.9.9.2
Date: 102/06/07
Author: HappyMan
Blog: https://cg2010studio.wordpress.com/
*/
#include<iostream>
#include<cmath>
#include<iomanip>
#include<windows.h>
using namespace std;
int main(){
int a=5,b=6,c=7;
LARGE_INTEGER startTime,endTime,fre;
double times;
QueryPerformanceFrequency(&fre); //取得CPU頻率
QueryPerformanceCounter(&startTime); //取得開機到現在經過幾個CPU Cycle
//doing something
for(int x=0;x<256;x++){
for(int y=0;y<256;y++){
for(int z=0;z<256;z++){
if(pow((x-a),2.0)+pow((y-b),2.0)+pow((z-c),2.0)==pow(5,2.0))
// if((x-a)*(x-a)+(y-b)*(y-b)+(z-c)*(z-c)==5*5)
cout<<"(x,y,z)="<<x<<' '<<y<<' '<<z<<endl;
}
}
}
QueryPerformanceCounter(&endTime); //取得開機到程式執行完成經過幾個CPU Cycle
times=((double)endTime.QuadPart-(double)startTime.QuadPart)/fre.QuadPart;
cout << fixed << setprecision(20) << times << 's' << endl;
system("pause");
return 0;
}
以上表示求點(5,6,7)距離為5的點有哪些～
執行結果：
(x,y,z)=0 6 7
(x,y,z)=1 3 7
(x,y,z)=1 6 4
(x,y,z)=1 6 10
(x,y,z)=1 9 7
(x,y,z)=2 2 7
(x,y,z)=2 6 3
(x,y,z)=2 6 11
(x,y,z)=2 10 7
(x,y,z)=5 1 7
(x,y,z)=5 2 4
(x,y,z)=5 2 10
(x,y,z)=5 3 3
(x,y,z)=5 3 11
(x,y,z)=5 6 2
(x,y,z)=5 6 12
(x,y,z)=5 9 3
(x,y,z)=5 9 11
(x,y,z)=5 10 4
(x,y,z)=5 10 10
(x,y,z)=5 11 7
(x,y,z)=8 2 7
(x,y,z)=8 6 3
(x,y,z)=8 6 11
(x,y,z)=8 10 7
(x,y,z)=9 3 7
(x,y,z)=9 6 4
(x,y,z)=9 6 10
(x,y,z)=9 9 7
(x,y,z)=10 6 7
5.61081534692547730000s
請按任意鍵繼續 . . .
程式跑三層迴圈共256*256*256=16777216次，以函式四個pow函式來計算平方，跑了5.6秒。
接著不使用pow函式，改為直接乘開，依然有同上的結果，不過效能快非常多……跑了0.13秒。
…
0.13744428139998247000s
請按任意鍵繼續 . . .
這是以Visual Studio 2010編譯器跑出來的結果，後者快前者演算法約43倍呢！
若以Dev C++ 4.9.9.2編譯器跑的話，則分別為6.328秒和0.079秒，後者快前者演算法約80倍呢！
看來編譯器各有優缺，瞭解工具並善用工具看來非常重要呢！
看演算法的簡單想法即是浮點運算和整數運算效能差很大！要是能達到同樣的效果，效率越快當然就越好囉～此時不必殺雞用牛刀。
參考：計算程式執行時間 (Compute Time of Execution)。
發表留言