python - 需要帮助了解如何实现内存

Question

我正在尝试完成实现记忆化的第一个练习，但我不知道如何解决这个问题:

我有一个函数可以将输入文本换行到指定的行长度，然后打印结果。

def wrap(input, lineSpaces):
    if len(input) <= lineSpaces:
        return input
    temp = input.rfind(" ", 0, lineSpaces - 1)
    if temp == -1:
        return input
    else:
        return input[:temp+1]+'\n'+wrap(input[temp+1:], lineSpaces)

# I/O
list = []
M = int(raw_input())
for i in xrange(0, M):
    lineSpaces = int(raw_input())
    input = raw_input()
    list.append(wrap(input, lineSpaces))

for i in list:
    print i+"\n"

我目前的内存尝试:

def wrap(input, lineSpaces):
    if len(input) <= lineSpaces:
        return input
    temp = input.rfind(" ", 0, lineSpaces - 1)
    if temp == -1:
        return input
    else:
        return input[:temp+1]+'\n'+wrap(input[temp+1:], lineSpaces)

# I/O
inputList = []
lineSpacesList = []
unmemoizedOutput = []
M = int(raw_input())
memo = {}

for i in xrange(0, M):
    lineSpacesList.append(int(raw_input()))
    inputList.append(raw_input())
    unmemoizedOutput.append(wrap(inputList[i], lineSpacesList[i]))

for i in unmemoizedOutput:
    if not i in memo:
        for j in xrange(0, M):
            memo[i] = i + wrap(inputList[j], lineSpacesList[j])
    print memo[i]+"\n"

我没有得到我想要的输出。当我输入时:

3
20
Lorem ipsum dolor sit amet, consectetuer adipiscing elit. A
30
Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Aenean commodo ligula eget dolor. Aenean massa. Cu
36
Lorem ipsum dolor sit amet,

我得到:

Lorem ipsum dolor 
sit amet, 
consectetuer 
adipiscing elit. ALorem ipsum dolor sit amet,

Lorem ipsum dolor sit amet, 
consectetuer adipiscing 
elit. Aenean commodo ligula 
eget dolor. Aenean massa. CuLorem ipsum dolor sit amet,

Lorem ipsum dolor sit amet,Lorem ipsum dolor sit amet,

这显然是错误的。看起来我的“内存”版本所做的唯一一件事就是将最终输出附加到所有其他输出。所以，我认为我对如何为这个功能实际实现记忆化的理解是完全错误的。有人可以指出我正确的方向吗？

Answer 1

内存是你在实现一个功能时做的事情，而不是在使用它的时候。当您产生输出时，您记录下此调用的输入对应于您产生的输出。当你接到电话时，你会检查你是否已经为你收到的输入存储了输出，如果有，你就使用存储的输出。它看起来像这样:

_memodict = {}
def memoized_function(input):
    try:
        return _memodict[input]
    except KeyError:
        # do what you would have normally done
        _memodict[input] = output
        return output

或者像这样:

import functools
def memoize(function):
    _memodict = {}

    # This decorator just makes the new function look a bit nicer
    @functools.wraps(function)
    def wrapped(*args):
        try:
            return _memodict[args]
        except KeyError:
            output = _memodict[args] = function(*args)
            return output
    return wrapped

@memoize
def function(input):
    # Exactly what you would have written normally