作者gwliao (gwliao)
看板NTUGIEE_EDA
标题程式的执行速度
时间Sun Sep 4 06:50:40 2005
刚刚在程式版看到有人讨论程式的执行速度, 很多记忆涌上心头. 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
1F：推 moonshade:奖品我都有了...没有吸引力Orz 61.230.55.69 09/04
2F：推 Donnie:是正版的片子吗？ 140.112.5.74 09/04
3F：推 gwliao:当然是正版CD :O140.112.230.224 09/04
4F：→ gwliao:月猫, 你听古典乐,又有蛮多CD, 当然这两片都有!140.112.230.224 09/04
5F：→ gwliao:不然还有侯捷的签名书,不过那是"赠与光万"的耶 XD140.112.230.224 09/04
6F：推 bluetai:跟access memory 有关的程式~ 219.86.53.237 09/04
7F：→ bluetai:不是跟 machine 有很大的关系吗? 219.86.53.237 09/04
8F：推 gwliao:是啊, ft1跟ft2是奇巧, ft3是淫技 Orz140.112.230.224 09/04
9F：→ gwliao:ft3是减少memory acces, 但不大有笑 :(140.112.230.224 09/04
10F：推 bluetai:oh~我耍宝了~ 我看错程式码了~ :p 219.86.53.237 09/04
11F：→ gwliao:因为只是初估cache size後的程式.140.112.230.224 09/04
12F：推 bluetai:我以为是x[i]=ooo,x[i+1]=xxx,x[i+2]=... 219.86.53.237 09/04
13F：→ gwliao:memory acces的次数是固定的, 要用cache减少 :)140.112.230.224 09/04
14F：推 moonshade:签名书听起来不赖XD 61.217.194.122 09/04
15F：→ bluetai:你拿书来我帮你签~ XD 140.112.48.60 09/05