在使用 Memoization 和 Recursion 时，如何改进计算第 N 行 Pascals 三角形的代码？

Question

我一直在修改递归并决定用它来计算帕斯卡三角形的行。我已经成功地创建了一个函数来生成适用于 n <= 7 的 Pascals Triangle，但是它的效率非常低。我知道生成帕斯卡三角形的身份，但我对此并不感兴趣。我想要的是一些改进下面代码的指导。

在大约 n = 7 之后，计算需要很长时间，这让我觉得我的 memoization 实现有误。

count = 0 
def Pascal(n):
    global count
    count += 1 
    pasc_list = [] 
    i = 0 
    j = i+1
    dictionary = {0:[1],1:[1,1]}

    if n in dictionary:
        return dictionary[n]
    else:
        pasc_list.append(1)
        while j < len(Pascal(n-1)):
            pasc_list.append(Pascal(n-1)[i] + Pascal(n-1)[j])
            i += 1 
            j = i + 1 
        pasc_list.append(1)
        dictionary[n] = pasc_list
    return pasc_list
a = Pascal(5)
print(a)
print(count)

对于 n = 5，作用域的数量已经是 4694，当 n = 6 时，作用域的数量是 75105，这是一个显着的增加。因此，如果有人可以帮助我降低制作示波器的速度，我将不胜感激！

Answer 1

你在每次迭代中调用一个 Pascal 函数三次（而且，他们中的每一个都调用它越来越多......）。因此，您最终的复杂度是 O(n!)。只需存储每个帕斯卡结果的计算：

count = 0 
def Pascal(n):
    global count
    count += 1 

    pasc_list = [] 
    i = 0 
    j = i+1
    dictionary = {0:[1],1:[1,1]}

    if n in dictionary:
        return dictionary[n]

    else:
        pasc_list.append(1)
        p = Pascal(n-1)  # <-------------------- HERE!!
        while j < len(p):
            pasc_list.append(p[i] + p[j])
            i += 1 
            j = i+1 

        pasc_list.append(1)
        dictionary[n] = pasc_list

    return pasc_list

a = Pascal(7)
print(a)
print(count)

将打印：

[1, 7, 21, 35, 35, 21, 7, 1]
7

对递归要非常准确，不要在 loop-statements 中调用繁重的函数（比如 while j < len(Pascal(n-1)): <-- it is VERY bad idea to write code this way!）。为什么这么慢？

假设我们正在计算 Pascal(3):

在 P3 中我们在 while 中调用 P2。所以我们为 j[0]-index 调用 P2，在它内部调用 2 次，在下一次迭代（j[1]-index）中调用另外 3 次。在每个 P2 迭代中，我们将 P1 迭代再调用 3 次（手动 P1 迭代是第 4 次）。我们对 P4 重复整个过程 4 次，对 P5 重复 16 次，而且越来越多......就在你的代码如此缓慢的时候。

Answer 2

要在 Python 中正确使用记忆，请使用可变默认参数，通常命名为 memo:

count = 0 

def Pascal(n, memo={0:[1],1:[1,1]}):
    global count
    count += 1 

    pasc_list = [] 
    i = 0 
    j = i+1

    if n in memo:
        return memo[n]

    else:
        pasc_list.append(1)
        while j < len(Pascal(n-1)):
            pasc_list.append(Pascal(n-1)[i] + Pascal(n-1)[j])
            i += 1 
            j = i+1 

        pasc_list.append(1)
        memo[n] = pasc_list

    return pasc_list

a = Pascal(7)
print(a)
print(count)

输出：

c:\srv\tmp> python pascal.py
[1, 7, 21, 35, 35, 21, 7, 1]
70

你还应该把记忆 return 作为你的函数做的第一件事：

def Pascal(n, memo={0:[1],1:[1,1]}):
    if n in memo:
        return memo[n]

    global count
    count += 1 

    pasc_list = [] 
    i = 0 
    j = i+1

    pasc_list.append(1)
    while j < len(Pascal(n-1)):
        pasc_list.append(Pascal(n-1)[i] + Pascal(n-1)[j])
        i += 1 
        j = i+1 

    pasc_list.append(1)
    memo[n] = pasc_list

    return pasc_list

输出：

c:\srv\tmp> python pascal.py
[1, 7, 21, 35, 35, 21, 7, 1]
6

Answer 3

记忆无法弥补糟糕的算法。在这种情况下，它不能弥补任何东西。考虑删除记忆逻辑的清理代码版本：

count = 0

def Pascal(n):
    global count

    count += 1

    pasc_list = [1]

    if n > 0:

        i = 0
        j = i + 1

        previous = Pascal(n - 1)

        while j < len(previous):
            pasc_list.append(previous[i] + previous[j])
            i += 1
            j = i + 1

        pasc_list.append(1)

    return pasc_list

a = Pascal(10)

print(a)
print(count)

（此解决方案、@thebjorn 和 @vurmux 都无法使用默认的 Python 堆栈分配达到 Pascal(1000)。）如果我们计时 @vurmux 接受的答案，以及我上面的答案，循环遍历每个从 0 到 900 的行：

for n in range(900):
    print(Pascal(n))

结果相同：

> time python3 no-memoization.py > /dev/null
52.169u 0.120s 0:52.36 99.8%    0+0k 0+0io 0pf+0w
> time python3 memoization.py > /dev/null
52.031u 0.125s 0:52.23 99.8%    0+0k 0+0io 0pf+0w
>

如果我们采用上面的 no-memoization 解决方案，并简单地添加 Python 自己的 lru-cache 装饰器：

from functools import lru_cache

count = 0

@lru_cache()
def Pascal(n):
# ...

我们得到了显着 (100x) 的加速：

> time python3 lru_cache.py > /dev/null
0.556u 0.024s 0:00.59 96.6% 0+0k 0+0io 0pf+0w
>

正如我们对@thebjorn 的 (+1) 解决方案所做的那样，它正确地重用了字典缓存，而不是在每次调用时重新分配它。

重定向到文件时，所有输出都是相同的。（很多时候我将 functools:lru-cache 添加到一个函数中只是为了发现它实际上减慢了它的速度——也就是说，不是这个优化的好候选者。）

专注于编写一个好的算法并尽可能地调整它。然后，研究记忆化等技术。但是做个计时看看是不是真的赢了。

在使用 Memoization 和 Recursion 时，如何改进计算第 N 行 Pascals 三角形的代码？

How can I improve my code for calculating the Nth row of Pascals Triangle while using Memoization and Recursion?

python

recursion

memoization