在C和python中,为什么递归四分法比迭代四分法快?

2024-03-29 14:40:58 发布

您现在位置:Python中文网/ 问答频道 /正文

我用Python编写了以下两个tetration函数:

def recur_tet(b, n):
    if n == 1:
        return(b)
    else:
        return(b ** recur_tet(b, n - 1))

def iter_tet(b, n):
    ans = 1
    for i in range(n):
        ans = b ** ans
    return(ans)

令人惊讶的是,递归版本的速度稍快:

python3> %timeit recur_tet(2,4)
1 µs ± 12.5 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

python3> %timeit iter_tet(2,4)
1.15 µs ± 14.5 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

我认为这可能与Python解释它的方式有关,所以我做了一个C版本:

/* tetration.c */
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

int recur_tet(int b, int n){
    if(n == 1){
        return(b);
    }
    else{
        return(pow(b, recur_tet(b, n - 1)));
    }
}

int iter_tet(int b, int n){
    int ans = 1;
    int i;
    for(i = 1; i <= n; i++){
        ans = pow(b, ans);
    }
    return(ans);
}

int main(int argc, char *argv[]){
    /* giving an argument of "1" will do a recursive tetration
    while an argument of "2" will do an iterative one */
    if(atoi(argv[1]) == 1){
        recur_tet(2,4);
    }
    else if(atoi(argv[1]) == 2){
        iter_tet(2,4);
    }
    return(0);
}

递归版本的速度更快:

> gcc tetration.c -o tet.o
> time(while ((n++ < 100000)); do ./tet.o 1; done)

real    4m24.226s
user    1m26.503s
sys     1m32.155s
> time(while ((n++ < 100000)); do ./tet.o 2; done)

real    4m40.998s
user    1m30.699s
sys     1m37.110s

因此,这种差异似乎是真实的。汇编的C程序(由gcc -S返回)将recur_tet表示为42条指令,而iter_tet表示为39条指令,因此递归程序似乎应该更长?但我对组装一无所知,所以谁知道呢

不管怎样,有没有人能洞察为什么每个函数的递归版本更快,尽管递归与迭代有着共同的智慧?我是不是在用一种愚蠢的方式写我的迭代版本,却没有看到效率低下的情况


Tags: of版本anreturnifincludedoelse
1条回答
网友
1楼 · 发布于 2024-03-29 14:40:58

Python和C比较的问题在于递归算法和迭代算法并不是真正等价的(即使它们应该产生相同的结果)

n1时,递归版本立即返回b,而不执行求幂运算。但是迭代版本在这种情况下执行幂运算(b**1在Python中,而pow(b, 1)在C中)。这是迭代版本速度较慢的原因

因此,一般来说,迭代版本比递归版本进行一次额外的求幂调用

要进行公平的比较,请将递归版本更改为在n1时执行幂运算,或者更改迭代版本以避免它

相关问题 更多 >