6

Python 函数对象有一个名为的属性字典，该字典func_dict从函数外部可见并且是可变的，但在调用函数时不会修改。（我从昨天提出的问题的答案中了解到这一点（#1753232）：谢谢！）我正在阅读代码（在http://pythonprogramming.jottit.com/functional_programming），它记住了斐波那契数的计算并想，“为什么不使用该func_dict属性进行记忆？” 它起作用了（见下文；输出在代码的末尾。）。这有点像有一个可用的类属性，但在对象之外有初始化代码（在这种情况下，不是一个类，而是一个函数）。

我想知道使用此属性可以完成哪些类似（或不同）的技巧？

def fib(n):
    if n in fib.cache:
        print "found fib.cache[%d] = %d: " %(n, fib.cache[n])
        return fib.cache[n]
    else:
        print "fib.cache[%d] = fib(%d) + fib(%d)" % (n, n-1, n-2)
        fib.cache[n] = fib(n-1) + fib(n-2)
        print "modified fib.cache: ", fib.cache
        return fib.cache[n]

fib.cache = {0:0, 1:1}

for x in range(7):
    print "==================>", x
    print fib( x)

"""
==================> 0
found fib.cache[0] = 0: 
0
==================> 1
found fib.cache[1] = 1: 
1
==================> 2
fib.cache[2] = fib(1) + fib(0)
found fib.cache[1] = 1: 
found fib.cache[0] = 0: 
modified fib.cache:  {0: 0, 1: 1, 2: 1}
1
==================> 3
fib.cache[3] = fib(2) + fib(1)
found fib.cache[2] = 1: 
found fib.cache[1] = 1: 
modified fib.cache:  {0: 0, 1: 1, 2: 1, 3: 2}
2
==================> 4
fib.cache[4] = fib(3) + fib(2)
found fib.cache[3] = 2: 
found fib.cache[2] = 1: 
modified fib.cache:  {0: 0, 1: 1, 2: 1, 3: 2, 4: 3}
3
==================> 5
fib.cache[5] = fib(4) + fib(3)
found fib.cache[4] = 3: 
found fib.cache[3] = 2: 
modified fib.cache:  {0: 0, 1: 1, 2: 1, 3: 2, 4: 3, 5: 5}
5
==================> 6
fib.cache[6] = fib(5) + fib(4)
found fib.cache[5] = 5: 
found fib.cache[4] = 3: 
modified fib.cache:  {0: 0, 1: 1, 2: 1, 3: 2, 4: 3, 5: 5, 6: 8}
8
"""
4

2 回答 2

7

请注意：该fib.cache技巧仅在fib确实是在执行时处于活动状态的范围内的相关函数对象的名称时才有效（例如，当您照常装饰它时，您必须将缓存的起始值分配给装饰器包装器，而不是被装饰的函数——如果在那之后它被进一步装饰，事情就会破裂）。

与标准的记忆习语相比，这有点脆弱：

def fib(n, _memo={0:1, 1:1}):
    if n in _memo:
        return _memo[n]
    else:
        _memo[n] = fib(n-1) + fib(n-2)
        return _memo[n]

或等效的装饰器。标准的成语也更快（虽然不是很多）——把它们都放在 mem.py 中，名称为 fib1（.cache-trick 一个，没有打印和未装饰）和 fib2（我的版本），我们看到......：

$ python -mtimeit -s'import mem' 'mem.fib1(20)'
1000000 loops, best of 3: 0.754 usec per loop
$ python -mtimeit -s'import mem' 'mem.fib2(20)'
1000000 loops, best of 3: 0.507 usec per loop

所以标准成语版本节省了大约 33% 的时间，但那是几乎所有调用实际上都命中了 memoization 缓存（这是在百万循环中的第一个之后填充的）——fib2 的速度优势在缓存未命中时更小，因为它来自更高的访问速度_memo（局部变量）与fib.cache（全局名称，fib，然后是其属性，缓存），并且缓存访问在缓存命中占主导地位（没有别的；-）但还有一点额外的在缓存未命中时工作（两个函数相等）。

无论如何，不​​要想在你的游行上下雨，但是当你发现一些新的很酷的想法时，一定要在“稳健性”和性能（如果你是缓存，大概你关心性能;-)。

于 2009-11-19T03:12:41.670 回答
1

我一直使用这种技术进行记忆。它使用这样一个事实，即您可以调用一个不是函数的对象，只要该对象__call__定义了它的方法。无论出于何种原因，我都没有想到背后的方法，也没有 Alex Martelli 的方法。我猜它的性能与 behindthefall 的方式大致相同，因为它的工作方式大致相同。也许慢一点。但正如链接页面指出的那样，“fib() 的定义现在是“显而易见的”定义，没有缓存代码模糊算法”，这有点好。

于 2009-12-30T18:48:43.880 回答