记忆化处理器

Question

创建一个像下面这样的类来处理记忆化过程，是不是“好做法”呢？ 记忆化的好处非常明显（在某些情况下，比如这个例子中，函数调用次数从501003减少到1507，CPU时间从1.409秒降到0.006秒），所以看起来像这样的类会很有用。

不过，我看到关于使用eval()的评论几乎都是负面的。在这种方法提供的灵活性面前，使用它是否可以被理解呢？

这个方法可以自动保存任何返回的值，但代价是会失去一些副作用。谢谢。

import cProfile

class Memoizer(object):
    """A handler for saving function results."""
    def __init__(self):
        self.memos = dict()
    def memo(self, string):
        if string in self.memos:
            return self.memos[string]
        else:
            self.memos[string] = eval(string)
            self.memo(string)

def factorial(n):
    assert type(n) == int
    if n == 1:
        return 1
    else:
        return n * factorial(n-1) 

# find the factorial of num
num = 500
# this many times
times = 1000

def factorialTwice():
    factorial(num)
    for x in xrange(0, times):
        factorial(num)
    return factorial(num)

def memoizedFactorial():
    handler = Memoizer()
    for x in xrange(0, times):
        handler.memo("factorial(%d)" % num)
    return handler.memo("factorial(%d)" % num)


cProfile.run('factorialTwice()')

cProfile.run('memoizedFactorial()')

Answer 1

eval 这个词常常被拼错成 evil，主要是因为在运行时执行“字符串”这件事涉及很多安全问题。你有没有充分处理好代码？引号呢？还有一堆让人头疼的事情。你的记忆处理器虽然能工作，但其实这并不是 Python 的标准做法。MAK 的方法更符合 Python 的风格。我们来做几个实验。

我把两个版本都编辑了一下，只用 100 作为输入运行了一次。我还把 Memoizer 的实例化部分移了出来。以下是结果。

>>> timeit.timeit(memoizedFactorial,number=1000)
0.08526921272277832h
>>> timeit.timeit(foo0.mfactorial,number=1000)
0.000804901123046875

另外，你的版本需要在要记忆的函数外面加一个包装，这个包装需要写成字符串。这看起来很糟糕。MAK 的解决方案就很干净，因为“记忆化的过程”被封装在一个单独的函数里，可以方便地应用到任何耗时的函数上，而且不会显得突兀。这种做法并不是很符合 Python 的风格。如果你感兴趣，我在我的 Python 教程里有一些关于如何写这种装饰器的细节，链接在这里：http://nibrahim.net.in/self-defence/。

Answer 2

你可以在不使用 eval 的情况下进行记忆化处理。

下面是一个（非常基础的）记忆化函数：

def memoized(f):
    cache={}
    def ret(*args):
        if args in cache:
            return cache[args]
        else:
            answer=f(*args)
            cache[args]=answer
            return answer
    return ret

@memoized
def fibonacci(n):
    if n==0 or n==1:
        return 1
    else:
        return fibonacci(n-1)+fibonacci(n-2)

print fibonacci(100)