분기 재귀가 선형 재귀보다 더 빠른 이유 (예 : 목록 반전)

Question

어제 목록 반전을 수행하는 여러 가지 다른 방법을 보여주기 위해리스트에 대해 두 가지 가능한 역기능을 작성했습니다. 그러나 분기 함수 (rev2)를 사용하는 함수가 선형 함수 (rev1)를 사용하는 함수보다 실제로 더 빠르다는 것을 알았습니다. 비록 분기 함수가 더 많은 호출을 끝내고 동일한 수의 호출 (빼기 하나)이 중요하지 않더라도 선형 재귀 함수의 부작용이없는 호출보다 (실제로는 계산 집약적입니다.) 명시 적으로 병렬 처리를 트리거하는 곳이 어디에도 없으므로 성능 차이는 어디에서 발생합니까? 더 많은 호출이 포함 된 함수가 더 짧은 시간 내에 수행됩니다.

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

짧은 답변 : 그것은 그렇게 많이 여기에 통화 아니지만,이 목록의 복사의 양이다. 결과적으로 선형 재귀는 (N ²) 시간 복잡도 O 재귀 분파 시간 복잡도 O를 갖는 wheras을 갖는다를 (N 로그 n).

재귀 호출은 여기 하지가 일정 시간 작동하지 않습니다 : 그것은리스트 그것을 복사의 길이에서 작동합니다. 실제로 n 요소 목록을 복사하면 O (n) 시간이 필요합니다. 우리는 선형 순환을 수행하는 경우

이제, 우리가 O (N) 호출을 수행하는 수단 (최대 콜 깊이는 O (N)가이다). 매번 한 항목을 제외한 목록을 전체적으로 복사합니다. 그래서 시간 복잡도는 다음과 같습니다

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

그래서 알고리즘의 시간 복잡도입니다 - 자체에서 수행하는 호출을 제공 O (1)-(N ²) O.

분기 재귀를 수행하는 경우 약 2 분의 1 길이의 목록을 2 부 만듭니다. 따라서 모든 레벨의 재귀는 O (n) 시간이 걸릴 것입니다. (이 반쪽은 목록의 복사본을 생성하므로 합계하여 모든 재귀 수준에서 전체 복사본을 만듭니다.)

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

그래서 시간 복잡도는 로그이 2 로그 여기 O (N 로그 n) (여기 이지만, 그 측면에서 중요하지 않습니다하지만 수준의 수 저울 logwise 큰 오).

사용 전망

대신 복사 목록, 우리가 보기을 사용할 수 있습니다

: 여기에 우리는 같은 목록에 대한 참조를 유지하지만, 목록의 범위를 지정하는 두 개의 정수를 사용합니다. 예를 들어 :

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)

우리가 지금 timeit 모듈을 실행하는 경우, 우리는 구하십시오

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

이것은 우리가 더 이상 목록을 복사하지 않으며, 따라서 append(..) 기능이 에서 작동하기 때문에 인 O (1)상각 됨 비용. 분기 재귀의 경우 두 개의 목록을 추가하는 반면, O (k)의 경우 k 두 목록의 길이 합으로 작동합니다. 이제 O (n) (선형 재귀)와 O (n log n) (분기 재귀)을 비교합니다.