程式的執行速度

[gwliao (gwliao)]

剛剛在程式版看到有人討論程式的執行速度, 很多記憶湧上心頭.  Q_Q
討論著以前的舊技巧,  都已經2005年, 還在懷念DOS時期的舊東西,
10幾年了, 世界沒有長進嗎?  有, 只是有人沒注意


下面是我的碩一幹的缺德事, 一個O(N^4)的程式,
run time把一起修課的同學和老師嚇到  XD
三年前的機器和compiler都比現在還落後,
當時的差距有到120倍以上, ( Max=128, 別人都20~30min, 我10秒不到 )
現在只有1X倍而已 :O 世界進步真快.


看誰有空,有興趣玩玩,
ft2和ft3都是畸巧淫技而已(尤其是ft3), 玩玩就好.
但是ft1是正常人想的出來的方法.
(ft1是compiler沒辦法幫忙的, compiler有可能用其他的方法加快程式)


Max=256 , 比ft3快, 送音樂CD一片 (Horowitz彈的拉曼三)
Max=1024, 比ft2快, 送音樂CD一片 (四季,小提琴協奏曲,仿古樂器演奏)
Max=1024, 比ft1快, 這是正常人想的到, 所以只能送一隻原子筆,保證30元以下 :P
Max=1024, 比ft 快, 保安,保安....有瘋子!     :O

要玩的人別花太多時間, 我從ft到ft3只花了7 hr,
對! 一個晚上, 黑夜到清晨 Orz 鳥作業一個, run time大到沒辦法debug (等到睡著了)
ft2和ft3, 想得到就想得到, 想不到的就不要想了,
因為你沒有經驗, 所以沒辦法用這些畸巧淫技, 專心弄演算法吧 XD


PS: 除了Max=256外, 其他的run time都是預估值,誤差約在10~20%.
-----------------------------------------------------------------------------
我的機器
Max=256
ft3:  32.386s
ft2:  69.778s
ft1:  74.331s
ft : 768.520s

Max=512
ft3: 2816
ft2:  716
ft1: 5632
ft :12288

Max=1024
ft3:  75776
ft2:  11418
ft1:  23552
ft : 197053
-------------------
eda4.ee.ntu.edu.tw
Max=256
ft3:  14.64user
ft2:  20.61user
ft1:  63.82user
ft : 490.90user
Max=512
ft3: 1136
ft2:  588
ft1: 1233
ft:  8125
-----------------------------------------------------------------------------
code:
#include <iostream>
#include <math.h>
using namespace std;

double  *data1=NULL;
double  *data2=NULL;
const double PI=3.141592654;

void ft(int Max) {
int i,j,x,y;
double f;

for(x=0;x<Max;x++)
for(y=0;y<Max;y++)
        data2[x*Max+y]=0;

for(x=0;x<Max;x++) {
        for(y=0;y<Max;y++)
        for(i=0;i<Max;i++)
        for(j=0;j<Max;j++)
                data2[x*Max+y]=data2[x*Max+y]+cos(2*PI*(x*i/Max+y*j/Max))*
                               data1[i*Max+j]/(Max*Max);
        cout<<"Shit "<<x<<"\n";
        }
}

int main(void) {
int Max=256;

data1=new double[Max*Max];
data2=new double[Max*Max];

for(int x=0;x<Max;x++)
for(int y=0;y<Max;y++)
        data1[x*Max+y]=rand()%256;
ft(Max);
}

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.112.230.224
推 moonshade:獎品我都有了...沒有吸引力Orz
推 Donnie:是正版的片子嗎？
推 gwliao:當然是正版CD  :O
→ gwliao:月貓, 你聽古典樂,又有蠻多CD, 當然這兩片都有!
→ gwliao:不然還有侯捷的簽名書,不過那是"贈與光萬"的耶 XD
推 bluetai:跟access memory 有關的程式~
→ bluetai:不是跟 machine 有很大的關係嗎?
推 gwliao:是啊, ft1跟ft2是奇巧,  ft3是淫技 Orz
→ gwliao:ft3是減少memory acces, 但不大有笑 :(
推 bluetai:oh~我耍寶了~ 我看錯程式碼了~ :p
→ gwliao:因為只是初估cache size後的程式.
推 bluetai:我以為是x[i]=ooo,x[i+1]=xxx,x[i+2]=...
→ gwliao:memory acces的次數是固定的, 要用cache減少 :)
推 moonshade:簽名書聽起來不賴XD
→ bluetai:你拿書來我幫你簽~ XD