sintaxis - Recursión lenta en python

recursividad programacion

Question

Sé que este tema está bien discutido, pero he encontrado un caso. Realmente no entiendo cómo el método recursivo es "más lento" que un método que usa "reduce, lambda, xrange".

def factorial2(x, rest=1):
if x <= 1:
return rest
else:
return factorial2(x-1, rest*x)
def factorial3(x):
if x <= 1:
return 1
return reduce(lambda a, b: a*b, xrange(1, x+1))

Sé que Python no optimiza la recursividad de cola por lo que la pregunta no es sobre eso. A mi entender, un generador debe generar n cantidad de números usando el operador +1 . Entonces, técnicamente, el fact(n) debería agregar un número n veces al igual que el recursivo. La lambda en la reduce se llamará n veces igual que el método recursivo ... Por lo tanto, dado que no tenemos una optimización de la cola de llamada en ambos casos, las pilas se crearán / destruirán y se devolverán n veces. Y un if en el generador debería verificar cuándo StopIteration una excepción StopIteration .

Esto me hace preguntarme por qué el método recursivo sigue siendo más lento que el otro ya que el recursivo usa aritmética simple y no usa generadores.

En una prueba, reemplacé el rest*x por x en el método recursivo y el tiempo invertido se redujo a la par con el método que usa reduce .

Aquí están mis tiempos de hecho (400), 1000 veces

factorial3: 1.22370505333

factorial2: 1.79896998405

Editar:

Hacer que el método comience de 1 a n no ayuda tampoco en lugar de n a 1 . Entonces, no una sobrecarga con el -1 .

Además, podemos hacer que el método recursivo sea más rápido. Intenté varias cosas como variables globales que puedo cambiar ... Usar un contexto variable al colocar variables en celdas que puedo modificar como una matriz y mantener el método recursivo sin parámetros. Enviar el método utilizado para la recursividad como un parámetro para que no tengamos que "eliminarlo" en nuestro alcance ...?! Pero nada hace que sea más rápido.

Señalaré que tengo una versión del hecho de que el uso de un forloop es mucho más rápido que ambos métodos, por lo que hay un claro margen de mejora, pero no esperaría nada más rápido que el de forloop.

Answer 1

La lentitud de la versión recursiva proviene de la necesidad de resolver en cada llamada las variables nombradas (argumento). He proporcionado una implementación recursiva diferente que tiene solo un argumento y funciona un poco más rápido.

$ cat fact.py
def factorial_recursive1(x):
if x <= 1:
return 1
else:
return factorial_recursive1(x-1)*x
def factorial_recursive2(x, rest=1):
if x <= 1:
return rest
else:
return factorial_recursive2(x-1, rest*x)
def factorial_reduce(x):
if x <= 1:
return 1
return reduce(lambda a, b: a*b, xrange(1, x+1))
# Ignore the rest of the code for now, we''ll get back to it later in the answer
def range_prod(a, b):
if a + 1 < b:
c = (a+b)//2
return range_prod(a, c) * range_prod(c, b)
else:
return a
def factorial_divide_and_conquer(n):
return 1 if n <= 1 else range_prod(1, n+1)
$ ipython -i fact.py
In [1]: %timeit factorial_recursive1(400)
10000 loops, best of 3: 79.3 µs per loop
In [2]: %timeit factorial_recursive2(400)
10000 loops, best of 3: 90.9 µs per loop
In [3]: %timeit factorial_reduce(400)
10000 loops, best of 3: 61 µs per loop

Como en su ejemplo se trata de números muy grandes, inicialmente sospeché que la diferencia de rendimiento podría deberse al orden de multiplicación. Multiplicar en cada iteración un producto parcial grande por el siguiente número es proporcional al número de dígitos / bits en el producto, por lo que la complejidad temporal de dicho método es O (n ² ), donde n es el número de bits en el final producto. En cambio, es mejor utilizar una técnica de dividir y conquistar, donde el resultado final se obtiene como un producto de dos valores aproximadamente igualmente largos, cada uno de los cuales se calcula recursivamente de la misma manera. Así que implementé esa versión también (vea factorial_divide_and_conquer(n) en el código anterior). Como puede ver a continuación, aún pierde en la versión reducida reduce() para argumentos pequeños (debido al mismo problema con los parámetros nombrados), pero lo supera para los argumentos grandes.

In [4]: %timeit factorial_divide_and_conquer(400)
10000 loops, best of 3: 90.5 µs per loop
In [5]: %timeit factorial_divide_and_conquer(4000)
1000 loops, best of 3: 1.46 ms per loop
In [6]: %timeit factorial_reduce(4000)
100 loops, best of 3: 3.09 ms per loop

ACTUALIZAR

Intentar ejecutar las versiones factorial_recursive?() Con x=4000 coincide con el límite de recursión predeterminado, por lo que debe aumentarse el límite:

In [7]: sys.setrecursionlimit(4100)
In [8]: %timeit factorial_recursive1(4000)
100 loops, best of 3: 3.36 ms per loop
In [9]: %timeit factorial_recursive2(4000)
100 loops, best of 3: 7.02 ms per loop