对 Python 中良好的递归性能感到惊讶 [英] Surprised about good recursion performance in python

问题描述

我为素数分解编写了这个相当糟糕的 Python 函数:

I wrote this rather poor Python function for prime factorization:

import math

def factor(n):
    for i in range(2, int(math.sqrt(n)+1)):
        if not n % i:
            return [i] + factor(n//i)
    return [n]

它按预期工作，现在我对使用迭代方法时性能是否会更好感兴趣:

and it worked as expected, now I was interested in whether the performance could be better when using an iterative approach:

def factor_it(n):
    r = []
    i = 2
    while i < int(math.sqrt(n)+1):
        while not n % i:
            r.append(i)
            n //= i
        i +=1
    if n > 1:
        r.append(n)
    return r

但是我观察到的(虽然函数给出了相同的结果)是迭代函数需要更长的时间才能运行.至少我有这样的感觉:

But what I observed (while the functions gave the same results) was that the iterative function took longer to run. At least I had the feeling, when doing this:

number = 31123478114123
print(factor(number))
print(factor_it(number))

所以我测量:

setup = '''
import math

def factor(n):
    for i in range(2, int(math.sqrt(n)+1)):
        if not n % i:
            return [i] + factor(n//i)
    return [n]

def factor_it(n):
    r = []
    i = 2
    while i < int(math.sqrt(n)+1):
        while not n % i:
            r.append(i)
            n //= i
        i +=1
    if n > 1:
        r.append(n)
    return r
'''

import timeit

exec(setup)

number = 66666667*952381*290201
print(factor(number))
print(factor_it(number))

print(timeit.Timer('factor('+str(number)+')',setup=setup).repeat(1,1))
print(timeit.Timer('factor_it('+str(number)+')',setup=setup).repeat(1,1))

这就是我得到的:

[290201, 952381, 66666667]
[290201, 952381, 66666667]
[0.19888348945642065]
[0.7451271022307537]

为什么在这种情况下递归方法比迭代方法快?

Why is the recursive approach in this case faster than the iterative one?

^{我使用 WinPython-64bit-3.4.4.2 (Python 3.4.4 64bits).}

推荐答案

这是因为您每次都在重新计算 sqrt.此修改的运行速度与您的递归版本一样快:

It’s because you’re recomputing sqrt each time. This modification runs as fast as your recursive version:

def factor_it2(n):
    r = []
    i = 2
    lim = int(math.sqrt(n)+1)
    while i < lim:
        while not n % i:
            r.append(i)
            n //= i
        lim = int(math.sqrt(n)+1)
        i += 1
    if n > 1:
        r.append(n)
    return r

timeit 给我这些时间:

factor      0.13133816363922143
factor_it   0.5705408816539869
factor_it2  0.14267319543853973

我认为仍然存在的微小差异是由于 for ... in range(...) 比等效的 while 循环更快，因为 for循环可以使用生成器，而不必执行一堆比较.

I think the tiny difference that remains is due to for … in range(…) being faster than the equivalent while loop, as the for loop can use a generator instead of having to execute a bunch of comparisons.

这篇关于对 Python 中良好的递归性能感到惊讶的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！