如何在使用Memoization和Recursion时改进计算Pascals Triangle的第N行的代码？
我一直在修改递归，并决定使用它来计算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，这是一个戏剧性的增长。因此，如果有人能帮助我降低作用域的制造速度，我将不胜感激！
回答 2
Stack Overflow用户
发布于 2019-05-21 02:58:33
要在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]
6Stack Overflow用户
发布于 2019-05-21 13:53:11
记忆不能弥补糟糕的算法。在这种情况下，它不能弥补任何东西。考虑删除了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这样的技术。但一定要计时，看看这是否真的是一场胜利。
https://stackoverflow.com/questions/56226546
复制相似问题