sind Python Lambdas anders als Standardfunktionen implementiert?

Question

Beim Versuch, eine Antwort für eine andere SO-Frage zu schreiben, ist etwas sehr Seltsames passiert.

kam ich im Grunde mit einem Einzeiler GCD auf und sagte it maybe slower because of recursion
gcd = lambda a,b : a if not b else gcd(b, a % b)

heren ein einfacher Test:

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

hier sind einige Benchmarks:

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] 

Nun das ist interessant I erwartet, viel langsamer zu sein, aber die Timings sind ziemlich nah,? vielleicht ist das Importieren des Moduls das Problem ...

>>> 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] 

nein, immer noch ziemlich enge Timings ok lassen Sie größere Werte versuchen.

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] 

interessant Ich frage mich, was los ist?
Ich nahm immer an, dass Rekursion langsamer war wegen des Overheads beim Aufruf einer Funktion, sind Lambdas die Ausnahme? und warum ich meine Rekursionsgrenze nicht erreicht habe?
Bei der Verwendung von def implementiert ich es sofort getroffen, wenn ich die Rekursionstiefe etwas wie 10**9 erhöhe ich tatsächlich bekommen einen segmentation fault wahrscheinlich einen Stapelüberlauf ...

aktualisieren

>>> 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] 
>>> 

noch mehr rätselhaft ...

Answer 1

Der Typ eines Lambdas ist genau der gleiche wie der Typ einer anderen Funktion, und bei beiden, wenn in einem anderen lokalen Bereich definiert, erfolgt die Erfassung der Umgebung.

Der einzige Unterschied besteht darin, dass mit der Lambda-Syntax definierte Funktionen nicht automatisch zum Wert einer Variablen im Gültigkeitsbereich werden, und dass die Lambda-Syntax den Körper als einen (möglicherweise zusammengesetzten) Ausdruck definiert davon wird von der Funktion zurückgegeben.

In Bezug auf die Geschwindigkeit der Rekursion - ja, es gibt einen leichten Overhead, aber anscheinend nicht so viel. Der Anruf-Overhead scheint hauptsächlich aus den Kosten der Zuweisung des Stapelrahmens zu bestehen.

Answer 2

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 

Drucke 3. Natürlich gibt es nicht viel Overhead für eine Rekursion von Tiefe 3.