Powolna rekursja w pytonie

Question

Wiem, że ten temat jest dobrze omawiany, ale doszedłem do sprawy, której nie rozumiem, jak metoda rekurencyjna jest "wolniejsza" niż metoda wykorzystująca "zmniejszyć, 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)) 

Wiem, że Python nie optymalizuje rekursji ogon, więc pytanie nie jest o tym. Według mojej wiedzy generator powinien generować n liczby liczb za pomocą operatora +1. Więc technicznie, fact(n) powinien dodać numer n razy tak jak rekursywny. lambda w reduce będzie nazywać się n razy tak samo jak metoda rekursywna ... Tak więc, ponieważ nie mamy optymalizacji wywołań końcowych w obu przypadkach, stosy będą tworzone/niszczone i zwracane n razy. I if w generatorze powinien sprawdzić, kiedy podnieść wyjątek StopIteration.

Zastanawiam się, dlaczego metoda rekursywna jest nadal wolniejsza od drugiej, ponieważ rekursywna używa prostej arytmetyki i nie używa generatorów.

W teście zastąpiłem rest*x przez x w metodzie rekurencyjnej, a czas spędzony został zmniejszony na równi z metodą z użyciem reduce.

Oto moje czasy dla faktu (400), 1000 razy

factorial3: +1,22370505333

factorial2: 1,79896998405

Edit:

Making metody start od 1 do n nie pomaga eit jej zamiast n do 1. Więc nie narzut z -1.

Co więcej, możemy przyspieszyć metodę rekurencyjną. Próbowałem wielu rzeczy, takich jak zmienne globalne, które mogę zmienić ... Używając kontekstu zmiennego, umieszczając zmienne w komórkach, które mogę modyfikować jak tablicę i zachowuję metodę rekursywną bez parametrów. Wysyłanie metody używanej do rekursji jako parametru, więc nie musimy "dereferencji" w naszym zakresie ...?! Ale nic nie sprawia, że ​​jest to szybsze.

Podkreślę, że mam wersję faktu, że użycie forloop jest znacznie szybsze niż obie z tych dwóch metod, więc jest wyraźnie miejsce na ulepszenia, ale nie oczekiwałbym niczego szybciej niż forloop.

Answer 1

Powolność wersji rekursywnej wynika z potrzeby rozstrzygnięcia w każdym wywołaniu nazwanych zmiennych (argumentów). Dostarczyłem innej rekurencyjnej implementacji, która ma tylko jeden argument i działa nieco szybciej.

$ 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 

Ponieważ w twoim przykładzie zaangażowane są bardzo duże liczby, początkowo podejrzewałem, że różnica w wydajności może wynikać z kolejności mnożenia. Mnożenie w każdej iteracji dużego produktu częściowego przez następną liczbę jest proporcjonalne do liczby cyfr/bitów w produkcie, więc złożoność czasowa takiej metody jest O (n), gdzie n jest liczbą bitów w ostateczny produkt.Zamiast tego lepiej jest użyć techniki dziel i rządź, w której wynik końcowy jest uzyskiwany jako iloczyn dwóch w przybliżeniu jednakowo długich wartości, z których każda jest rekurencyjnie obliczana w ten sam sposób. Dlatego też zaimplementowałem tę wersję (patrz factorial_divide_and_conquer(n) w powyższym kodzie). Jak widać poniżej, wciąż traci na wersji reduce() dla małych argumentów (z powodu tego samego problemu z nazwanymi parametrami), ale przewyższa go dla dużych argumentów.

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 

UPDATE

próbuje uruchomić wersje factorial_recursive?() z x=4000 hitów domyślny limit rekurencji, więc limit musi być increased:

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