为什么分支递归比线性递归更快（例如：列表反转）

Question

昨天我为列表编写了两个可能的反向函数，以演示一些不同的列表反转方法。但后来我注意到使用分支递归（rev2）的函数实际上比使用线性递归（rev1）的函数更快，即使分支函数需要更多的调用来完成并且相同数量的调用（减去1）非平凡调用（实际上更多的计算密集）比线性递归函数的非平凡调用。我没有明确地触发并行性，那么性能差异来自何处使得具有更多涉及的更多调用的函数花费更少的时间？

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（n2），其中分支递归具有时间复杂度O（n log n）。

这里的递归调用不会在恒定时间内运行：它以它复制的列表的长度运行。实际上，如果复制n个元素的列表，则需要O（n）时间。

现在，如果我们执行线性递归，则意味着我们将执行O（n）调用（最大调用深度为O（n））。每次，我们将完全复制列表，除了一个项目。所以时间的复杂性是：

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

因此，算法的时间复杂度是 - 假设调用本身是在O（1） - O（n2）中完成的。

如果我们执行分支递归，我们制作列表的两个副本，每个副本的长度大约是一半。因此，每个递归级别将花费O（n）时间（因为这些一半也会产生列表的副本，如果我们总结这些，我们在每个递归级别创建一个完整的副本）。但是级别的数量按比例缩放：

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

所以时间复杂度在这里是O（n log n）（这里log是2-log，但就大哦来说无关紧要）。

Using views

我们可以使用视图而不是复制列表：这里我们保持对同一列表的引用，但使用两个指定列表范围的整数。例如：

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）（分支递归）进行比较。