Prelude
对于一个特定问题，我有两个实现，一个递归，一个迭代，我想知道是什么原因导致迭代解决方案比递归解决方案慢 ~30%。
给定递归解决方案，我编写了一个迭代解决方案，使堆栈显式。
显然，我只是模仿递归正在做什么，所以当然 Python 引擎可以更好地优化来处理簿记。但是我们可以编写具有类似性能的迭代方法吗？
我的案例研究是欧拉项目的问题#14。
找到起始数量低于一百万的最长的Collatz链。
法典
这是一个简洁的递归解决方案(由于问题线程中的veritas加上jJjjJ的优化)：
def solve_PE14_recursive(ub=10**6):
def collatz_r(n):
if not n in table:
if n % 2 == 0:
table[n] = collatz_r(n // 2) + 1
elif n % 4 == 3:
table[n] = collatz_r((3 * n + 1) // 2) + 2
else:
table[n] = collatz_r((3 * n + 1) // 4) + 3
return table[n]
table = {1: 1}
return max(xrange(ub // 2 + 1, ub, 2), key=collatz_r)
这是我的迭代版本：
def solve_PE14_iterative(ub=10**6):
def collatz_i(n):
stack = []
while not n in table:
if n % 2 == 0:
x, y = n // 2, 1
elif n % 4 == 3:
x, y = (3 * n + 1) // 2, 2
else:
x, y = (3 * n + 1) // 4, 3
stack.append((n, y))
n = x
ysum = table[n]
for x, y in reversed(stack):
ysum += y
table[x] = ysum
return ysum
table = {1: 1}
return max(xrange(ub // 2 + 1, ub, 2), key=collatz_i)
以及使用IPython的机器(具有大量内存的i7机器)上的计时：
In [3]: %timeit solve_PE14_recursive()
1 loops, best of 3: 942 ms per loop
In [4]: %timeit solve_PE14_iterative()
1 loops, best of 3: 1.35 s per loop
评论
递归解决方案很棒：
- 经过优化，可根据两个最低有效位跳过一两个步骤。
我最初的解决方案没有跳过任何 Collatz 步骤，花了 ~1.86 秒
很难 - 达到 Python 的默认递归限制 1000。
collatz_r(9780657630)返回 1133，但需要少于 1000 次递归调用。 - 记忆避免回溯
- 按需计算
collatz_r长度max
玩弄它，计时似乎精确到 +/- 5 毫秒.
像 C 和 Haskell 这样的静态类型的语言可以获得低于 100 毫秒的时序。
我通过设计将记忆table的初始化放在这个问题的方法中，以便计时将反映每次调用时表值的"重新发现"。
collatz_r(2**1002)提高RuntimeError: maximum recursion depth exceeded.collatz_i(2**1002)高兴地带着1003回来了。
我熟悉生成器、协程和装饰器。
我正在使用Python 2.7。我也很高兴使用Numpy(我的机器上的1.8)。
我在寻找什么
- 缩小性能差距的迭代解决方案
- 关于 Python 如何处理递归的讨论
- 与显式堆栈关联的性能损失的更精细细节
我主要寻找第一个，尽管第二个和第三个对这个问题非常重要，并且会增加我对 Python 的理解。
这是我在运行一些基准测试后对(部分)解释的镜头，这些基准测试证实了您的数字。
虽然递归函数调用在 CPython 中很昂贵，但它们并不像使用列表模拟调用堆栈那样昂贵。递归调用的堆栈是用 C 实现的紧凑结构(参见 Eli Bendersky 的解释和源代码中Python/ceval.c的文件)。
相比之下，你的模拟堆栈是一个Python列表对象，即一个堆分配的，动态增长的指向元组对象的指针数组，这些指针又指向实际值;再见，引用位置，你好缓存未命中。然后，您可以在这些对象上使用Python臭名昭著的缓慢迭代。使用kernprof进行逐行分析可确认迭代和列表处理需要花费大量时间：
Line # Hits Time Per Hit % Time Line Contents
==============================================================
16 @profile
17 def collatz_i(n):
18 750000 339195 0.5 2.4 stack = []
19 3702825 1996913 0.5 14.2 while not n in table:
20 2952825 1329819 0.5 9.5 if n % 2 == 0:
21 864633 416307 0.5 3.0 x, y = n // 2, 1
22 2088192 906202 0.4 6.4 elif n % 4 == 3:
23 1043583 617536 0.6 4.4 x, y = (3 * n + 1) // 2, 2
24 else:
25 1044609 601008 0.6 4.3 x, y = (3 * n + 1) // 4, 3
26 2952825 1543300 0.5 11.0 stack.append((n, y))
27 2952825 1150867 0.4 8.2 n = x
28 750000 352395 0.5 2.5 ysum = table[n]
29 3702825 1693252 0.5 12.0 for x, y in reversed(stack):
30 2952825 1254553 0.4 8.9 ysum += y
31 2952825 1560177 0.5 11.1 table[x] = ysum
32 750000 305911 0.4 2.2 return ysum
有趣的是，即使是n = x也占用了总运行时间的 8% 左右。
(不幸的是，我无法kernprof为递归版本生成类似的东西。
迭代代码有时比递归代码更快，因为它避免了函数调用开销。但是，stack.append也是一个函数调用(以及顶部的属性查找)，并增加了类似的开销。计算调用append，迭代版本进行的函数调用与递归版本相同。
在这里比较前两个和后两个时间...
$ python -m timeit pass
10000000 loops, best of 3: 0.0242 usec per loop
$ python -m timeit -s "def f(n): pass" "f(1)"
10000000 loops, best of 3: 0.188 usec per loop
$ python -m timeit -s "def f(n): x=[]" "f(1)"
1000000 loops, best of 3: 0.234 usec per loop
$ python -m timeit -s "def f(n): x=[]; x.append" "f(1)"
1000000 loops, best of 3: 0.336 usec per loop
$ python -m timeit -s "def f(n): x=[]; x.append(1)" "f(1)"
1000000 loops, best of 3: 0.499 usec per loop
。确认append调用排除属性查找所需的时间与调用最小纯 Python 函数所需的时间大致相同，~170 ns。
综上所述，我得出结论，迭代版本不享有固有的优势。下一个要考虑的问题是哪一个做更多的工作。为了得到一个(非常)粗略的估计，我们可以查看每个版本中执行的行数。我做了一个快速实验来发现：
collatz_r称为 1234275 次，if块的主体执行 984275 次。collatz_i调用 250000 次，while循环运行 984275 次
现在，假设collatz_r在if外有 2 行，在有 4 行(在最坏的情况下，当else被击中时执行)。这加起来要执行的行数为 640 万行。collatz_i的可比数字可能是5和9，加起来为1 000万。
即使这只是一个粗略的估计，也足以符合实际时间。