说真的,这个问题搞得我怀疑人生,至我写这篇博文时,我还是没有相通
首先这个问题来自于一道acm,这道题是一道动态规划,于是我用了递归,下面是递归函数的代码
int search(int day_num,int this_day,int n)
{
if(day_num==day-1)
{
int results=0;
for(int i=n;i<num;i++)
{
results+=a[i];
}
return this_day+results;
}
if(n==num-1)
{
if(day_num==day-2)
{
return this_day*a[n];
}
return 0;
}
if(this_day==0)
{
int debug_a=search(day_num,this_day+a[n],n+1);
return debug_a;
}
else
{
int debug_a=search(day_num,this_day+a[n],n+1);
int debug_b=this_day*search(day_num+1,a[n],n+1);
return MAX(debug_a,debug_b);
}
}
最后几行我为了方便调试,加上了几个变量。最后提交代码的时候也一起提交了,也过了。
不过后来我想了一下还是把变量去掉再提交吧。于是改成了这样:
if(this_day==0)
{
return search(day_num,this_day+a[n],n+1);
}
else
{
return MAX(search(day_num,this_day+a[n],n+1),this_day*search(day_num+1,a[n],n+1));
}
神奇的事情发生了,居然超时了。
?????
我真的百思不得其解,明明是优化了代码,为啥反而会超时????
看了一下oj的说明,用以下参数分别编译两份代码
-static -w -O2 -DONLINE_JUDGE -std=c++0x
之后拖进ida进行分析。
有局部变量:
无局部变量:
为了方便,只截下了表示最后那几行代码的片段
两段代码编译出来的差别之大让我无法相信。。。。
多的不说,就这一段,没有局部变量编译出来反而语句多了很多,而且整个函数的逻辑也变了一些。
而又局部变量的那一段整个函数的逻辑没有大的改变,而且这一段看起来也简介很多。
留坑,以后有机会会研究一下
如果MAX是个粗制滥造的宏(比如#define MAX(a,b) ((a)>(b)?(a):(b))这样)的话,怕是被展开成了多次递归调用了。
居然还有这种无聊的设定吗。。。。。不是很懂计算机玄学
#define只是简单替换,你可以看看生成的预编译代码……
如果真的像我说的那样你的预编译后的代码多半是
return search(day_num,this_day+a[n],n+1) > this_day*search(day_num+1,a[n],n+1)
? search(day_num,this_day+a[n],n+1)
this_day*search(day_num+1,a[n],n+1);
所以我后来再也没用过#define来定义函数
不过用得好的话很酷炫,Linux和GNU套件很多源码里有这玩意儿编译期预生成函数
有趣