python - 为什么 for 循环阶乘函数比递归函数更快？

Question

我写了两个函数来计算组合。第一个使用 for 循环，另一个使用递归阶乘函数。为什么第一个比第二个快？

def combinations(n: int, k: int) -> int:
    # Collection >= Selection
    if n < k:
        raise ValueError(
            "The size of the collection we are selecting items from must be "
            "larger than the size of the selection."
        )
    # Sizes > 0
    if n < 0 or k < 0:
        raise ValueError(
            "Cannot work with negative integers."
        )
    # Compute with standard python only
    numerator = 1
    for i in range(n + 1 - k, n+1):
        numerator *= i
    denominator = 1
    for i in range(1, k+1):
        denominator *= i
    return int(numerator / denominator)

第二个函数需要一个阶乘函数定义为:

def factorial(n: int) -> int:
    if n < 0:
        raise ValueError(
            "Cannot calculate factorial of a negative number."
        )
    # Recursive function up to n = 0
    return n * factorial(n - 1) if n - 1 >= 0 else 1

它被定义为:

def combinations2(n: int, k: int) -> int:
    # Collection >= Selection
    if n < k:
        raise ValueError(
            "The size of the collection we are selecting items from must be "
            "larger than the size of the selection."
        )
    return int(factorial(n) / (factorial(k) * factorial(n - k)))

当我在 IPython 控制台上运行以下测试时，很明显哪个更快

%timeit combinations(1000, 50)
16.2 µs ± 1.95 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)

和

%timeit combinations2(1000, 50)
1.6 ms ± 129 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

组合的新版本2

好的，根据评论，我同意 combinations2 正在执行更多操作。所以我重写了阶乘和组合函数，这是它们的版本:

def factorial(n: int, lower: int=-1) -> int:
    # n > 0
    if n < 0:
        raise ValueError(
            "Cannot calculate factorial of a negative number."
        )
    # Recursive function up to n = 0 or up to lower bound
    if n - 1 >= 0 and n - 1 >= lower:
        return n * factorial(n - 1, lower)
    return 1

现在可以有一个下限。请注意，通常阶乘 (a, b) = 阶乘 (a)/阶乘 (b)。此外，这是 combinations2 函数的新版本:

def combinations2(n: int, k: int) -> int:
    if n < k:
        raise ValueError(
            "The size of the collection we are selecting items from must be "
            "larger than the size of the selection."
        )
    return int(factorial(n, n - k) / factorial(k))

但同样，这是他们的比较:

%timeit combinations(100, 50)
10.5 µs ± 1.67 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)
%timeit combinations2(100, 50)
56.1 µs ± 5.79 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

Answer 1

只计算操作次数:

在 combinations 中，您正在对分子进行 (n+1) - (n+1-k) 乘法，以及 (k+1) - 1 分母的乘法。

总计:2k 次乘法

在 cominations2 中，您正在进行 n + k + (n-k) 乘法，即 2n 乘法。

并且您还进行了 2n 函数调用以进行递归。

k=50 和 n=1000，难怪第一个解决方案更快。