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]

何が起こっているのだろうか？
関数を呼び出すオーバーヘッドのために再帰が遅いといつも思っていましたが、ラムダは例外ですか? なぜ再帰制限に達していないのですか?
使用して実装する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

ラムダのタイプは他の関数のタイプとまったく同じであり、両方の場合、別のローカルスコープで定義されていると、環境キャプチャが発生します。

唯一の違いは、ラムダ構文で定義された関数は、それが表示されるスコープ内の変数の値にならないことと、ラムダ構文では本体が1つの（場合によっては複合）式である必要があり、その値が返されることです。関数から。

再帰の速度に関しては、はい、わずかなオーバーヘッドがありますが、明らかにそれほど多くはありません。呼び出しのオーバーヘッドは、ほとんどの場合、スタックフレームを割り当てるコストで発生しているように見えます。

于 2012-06-24T07:13:58.457 に答える