Just a Computer Graphics Studio & My Life

演算法感興趣的我,一直想知道自己寫的程式的效能如何,所以這一次特別來瞭解演算法執行時間 (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)

廣告

發表留言

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s

標籤雲

%d 位部落客按了讚: