Warum Verzweigung Rekursion schneller als lineare Rekursion (Beispiel: Listeninversion)

Question

Gestern schrieb ich zwei mögliche umgekehrte Funktionen für Listen, um einige verschiedene Möglichkeiten zur Listeninversion zu demonstrieren. Aber dann habe ich bemerkt, dass die Funktion mit Verzweigung Rekursion (rev2) ist tatsächlich schneller als die Funktion mit linearen Rekursion(), obwohl die Verzweigung Funktion mehr Anrufe zu beenden und die gleiche Anzahl von Anrufen (minus eins) von nicht-trivialen dauert Aufrufe (die eigentlich rechenintensiver sind) als die nicht-trivialen Aufrufe der linear rekursiven Funktion. Nirgends löse ich explizit Parallelität aus, woher kommt dann der Leistungsunterschied, der eine Funktion mit mehr Anrufen macht, die mehr Zeit benötigen?

from sys import argv 
from time import time 


nontrivial_rev1_call = 0 # counts number of calls involving concatentation, indexing and slicing 
nontrivial_rev2_call = 0 # counts number of calls involving concatentation, len-call, division and sclicing 

length = int(argv[1]) 


def rev1(l): 
    global nontrivial_rev1_call 

    if l == []: 
     return [] 
    nontrivial_rev1_call += 1 
    return rev1(l[1:])+[l[0]] 

def rev2(l): 
    global nontrivial_rev2_call 
    if l == []: 
     return [] 
    elif len(l) == 1: 
     return l 
    nontrivial_rev2_call += 1 
    return rev2(l[len(l)//2:]) + rev2(l[:len(l)//2]) 



lrev1 = rev1(list(range(length))) 
print ('Calls to rev1 for a list of length {}: {}'.format(length, nontrivial_rev1_call)) 


lrev2 = rev2(list(range(length))) 
print ('Calls to rev2 for a list of length {}: {}'.format(length, nontrivial_rev2_call)) 
print() 

l = list(range(length)) 


start = time() 
for i in range(1000): 
    lrev1 = rev1(l) 
end = time() 

print ("Average time taken for 1000 passes on a list of length {} with rev1: {} ms".format(length, (end-start)/1000*1000)) 


start = time() 
for i in range(1000): 
    lrev2 = rev2(l) 
end = time() 

print ("Average time taken for 1000 passes on a list of length {} with rev2: {} ms".format(length, (end-start)/1000*1000)) 

Beispielaufruf:

$ python reverse.py 996 
calls to rev1 for a list of length 996: 996 
calls to rev2 for a list of length 996: 995 

Average time taken for 1000 passes on a list of length 996 with rev1: 7.90629506111145 ms 
Average time taken for 1000 passes on a list of length 996 with rev2: 1.3290061950683594 ms 

Answer 1

Kurze Antwort: Es ist nicht so sehr die Anrufe hier, aber es ist die Menge des Kopierens der Listen. Als Ergebnis wird die lineare Rekursion Zeitkomplexität hat O (n 2 ) wheras das Verzweigungs Rekursion Zeitkomplexität O (n log n) hat.

Der rekursive Aufruf hier tut nicht in konstanter Zeit arbeiten: sie arbeitet in der Länge der Liste kopiert. In der Tat, wenn Sie eine Liste von n Elemente kopieren, erfordert es O (n) Zeit.

Wenn wir nun die lineare Rekursion durchführen, es bedeutet, werden wir O (n) Anrufe durchführen (die maximale Anruf Tiefe O (n)). Jedes Mal werden wir die Liste komplett kopieren, bis auf einen Punkt. So ist die Zeitkomplexität ist:

n 
--- 
\  n * (n+1) 
/ k = ----------- 
---   2 
k=1 

So ist die Zeitkomplexität des Algorithmus wird - gegeben, die Anrufe selbst getan werden in O (1)-O (n).

Falls wir eine Verzweigungsrekursion durchführen, erstellen wir zwei Kopien der Liste, die jeweils etwa die Hälfte haben. Also alle Ebene der Rekursion dauert O (n) Zeit (da diese Hälften in Kopien der Liste auch ergeben, und wenn wir diese zusammenfassen, machen wir eine vollständige Kopie auf jedem rekursiven Ebene). Aber die Anzahl der Ebenen Skalen logwise:

log n 
----- 
\  
/ n = n log n 
----- 
k=1 

So ist die Zeitkomplexität hier ist O (n log n) (hier log ist das 2-log, aber das spielt keine Rolle in Bezug auf groß oh).

Mit Blick

Anstelle des Kopierens Listen können wir Ansichten verwenden: hier halten wir einen Verweis auf die gleichen Liste, aber zwei ganzen Zahlen verwenden, die die Spannweite der Liste angeben. Zum Beispiel:

def rev1(l, frm, to): 
    global nontrivial_rev1_call 
    if frm >= to: 
     return [] 
    nontrivial_rev1_call += 1 
    result = rev1(l, frm+1, to) 
    result.append(l[frm]) 
    return result 

def rev2(l, frm, to): 
    global nontrivial_rev2_call 
    if frm >= to: 
     return [] 
    elif to-frm == 1: 
     return l[frm] 
    nontrivial_rev2_call += 1 
    mid = (frm+to)//2 
    return rev2(l, mid, to) + rev2(l, frm, mid)

Wenn wir jetzt das timeit Modul ausführen, erhalten wir:

>>> timeit.timeit(partial(rev1, list(range(966)), 0, 966), number=10000) 
2.176353386021219 
>>> timeit.timeit(partial(rev2, list(range(966)), 0, 966), number=10000) 
3.7402000919682905 

Das ist, weil wir nicht mehr die Listen kopieren und damit die append(..) Funktion arbeitet in O (1)amortisiert kosten. Während wir für die Verzweigungsrekursion zwei Listen anhängen, so funktioniert es in O (k) mit k die Summe der Länge der beiden Listen. Wir vergleichen nun O (n) (lineare Rekursion) mit O (n log n) (Verzweigungsrekursion).