为什么分支递归比线性递归更快(示例:列表反转)

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

简短答案：这里的调用不是太多，但它是列表的复制量。结果，线性递归具有时间复杂性 o（n ² ）分支递归有时间复杂性 o（n log n）。

此处的递归调用在恒定时间内运行：它在列表的长度上运行，它复制了。确实，如果您复制 n 元素的列表，则需要 o（n）时间。

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

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

因此，算法的时间复杂性是 - 给定调用本身是在 o（1） - o（n ² ）中完成的。

如果我们执行分支递归，则将其撰写两个列表的副本，每个副本的长度约为一半。因此，递归的每个级别都将采用 o（n）时间（因为这些半部分也会产生列表的副本，如果我们总结一下，我们会做一个整个在每个递归级别复制）。但是级别数量缩放logwise：

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

因此，时间复杂性在这里 o（n log n）（这里 log 是2-log，但这在 big方面并不重要哦）。

使用视图

我们可以使用 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） amortized 成本起作用。而对于分支递归，我们附加了两个列表，因此它在 o（k）中使用 k 是两个列表的长度之和。因此，现在我们将 o（n）（线性递归）与 o（n log n）（分支递归）进行比较。