c++ - 为什么函数的递归版本比 C 中的迭代版本更快？

Question

我正在检查梯度下降的两种实现方式之间的区别，我的猜测是在编译器优化之后，两个版本的算法将是等效的。

令我惊讶的是，递归版本明显更快。我没有丢弃任何版本的实际缺陷，甚至没有丢弃我测量时间的方式。你们能给我一些见解吗？

这是我的代码:

#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");
}

我正在使用以下选项在 Ubuntu 11.04 上使用 gcc 4.5.2 进行编译: 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.

我读到一个线程，它也询问算法的递归版本比迭代版本更快。那里的解释是，作为使用堆栈的递归版本和使用一些 vector 的另一个版本，堆上的访问正在减慢迭代版本。但在这种情况下(据我所知)我只是在两种情况下都使用了堆栈。

我错过了什么吗？有什么我没有看到的明显的东西吗？我测量时间的方法错了吗？有什么见解吗？

编辑:谜团在评论中解开。正如@TonyK 所说，printf 的初始化减慢了第一次执行的速度。抱歉，我错过了那明显的事情。

顺便说一句，代码编译正确，没有警告。我不认为“return descgrad(..”是必要的，因为之前发生了停止条件。

Answer 1

我已经在本地编译并运行了您的代码。将 printf 移到定时 block 之外，使两个版本每次都在 ~5ms 内执行。

因此，您在时间安排上的一个主要错误是您测量了 printf 的复杂野兽，它的运行时间使您实际尝试测量的代码相形见绌。

我的 main()-函数现在看起来像这样:

int main() {
    struct timespec s1, e1, s2, e2;

    double d = 0.0;

    clock_gettime(CLOCK_MONOTONIC, &s1);
    d = descgraditer(100,99,0.01,0.00001);
    clock_gettime(CLOCK_MONOTONIC, &e1);
    printf("Minimum : %f\n", d);

    clock_gettime(CLOCK_MONOTONIC, &s2);
    d = descgrad(100,99,0.01,0.00001);
    clock_gettime(CLOCK_MONOTONIC, &e2);
    printf("Minimum : %f\n",d);

    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");
}