在Python中为字典创建默认值

Question

让我们编写一个能够缓存计算结果的方法。

“如果”方法：

def calculate1(input_values):
    if input_values not in calculate1.cache.keys():
        # do some calculation
        result = input_values
        calculate1.cache[input_values] = result
    return calculate1.cache[input_values]
calculate1.cache = {}

"Except"方法:

def calculate2(input_values):
    try:
       return calculate2.cache[input_values]
    except AttributeError:
       calculate2.cache = {}
    except KeyError:
       pass
    # do some calculation
    result = input_values
    calculate2.cache[input_values] = result
    return result

“get/has” 方法:

def calculate3(input_values):

    if not hasattr(calculate3, cache):
        calculate3.cache = {}

    result = calculate3.cache.get(input_values)
    if not result:
        # do some calculation
        result = input_values
        calculate3.cache[input_values] = result
    return result

有没有其他更快的方法？哪个更符合Python风格？你会使用哪一个？

注意：速度上存在差异：

calculate = calculateX # depening on test run
for i in xrange(10000):
    calculate(datetime.utcnow())

结果 time python test.py:

calculate1: 0m9.579s
calculate2: 0m0.130s
calculate3: 0m0.095s

- Martin Tóth

---

你的基准测试看起来有问题 - 我不相信第三种方法会比其他方法快100倍。你有没有偶然重复使用了第一次运行时的缓存？ - Eli Bendersky

使用键确实会减慢速度，至少在Python 2中（其中它生成一个列表）。这也意味着线性搜索。为什么不只是使用input_values not in calculate1.cache？这是一个简单的哈希查找，可能接近其他方法（例如，<0.300秒）。 - user395760

如果你想测量Python代码的执行时间，你可以使用timeit模块，它比time函数给出的答案更准确。 - David Webb

你的基准测试似乎不太恰当；至少在我的系统上，它没有使用来自缓存的值，因为每个循环所需时间超过了一微秒。添加“print len(calculate.cache)”语句，并尝试添加某些检查缓存的代码。也许可以用"datetime.utcnow().microsecond % 500"来检查缓存。 - dr jimbob

嗯，我认为如果你只是想要进行记忆化，defaultdict 可能并不会有特别大的帮助。在 Python 中，最好使用一个装饰器类来进行记忆化。请参见下面的答案。 - dr jimbob

Answer 1

使用 collections.defaultdict。它专门为此目的设计而来。

- unutbu

---

defaultdict看起来很合理，但我想知道它是否比其他方法更快？有时我在使用这种Python扩展时会遇到不好的意外。 - kriss

即使它变慢了，有什么关系呢？这是正确的解决方案。如果它成为瓶颈，就用手动调优的实现替换它。如果它被纳入标准库中，至少它的复杂度可能是可以接受的。 - user395760

@kriss 使用 defaultdict，运行时间为 0m0.101s。 - Martin Tóth

@delnan：OP要求性能，显然他很在意。除此之外，我不同意Pythonic思维方式中“只有一种正确的解决方案”的观点，这是主观的。我喜欢知道我使用的方法是否简洁、简单、快速，同时也可以做出明智的选择。但在这种情况下，defaultdict显然具有简洁、高效和简单的特点。 - kriss

无论如何，这正是我寻求的答案（尽管我的问题与 OP 的有所不同）——现在我并不关心性能，只关心可读性/可维护性。谢谢你，unutbu！ :) - Henrik Heimbuerger

Answer 2

当然，毕竟这是Python: 只需使用defaultdict即可。

- Aaron Digulla

Answer 3

如果你想要使用记忆化技术，最好使用Memoize类和装饰器。

class Memoize(object):
    def __init__(self, func):
        self.func = func
        self.cache = {}

    def __call__(self, *args):
        if args not in self.cache:
            self.cache[args] = self.func(*args)
        return self.cache[args]

现在定义一些需要进行记忆化的函数，比如一个键强化函数，它对一个字符串哈希做了一百万次md5sum操作。

import md5

def one_md5(init_str):
    return md5.md5(init_str).hexdigest()

@Memoize
def repeat_md5(cur_str, num=1000000, salt='aeb4f89a2'):
    for i in xrange(num):
        cur_str = one_md5(cur_str+salt)
    return cur_str

@Memoize函数装饰器等效于定义函数，然后定义repeat_md5 = Memoize(repeat_md5)。当你对特定的一组参数第一次调用它时，函数需要大约1秒钟来计算；而下一次调用将近乎瞬间完成，因为它从缓存中读取。

至于备忘录方法，只要你不做傻事（比如第一种方法中你使用if key in some_dict.keys()而非if key in some_dict），就不应该有太大的区别。第一种方法很糟糕，因为你首先从字典生成一个数组，然后检查键是否在这个数组中；而不是直接检查键是否在字典中（参见像Pythonista一样编程）。此外，捕获异常的速度比使用if语句要慢（你必须创建一个异常，然后异常处理程序必须处理它，然后你才能捕获它）。

- dr jimbob