提问者:小点点

为什么生成器表达式与python 3中的map对象相比具有较低的递归深度,尽管被认为更pythonic?


例如,我们可以在生成器中使用递归定义斐波那契序列:

from itertools import pairwise

def fibs():
    yield 0
    yield 1
    yield from map(sum, pairwise(fibs()))

for index, result in enumerate(fibs()):
    print(index, result)

如果我们尝试运行它,它会在索引为1025时放弃,在递归深度超过错误下被粉碎。下面我复制了输出的结尾:

1024 4506699633677819813104383235728886049367860596218604830803023149600030645708721396248792609141030396244873266580345011219530209367425581019871067646094200262285202346655868899711089246778413354004103631553925405243
1025 7291993184377412737043195648396979558721167948342308637716205818587400148912186579874409368754354848994831816250311893410648104792440789475340471377366852420526027975140687031196633477605718294523235826853392138525
Traceback (most recent call last):
  File "/home/user/Área de Trabalho/fibs1.py", line 6, in fibs
    yield from map(sum, pairwise(fibs()))
  File "/home/user/Área de Trabalho/fibs1.py", line 6, in fibs
    yield from map(sum, pairwise(fibs()))
  File "/home/user/Área de Trabalho/fibs1.py", line 6, in fibs
    yield from map(sum, pairwise(fibs()))
  [Previous line repeated 997 more times]
RecursionError: maximum recursion depth exceeded while calling a Python object

现在我们可以尝试通过用生成器表达式替换map来更改它,以使其更Pythonic:

from itertools import pairwise

def fibs():
    yield 0
    yield 1
    yield from (sum(pair) for pair in pairwise(fibs()))

for index, result in enumerate(fibs()):
    print(index, result)

现在问题是,这个版本的运行时间只有第一个版本的一半,内爆深度仅为513,错误消息要大得多,同时它还返回最大递归深度超过错误:

512 44893845313309942978077298160660626646181883623886239791269694466661322268805744081870933775586567858979269
513 72639767602615659833415769076743441675530755653534070653184546540063470576806357692953027861477736726533858
Traceback (most recent call last):
  File "/home/user/Área de Trabalho/fibs2.py", line 6, in <genexpr>
    yield from (sum(pair) for pair in pairwise(fibs()))
  File "/home/user/Área de Trabalho/fibs2.py", line 6, in fibs
    (... this repeats a lot, exceeds maximum character limit in SO)
    yield from (sum(pair) for pair in pairwise(fibs()))
  File "/home/user/Área de Trabalho/fibs2.py", line 6, in fibs
    yield from (sum(pair) for pair in pairwise(fibs()))
RecursionError: maximum recursion depth exceeded while calling a Python object

所以我问,为什么有区别?

我在玩fibonacci Joel Grus在他的博客中发布的类似haskell的实现时注意到了这个问题,但将其更改为使用python 3.10发布时在itertools模块中引入的成对。这样就需要单个导入(成对),而不是三个导入(add, islice,tec)和一个辅助函数定义(尾巴)。


共1个答案

匿名用户

您所指的“耐力”与惰性评估和具有配置的最大堆栈深度的尾递归有关。

Common Lisp和Schem之间最大的区别是后者绝对需要适当的尾递归支持。Lisp代码可能能够永远循环,但对于符合该格式的方案代码,它可以保证,而不会增加堆栈。

在pythonitertools上下文中,你基本上是在抱怨这不是规范的一部分。而且,以这样或那样的方式表达想法可能会在每次迭代中推动单个堆栈帧或一对堆栈帧。好吧,很公平。你正在测试的工具不是为了符合这一要求而编写的,当你推动这方面时,它们可能会出现不足。当设计一个解决方案时,你可能会考虑用一个小lru_cache来修补,但在这里我理解这只是一个学术练习,试图探索极限,你已经找到了它们。

代码正在做你要求的事情。是的,还有设计更好代码的空间。加油!