我正在比较两个梯度下降实现之间的差异，我猜测在编译器优化后，这两个版本的算法都应该是等价的。
令我惊讶的是，递归版本要快得多。在任何一个版本中，甚至是在我测量时间的方式上，我都没有找到任何实际的缺陷。请问您能提供一些见解吗？
以下是我的代码：
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <stdint.h>
double f(double x)
{
return 2*x;
}
double descgrad(double xo, double xnew, double eps, double precision)
{
// printf("step ... x:%f Xp:%f, delta:%f\n",xo,xnew,fabs(xnew - xo));
if (fabs(xnew - xo) < precision)
{
return xnew;
}
else
{
descgrad(xnew, xnew - eps*f(xnew), eps, precision);
}
}
double descgraditer(double xo, double xnew, double eps, double precision)
{
double Xo = xo;
double Xn = xnew;
while(fabs(Xn-Xo) > precision)
{
//printf("step ... x:%f Xp:%f, delta:%f\n",Xo,Xn,fabs(Xn - Xo));
Xo = Xn;
Xn = Xo - eps * f(Xo);
}
return Xn;
}
int64_t timespecDiff(struct timespec *timeA_p, struct timespec *timeB_p)
{
return ((timeA_p->tv_sec * 1000000000) + timeA_p->tv_nsec) -
((timeB_p->tv_sec * 1000000000) + timeB_p->tv_nsec);
}
int main()
{
struct timespec s1, e1, s2, e2;
clock_gettime(CLOCK_MONOTONIC, &s1);
printf("Minimum : %f\n",descgraditer(100,99,0.01,0.00001));
clock_gettime(CLOCK_MONOTONIC, &e1);
clock_gettime(CLOCK_MONOTONIC, &s2);
printf("Minimum : %f\n",descgrad(100,99,0.01,0.00001));
clock_gettime(CLOCK_MONOTONIC, &e2);
uint64_t dif1 = timespecDiff(&e1,&s1) / 1000;
uint64_t dif2 = timespecDiff(&e2,&s2) / 1000;
printf("time_iter:%llu ms, time_rec:%llu ms, ratio (dif1/dif2) :%g\n", dif1,dif2, ((double) ((double)dif1/(double)dif2)));
printf("End. \n");
}
我正在使用gcc 4.5.2在Ubuntu 11.04上编译，选项如下： gcc grad.c -O3 -lrt -o dg
我的代码输出为：
Minimum : 0.000487
Minimum : 0.000487
time_iter:127 ms, time_rec:19 ms, ratio (dif1/dif2) :6.68421
End.
我读到了一个帖子，也提到递归版本的算法比迭代版本更快。那里的解释是递归版本使用堆栈，而另一个版本使用一些向量，堆上的访问会减慢迭代版本的速度。但在这种情况下（在我最好的理解中），我只是在两种情况下都使用堆栈。
我是否漏掉了什么？有什么明显的东西我没有看到吗？我的计时方式有问题吗？有什么见解？
编辑： 在评论中解决了谜团。正如@TonyK所说，printf的初始化减慢了第一次执行的速度。很抱歉我错过了这个显而易见的事情。
顺便说一下，代码编译没有警告。我认为“return descgrad（…”不必要，因为停止条件发生在之前。
if语句为false时，descgrad的返回语句在哪里？这段代码不应该编译。 - Christopher Neylanreturn，进行了足够数量的迭代，并从基准测试中删除了printf后，两个时间非常相似。链接 - Mike Seymour