Python:嵌套字典与元组键(调用前者要快得多)

Question

我注意到，在许多情况下，从嵌套字典中检索数据比从具有元组键的字典中检索数据要快得多。这似乎与所说的矛盾here .谁能解释一下是什么原因造成的？我的问题是更快的方法似乎不那么“pythonic”并且会导致巨大的丑陋嵌套字典(例如 a_dict[a][b][c][d] 而不是 a_dict[a,b,c,d])。

以下是使用整数作为键时发生这种情况的示例:

使用元组:

print timeit.timeit('''
for (int1, int2) in indexes:
    x[ int1, int2 ]
''', setup='''
x={}
indexes = []
for int1 in xrange(1000):
    for int2 in xrange(1000):
        x[ int1, int2 ] = 'asd'
        indexes.append((int1, int2))
''', number = 100)

使用嵌套字典:

print timeit.timeit('''
for (int1, int2) in indexes:
    x[int1][ int2 ]
''', setup='''
x={}
indexes = []
for int1 in xrange(1000):
    x[int1] = {}
    for int2 in xrange(1000):
        x[ int1 ][int2] = 'asd'
        indexes.append((int1, int2))
''', number = 100)

结果:

36.8627537348
12.2223380257

在我看来，这是一个非常重要的差异。

Answer 1

首先，您所做的两个分析并不完全正确。在第一种情况下，您要解压缩 key ，然后重新打包它们以获得值。

我得到的时间是:

In [3]: timeit.timeit('''
   ...: for key in indexes:
   ...:     x[key]
   ...: ''', setup='''
   ...: x={}
   ...: indexes = []
   ...: for a in range(1000):
   ...:     for b in range(1000):
   ...:         x[a,b] = 'asd'
   ...:         indexes.append((a, b))
   ...: ''', number=100)
Out[3]: 28.43928542699996
In [5]: timeit.timeit('''
   ...: for key in indexes:
   ...:     a,b = key
   ...:     x[a][b]
   ...: ''', setup='''
   ...: x={}
   ...: indexes = []
   ...: for a in range(1000):
   ...:     x[a] = {}
   ...:     for b in range(1000):
   ...:         x[a][b] = 'asd'
   ...:         indexes.append((a, b))
   ...: ''', number=100)
Out[5]: 10.23602621900045

(使用python3.3)，差异已经小了一点。你的基准显示有 3 倍的差异，我的有 2.78 倍的差异。

性能上的差异是由于:

• 元组需要更多时间来散列。事实上，整数散列到它们自己(hash(1) -> 1)，因此它们花费最少的时间来散列，元组必须计算它们所有元素的散列和连接他们在一起。

• 每次访问字典键时，字典都必须检查键是否相等，比较元组比比较整数慢。

我想指出您的基准没有多大意义。为什么要将所有键存储在列表中？请注意，使用元组键，您可以简单地遍历字典，而在嵌套情况下，您必须使用嵌套循环。此外，嵌套字典可能会使用更多内存。

在使用高度嵌套的字典之前，您必须确保字典访问是瓶颈。而且我怀疑它是否会成为瓶颈，特别是如果您除了访问/存储字典中的项目之外还做任何其他事情。

嵌套序列往往难以处理，您通常需要嵌套循环来处理它们，这意味着更多代码和更少可维护代码。