¿Python lambdas se implementa de forma diferente a las funciones estándar?

Question

Al intentar escribir una respuesta para otra pregunta SO, sucedió algo realmente peculiar.

básicamente me ocurrió con un mcd un trazador de líneas y dijo it maybe slower because of recursion
gcd = lambda a,b : a if not b else gcd(b, a % b)

aquí está una prueba simple:

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

aquí están algunos puntos de referencia:

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] 

bueno eso es lo interesante se espera que sea mucho más lento, pero los tiempos son bastante cercanos,? tal vez la importación del módulo es el problema ...

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

aún bastante bastante cerca de los tiempos bien, vamos a intentar valores más grandes.

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] 

interesante Me pregunto qué está pasando?
Siempre supuse que la recursividad era más lenta debido a la sobrecarga de llamar a una función, ¿son lambdas la excepción? y por qué no he alcanzado mi límite de recursión?
Si se implementa utilizando def lo golpeó de inmediato, si aumento el nivel de recursividad a algo así como 10**9 De hecho, me sale un probablemente un desbordamiento de pila segmentation fault ...

actualización

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

aún más desconcertante ...

Answer 1

El tipo de lambda es exactamente el mismo que el tipo de cualquier otra función, y en el caso de ambos, si se define en otro ámbito local, se produce la captura del entorno.

La única diferencia es que las funciones definidas con la sintaxis lambda no se convierten automáticamente en el valor de una variable en el ámbito en el que aparece, y esa sintaxis lambda requiere que el cuerpo sea una expresión (posiblemente compuesta), el valor de lo cual se devuelve desde la función.

En cuanto a la velocidad de recursión, sí, hay una ligera sobrecarga, pero aparentemente no tanto. La sobrecarga de llamadas parecería estar hecha principalmente del costo de asignar el marco de pila.

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 

Prints 3. Por supuesto, no hay una gran sobrecarga para una recursión de profundidad 3.