python - 为什么尾递归优化比 Python 中的普通递归更快？

Question

虽然我知道尾递归优化是非 Pythonic 的，但我想出了一个快速的 hack 来解决这里的一个问题，这个问题在我准备发布时就被删除了。

在 1000 个堆栈限制下，深度递归算法在 Python 中不可用。但有时通过解决方案进行初步思考非常有用。由于函数在 Python 中是一流的，所以我尝试返回一个有效函数和下一个值。然后在循环中调用该过程，直到完成单个调用。我敢肯定这不是新的。

我发现有趣的是，我预计来回传递函数的额外开销会使它比正常递归慢。在我的粗略测试中，我发现它花费了正常递归时间的 30-50%。 (还有允许 LONG 递归的额外好处。)

这是我正在运行的代码:

from contextlib import contextmanager
import time

# Timing code from StackOverflow most likely.
@contextmanager
def time_block(label):
    start = time.clock()
    try:
        yield
    finally:
        end = time.clock()
        print ('{} : {}'.format(label, end - start))


# Purely Recursive Function
def find_zero(num):
    if num == 0:
        return num
    return find_zero(num - 1)


# Function that returns tuple of [method], [call value]
def find_zero_tail(num):
    if num == 0:
        return None, num
    return find_zero_tail, num - 1


# Iterative recurser
def tail_optimize(method, val):
    while method:
        method, val = method(val)
    return val


with time_block('Pure recursion: 998'):
    find_zero(998)

with time_block('Tail Optimize Hack: 998'):
    tail_optimize(find_zero_tail, 998)

with time_block('Tail Optimize Hack: 1000000'):
    tail_optimize(find_zero_tail, 10000000)

# One Run Result:
# Pure recursion: 998 : 0.000372791020758
# Tail Optimize Hack: 998 : 0.000163852100569
# Tail Optimize Hack: 1000000 : 1.51006975627

为什么第二种方式更快？

我的猜测是在堆栈上创建条目的开销，但我不确定如何找出答案。

编辑:

在玩调用计数时，我做了一个循环来尝试使用不同的 num 值。当我多次循环和调用时，递归更接近奇偶校验。

因此，我在时间之前添加了这个，即新名称下的 find_zero:

def unrelated_recursion(num):
    if num == 0:
        return num
    return unrelated_recursion(num - 1)

unrelated_recursion(998)

现在，尾部优化调用占整个递归时间的 85%。

所以我的理论是 15% 的惩罚是更大堆栈的开销，而不是单个堆栈。

我看到每次只运行一次时执行时间有如此巨大差异的原因是分配堆栈内存和结构的惩罚。一旦分配，使用它们的成本就会大大降低。

因为我的算法非常简单，所以内存结构分配占了执行时间的很大一部分。

当我减少对 unrelated_recursion(499) 的堆栈启动调用时，我在 find_zero(998) 执行时间内获得了完全启动和未启动堆栈之间的一半。这在理论上是有道理的。

Answer 1

作为评论希望提醒我，我并没有真正回答这个问题，所以这是我的观点:

在您的优化中，您正在分配、解包和解除分配元组，因此我尝试不使用它们:

# Function that returns tuple of [method], [call value]
def find_zero_tail(num):
    if num == 0:
        return None
    return num - 1


# Iterative recurser
def tail_optimize(method, val):
    while val:
        val = method(val)
    return val

对于 1000 次尝试，每次尝试都以 value = 998 开始:

• 这个版本需要 0.16 秒
• 您的“优化”版本用了 0.22 秒
• “未优化”的花费了 0.29 秒

(请注意，对我而言，您的优化版本比未优化版本更快......但我们不会进行完全相同的测试。)

但我认为这对获取这些统计数据没有用:成本更多地在 Python 方面(方法调用、元组分配等)，而不是您的代码执行实际操作。在实际应用程序中，您最终不会测量 1000 个元组的成本，而是实际实现的成本。

但千万不要这样做:这几乎是白白难读，你是在为读者而不是机器写作:

# Function that returns tuple of [method], [call value]
def find_zero_tail(num):
    if num == 0:
        return None, num
    return find_zero_tail, num - 1


# Iterative recurser
def tail_optimize(method, val):
    while method:
        method, val = method(val)
    return val

我不会尝试实现一个更具可读性的版本，因为我最终可能会:

def find_zero(val):
    return 0

但我认为在实际情况下有一些很好的方法来处理递归限制(在内存大小或深度方面):

为了帮助解决内存(不是深度)问题，functools 中的 lru_cache 通常会有很大帮助:

>>> from functools import lru_cache
>>> @lru_cache()
... def fib(x):
...     return fib(x - 1) + fib(x - 2) if x > 2 else 1
... 
>>> fib(100)
354224848179261915075

对于堆栈大小，您可以使用 list 或 deque，这取决于您的上下文和用法，而不是使用语言堆栈。根据确切的实现(当您实际上将简单的子计算存储在堆栈中以重新使用它们时)它被称为 dynamic programming :

>>> def fib(x):
...     stack = [1, 1]
...     while len(stack) < x:
...         stack.append(stack[-1] + stack[-2])
...     return stack[-1]
... 
>>> fib(100)
354224848179261915075

但是，使用您自己的结构而不是调用堆栈的好处来了，您并不总是需要保留整个堆栈来继续计算:

>>> def fib(x):
...     stack = (1, 1)
...     for _ in range(x - 2):
...         stack = stack[1], stack[0] + stack[1]
...     return stack[1]
... 
>>> fib(100)
354224848179261915075

但总结一下“在尝试实现之前先了解问题”(不可读、难以调试、难以视觉证明，这是糟糕的代码，但很有趣):

>>> def fib(n):
...     return (4 << n*(3+n)) // ((4 << 2*n) - (2 << n) - 1) & ((2 << n) - 1)
... 
>>> 
>>> fib(99)
354224848179261915075

如果你问我，最好的实现是更具可读性的(对于 Fibonacci 示例，可能是具有 LRU 缓存但通过更改 ... if ... else ... 使用更具可读性的 if 语句，对于另一个示例，deque 可能更具可读性，对于其他示例，动态编程可能更好......

“您是为阅读您的代码的人编写代码，而不是为机器编写代码”。