递归Fibonacci函数在C中的执行时间比等效的Nim和Pascal代码慢

62o28rlo 于 2023-08-03 发布在其他

关注(0)|答案(2)|浏览(72)

At this link有一个关于用各种语言编写的递归斐波那契函数的基准测试。我尝试了一些示例（特别是Nim和Pascal），并验证了执行时间与该页面上的相同。然后我尝试了下面的C版本（我很感兴趣，因为我正在学习C和C++），我很困惑地看到，在我的机器（旧的i5桌面）上，时间是~17秒，而在基准测试页面上是~7秒！！我使用了与该页面上所述相同的编译器标志（即-O3和release target），但执行时间要慢得多。我在Microsoft Windows上使用Mingw 64，代码为：：blocks。
我不敢相信尼姆和帕斯卡跑得更快。毕竟，如果我没有弄错的话，Nim编译成了C！
我做错了什么？
代码为：

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>

static uint64_t fib(uint64_t n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

int main() {
    time_t t1 = time(NULL);
    uint64_t res = fib(47);
    time_t t2 = time(NULL);
    printf("%llu seconds\n", t2 - t1);
    return 0;
}

字符串

来源：https://stackoverflow.com/questions/76611371/execution-time-of-recursive-fibonacci-function-is-slower-in-c-than-equivalent-ni

2条答案

按热度按时间

g2ieeal71#

您没有做错任何事情，您的系统恰好具有比基准机器更慢的CPU。在PC上运行其他语言的示例可能会产生更长的时间。同样的代码在我的M2 Macbook上运行大约8秒。
这个简单的递归Fibonacci实现是衡量函数调用性能的经典方法。正如您在README文件中看到的，静态类型编译语言的性能非常相似。测试的编译器中没有一个与fib函数中的模式匹配，以生成运行时间不到1微秒的替代算法的代码。
下面是一个修改后的版本，除了输出更精确的时间外，还可以输出结果，并接受命令行参数：

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>
#include <time.h>

static uint64_t fib(uint64_t n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

static double time_microseconds(void) {
#ifdef TIME_UTC
    struct timespec ts;
    timespec_get(&ts, TIME_UTC);
    return ts.tv_sec * 1000000.0 + ts.tv_nsec / 1000;
#elif 1
    return clock() * 1000000.0 / CLOCKS_PER_SEC;
#else
    return time(NULL) * 1000000.0;
#endif
}

static void test_fib(uint64_t n) {
    double t1 = time_microseconds();
    uint64_t res = fib(n);
    double t2 = time_microseconds();
    printf("fib(%"PRIu64") = %"PRIu64"  %g seconds\n", n, res, (t2 - t1) / 1000000.0);
}

int main(int argc, char *argv[]) {
    if (argc > 1) {
        for (int i = 1; i < argc; i++)
            test_fib(strtoul(argv[i], NULL, 0));
    } else {
        test_fib(47);
    }
    return 0;
}

字符串
我的M2笔记本电脑上的输出：

chqrlie@macbook ~/dev/stackoverflow > ./230704-fib 10 20 30 {40..47}
fib(10) = 55  1e-06 seconds
fib(20) = 6765  4.5e-05 seconds
fib(30) = 832040  0.00471 seconds
fib(40) = 102334155  0.29385 seconds
fib(41) = 165580141  0.453271 seconds
fib(42) = 267914296  0.728588 seconds
fib(43) = 433494437  1.18065 seconds
fib(44) = 701408733  1.91074 seconds
fib(45) = 1134903170  3.08946 seconds
fib(46) = 1836311903  5.02768 seconds
fib(47) = 2971215073  8.17137 seconds

型
下面的更快版本在不到一微秒的时间内对所有测试值产生相同的结果，但如果在其他语言中以这种方式实现，也会产生相同的结果：

static uint64_t fib_fast(uint64_t n) {
    uint64_t a = 0, b = 1, c = n;
    while (n --> 1) {
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}

型

赞(0）回复(0）举报 2023-08-03

70gysomp2#

我不敢相信尼姆和帕斯卡跑得更快。毕竟，如果我没有弄错的话，Nim编译成了C！
关于这个具体的问题，你可以在 *drujensen的 * github仓库的issues区域找到解释：The fastest languages are cheating #119

赞(0）回复(0）举报 2023-08-03