7

在尝试为另一个 SO 问题写答案时，发生了一件非常奇怪的事情。

我基本上想出了一个单线 gcd 并说it maybe slower because of recursion
gcd = lambda a,b : a if not b else gcd(b, a % b)

这是一个简单的测试：

assert gcd(10, 3) == 1 and gcd(21, 7) == 7 and gcd(100, 1000) == 100

这里有一些基准：

timeit.Timer('gcd(2**2048, 2**2048+123)', setup = 'from fractions import gcd').repeat(3, 100)
# [0.0022919178009033203, 0.0016410350799560547, 0.0016489028930664062]
timeit.Timer('gcd(2**2048, 2**2048+123)', setup = 'gcd = lambda a,b : a if not b else gcd(b, a % b)').repeat(3, 100)
# [0.0020480155944824219, 0.0016460418701171875, 0.0014090538024902344]

嗯，这很有趣，我预计会慢得多，但时间相当接近，？也许导入模块是问题...

>>> setup = '''
... def gcd(a, b):
...     """Calculate the Greatest Common Divisor of a and b.
... 
...     Unless b==0, the result will have the same sign as b (so that when
...     b is divided by it, the result comes out positive).
...     """
...     while b:
...         a, b = b, a%b
...     return a
... '''
>>> timeit.Timer('gcd(2**2048, 2**2048+123)', setup = setup).repeat(3, 100)
[0.0015637874603271484, 0.0014810562133789062, 0.0014750957489013672]

不，仍然相当接近时间确定让我们尝试更大的值。

timeit.Timer('gcd(2**9048, 2**248212)', setup = 'gcd = lambda a,b : a if not b else gcd(b, a % b)').repeat(3, 100) [2.866894006729126, 2.8396279811859131, 2.8353509902954102]
[2.866894006729126, 2.8396279811859131, 2.8353509902954102]
timeit.Timer('gcd(2**9048, 2**248212)', setup = setup).repeat(3, 100)
[2.8533108234405518, 2.8411397933959961, 2.8430981636047363]

有趣我想知道发生了什么事？
由于调用函数的开销，我一直认为递归较慢，lambdas 是例外吗？为什么我还没有达到我的递归限制？
如果使用def我立即点击它来实现，如果我将递归深度增加到类似于10**9我实际上segmentation fault可能得​​到堆栈溢出的东西......

更新

>>> setup = '''
... import sys
... sys.setrecursionlimit(10**6)
... 
... def gcd(a, b):
...     return a if not b else gcd(b, a % b)
... '''
>>> 
>>> timeit.Timer('gcd(2**9048, 2**248212)', setup = 'gcd = lambda a,b:a if not b else gcd(b, a%b)').repeat(3, 100)
[3.0647969245910645, 3.0081429481506348, 2.9654929637908936]
>>> timeit.Timer('gcd(2**9048, 2**248212)', setup = 'from fractions import gcd').repeat(3,   100)
[3.0753359794616699, 2.97499680519104, 3.0096950531005859]
>>> timeit.Timer('gcd(2**9048, 2**248212)', setup = setup).repeat(3, 100)
[3.0334799289703369, 2.9955930709838867, 2.9726388454437256]
>>>

更令人费解...

4

2 回答 2

6 
counter = 0

def gcd(a, b):
    global counter
    counter += 1
    return a if not b else gcd(b, a % b)

gcd(2**9048, 2**248212)
print counter

打印3。当然，深度为 3 的递归并没有太多开销。

于 2012-06-24T09:01:57.080 回答
-1

lambda 的类型与任何其他函数的类型完全相同，并且在两者的情况下，如果在另一个本地范围内定义，则会发生环境捕获。

唯一的区别是使用 lambda 语法定义的函数不会自动成为变量出现的范围内的值，并且 lambda 语法要求主体是一个（可能是复合的）表达式，其值被返回从功能上。

至于递归的速度 - 是的，有一点开销，但显然没有那么多。调用开销似乎主要来自分配堆栈帧的成本。

于 2012-06-24T07:13:58.457 回答