python - Memoization 无法正常工作，来自 MIT 开放课件“计算机科学与编程导论”第 21 课的 python 代码

Question

我是编码新手，正在学习 MIT 开放课件 6.00 课程“计算机科学与编程导论”。第 21 课专门介绍了动态规划和记忆。

作业/讲座代码是一个优化程序，从一组可放入容量有限的袋子中的物品中找到价值最大的物品组合。这是提供的代码的一部分：

def solve(toConsider, avail):
    global numCalls
    numCalls += 1
    if toConsider == [] or avail == 0:
        result = (0, ())
    elif toConsider[0].getWeight() > avail:
        result = solve(toConsider[1:], avail)
    else:
        nextItem = toConsider[0]
        #Explore left branch
        withVal, withToTake = solve(toConsider[1:],
                                    avail - nextItem.getWeight())
        withVal += nextItem.getValue()
        #Explore right branch
        withoutVal, withoutToTake = solve(toConsider[1:], avail)
        #Choose better branch
        if withVal > withoutVal:
            result = (withVal, withToTake + (nextItem,))
        else:
            result = (withoutVal, withoutToTake)
    return result

def fastSolve(toConsider, avail, memo = None):
    global numCalls
    numCalls += 1
    if memo == None:
        #Initialize for first invocation
        memo = {}
    if (len(toConsider), avail) in memo:
        #Use solution found earlier
        result = memo[(len(toConsider), avail)]
        return result
    elif toConsider == [] or avail == 0:
        result = (0, ())
    elif toConsider[0].getWeight() > avail:
        #Lop off first item in toConsider and solve
        result = fastSolve(toConsider[1:], avail, memo)
    else:
        item = toConsider[0]
        #Consider taking first item
        withVal, withToTake = fastSolve(toConsider[1:],
                                        avail - item.getWeight(),
                                        memo)
        withVal += item.getValue()
        #Consider not taking first item
        withoutVal, withoutToTake = fastSolve(toConsider[1:],
                                              avail, memo)
        #Choose better alternative
        if withVal > withoutVal:
            result = (withVal, withToTake + (item,))
        else:
            result = (withoutVal, withoutToTake)
    #Update memo
    memo[(len(toConsider), avail)] = result
    return result

import time
import sys
sys.setrecursionlimit(2000)

def test(maxVal = 10, maxWeight = 10, runSlowly = False):
    random.seed(0)
    global numCalls
    capacity = 8*maxWeight
    print '#items, #num taken, Value, Solver, #calls, time'
    for numItems in (4,8,16,32,64,128,256,512,1024):
        Items = buildManyItems(numItems, maxVal, maxWeight)
        if runSlowly:
            tests = (fastSolve, solve)
        else:
            tests = (fastSolve,)
        for func in tests:
            numCalls = 0
            startTime = time.time()
            val, toTake = func(Items, capacity)
            elapsed = time.time() - startTime
            funcName = func.__name__
            print numItems, len(toTake), val, funcName, numCalls, elapsed

在讲座中，当讲师运行此测试代码时，由于使用了 memoization，fastSolve 的性能存在巨大差异，但是当我运行此代码时，memoization 似乎不起作用 - 没有区别Solve 和 fastSolve 之间的调用次数或运行时间。

我知道这段代码是为早期版本的python（我相信是2.7）编写的，我目前正在使用python 3.8.0。

谁能帮我确定为什么 fastSolve/memoization 没有按预期工作？

标签： pythonpython-2.7memoizationpython-3.8