Joe*_*Joe 15 python recursion performance benchmarking tail-recursion
虽然我知道尾部递归优化是非Pythonic的,但我想到了一个快速入侵这里的问题,一旦我准备发布就删除了.
由于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)执行时间内完全启动和未启动堆栈之间的大约一半.这与理论有关.
作为希望提醒我的评论，我并没有真正回答这个问题，所以这是我的观点：
在你的优化中，你要分配、解包和取消分配元组，所以我尝试不使用它们：
# 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 开始：
（请注意，对我来说，您的优化版本比未优化版本更快......但我们不进行完全相同的测试。）
但我认为这对于获取这些统计数据没有用：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
对于堆栈大小，您可以根据您的上下文和用法使用 alist或 a ，而不是使用语言堆栈。deque根据具体的实现（当您实际上在堆栈中存储简单的子计算以重新使用它们时），它被称为动态编程：
>>> 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
如果你问我，最好的实现是更具可读性的实现（对于斐波那契示例，可能是具有 LRU 缓存的实现，但通过使用... if ... else ...更具可读性的 if 语句更改，对于另一个示例，adeque可能更具可读性，对于其他示例，动态规划可能会更好......
“你是为阅读你的代码的人而写，而不是为机器”。