分岐再帰が線形再帰よりも高速である理由（例：リスト反転）

Question

昨日、リスト反転のためにいくつかの異なる方法を示すために、リストの2つの逆関数を書きました。しかし、分岐関数がより多くの呼び出しを終わらせ、同じ数の呼び出し（マイナス1）が重要でないにもかかわらず、分岐再帰（rev2）を使用する関数が実際には線形再帰を使用する関数線形回帰関数の自明でない呼び出しよりも（実際にはより多くの計算を要する）呼び出しである。明示的に並列処理を起動しているところはありません。そのため、パフォーマンスの差はどこから来ていますか。

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

例コール：

$ 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

短い答え：それはずっとここに呼び出していないのですが、それはリストのコピーの量です。結果として線形再帰は時間複雑O（N ）を有する再帰分岐 wheras はO（N Nログ）の時間複雑性を有します。ここ

再帰呼び出しはないは、一定時間で動作ん：それは、リストのそれをコピーの長さで動作します。実際、n要素のリストをコピーすると、O（n）時間が必要になります。私たちは、線形再帰を行う場合

は今、それは我々がO（n）のコール（最大コール深さはO（n）のである）を実行することを意味します。毎回、1つのアイテムを除いて、リストを完全にコピーします。そう時間複雑である：

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

ので、アルゴリズムの時間複雑度は - O（N ） - コール自体がO（1）で行われる所与。

分岐再帰を実行する場合、リストのコピーを2つ作成します。それぞれの長さは約半分です。したがって、すべてレベルの再帰は、O（n）時間になります（これらの半分はリストのコピーにもなりますので、これらを合計するとすべての再帰レベルでコピーが作成されます）。しかしlogwiseスケールレベルの数：

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

だから複雑さがここO（nはn個のログ）（ここではログある時間は2ログですが、それは、という点で重要ではありません。 big oh）。ここで我々は同じリストへの参照を保持しますが、リストのスパンを指定する2つの整数を使用します。ビュー

代わりのリストをコピーを使用して

、我々はビューを使用することができます。例えば：私たちは今、timeitモジュールを実行する場合

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)

、我々は得る：（1）私たちは、もはやリストをコピーし、ひいてはappend(..)機能がOで動作するため、

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

はこれではありません償却費用。一方、分岐再帰の場合、2つのリストが追加されるため、で動作し、kの2つのリストの長さの合計です。今度は、O（n）（線形再帰）とO（n log n）（分岐再帰）を比較します。