Recursion lenta en python

Sé que este tema está bien discutido, pero he llegado a un punto en el que no entiendo realmente 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 recursión de la cola, así que la pregunta no es sobre eso. A mi entender, un generador aún debe generar una cantidad de números utilizando el operador +1 . Así que técnicamente, el fact(n) debería agregar un número n veces como el recursivo. La lambda en la reduce se llamará n veces igual que el método recursivo … Por lo tanto, como no tenemos una optimización de llamada de cola en ambos casos, las stacks se crearán / destruirán y se devolverán n veces. Y if en el generador, debe verificar cuándo se debe generar 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 método recursivo usa aritmética simple y no usa generadores.

En una prueba, reemplacé rest*x por x en el método recursivo y el tiempo empleado se redujo a la par con el método usando 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 tampoco ayuda en lugar de n a 1 . Así que no es una sobrecarga con el -1 .

Además, podemos hacer el método recursivo más rápido. Probé varias cosas como variables globales que puedo cambiar … Usando un contexto mutable colocando 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 recursión como parámetro para que no tengamos que “desreferirlo” en nuestro scope …?! Pero nada lo hace más rápido.

Señalaré que tengo una versión del hecho de que uso un forloop que es mucho más rápido que los dos métodos, por lo que claramente hay espacio para mejorar pero no esperaría nada más rápido que el forloop.

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 están involucrados números muy grandes, inicialmente sospeché que la diferencia de rendimiento podría deberse al orden de multiplicación. Al 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 del tiempo de tal método es O (n 2 ), donde n es el número de bits en el final producto. En su lugar, es mejor usar una técnica de dividir y conquistar, donde el resultado final se obtiene como producto de dos valores aproximadamente igualmente largos, cada uno de los cuales se calcula de forma recursiva de la misma manera. Así que también implementé esa versión (ver factorial_divide_and_conquer(n) en el código anterior). Como puede ver a continuación, todavía pierde con la versión basada en reduce() para argumentos pequeños (debido al mismo problema con los parámetros nombrados), pero lo supera para 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

¿Intentando ejecutar las versiones factorial_recursive?() Con x=4000 alcanza el límite de recursión predeterminado, por lo que se debe boost 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