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

Question

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

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

要在Python语言中正确使用memoization，请使用可变的默认参数，通常命名为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

您还应该将memoization返回作为您的函数做的第一件事：

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 2

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

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
>

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

from functools import lru_cache

count = 0

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

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

> 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这样的技术。但一定要计时，看看这是否真的是一场胜利。