为什么这种迭代Collatz方法比Python中的递归版本慢30%？

Question

对于一个特定的问题，我有两种实现，一种是递归的，另一种是迭代的，我想知道是什么导致迭代解决方案比递归解决方案慢约30%。

给定递归解决方案，我编写了一个迭代解决方案，使堆栈显式化。
显然，我只是模仿递归的作用，所以当然Python引擎可以更好地优化以处理簿记。但是我们可以编写具有类似性能的迭代方法吗？

我的案例研究是Euler项目的问题#14。

找到起始值低于一百万的最长Collatz链。

下面是一个简洁的递归解决方案（问题线程中的veritas加上JJ的优化）：

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毫秒以下。
我在这个问题的design方法中设置了Memorization表的初始化，以便计时反映每次调用时表值的“重新发现”。

collatz\u r（2**1002）引发运行时错误：超过最大递归深度
collatz\u i（2**1002）带着1003愉快地返回。

我熟悉发电机、协同程序和装饰程序
我正在使用Python 2.7。我也很高兴使用Numpy（在我的机器上是1.8）。

• 消除性能差距的迭代解决方案

我主要寻找第一个，尽管第二个和第三个对这个问题非常重要，并且会增加我对Python的理解。




Answer 1

匿名用户

迭代代码有时比递归代码更快，因为它避免了函数调用开销。但是，<代码>堆栈。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。

综上所述，我得出结论，迭代版本没有固有的优势。下一个要考虑的问题是哪一个做得更多。为了得到（非常）粗略的估计，我们可以查看每个版本中执行的行数。我做了一个快速的实验来发现：

• 调用1234275次collatz\u r，if块的主体执行984275次

现在，假设collatz\r在if外有2行，在if内有4行（最坏的情况下，当碰到else时执行）。总共需要执行640万行。collatz\u i的可比数字可能是5和9，总计1000万。

即使这只是一个粗略的估计，也足以与实际时间相符。

Answer 2

这是我在运行一些基准测试后的（部分）解释，这些基准测试证实了你的数据。

虽然在CPython中递归函数调用的代价很高，但它们的代价远没有使用列表模拟调用堆栈那么高。递归调用的堆栈是用C实现的紧凑结构（请参阅Eli Bendersky的解释和源代码中的文件Python/ceval.C）。

相比之下，您的模拟堆栈是一个Python列表对象，即一个堆分配的、动态增长的指向元组对象的指针数组，这些指针反过来指向实际值；再见，引用的位置，hello缓存未命中。然后在这些对象上使用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为递归版本生成类似的内容。）