Python：嵌套字典 vs.元组键（调用嵌套字典较快）

Question

我注意到，在许多情况下，从嵌套字典中检索数据比使用元组键的字典更快。这似乎与此处所说的相矛盾。（来源）能否有人解释一下导致这种情况的原因？我的问题是，更快的方法似乎不太符合“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

在我看来，这是一个非常重要的区别。

- TimY

Answer 1

首先，您所进行的两个分析并不完全正确。在第一种情况下，您正在解包键，然后重新打包它们以获取值。

我得到的时间是：

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)，因此它们需要最少的哈希时间，而元组必须计算它们所有元素的哈希值并且将它们连接在一起。

• 每次访问字典键时，字典都必须检查键的相等性，并且比较元组比比较整数要慢。

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

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

嵌套序列往往很难处理，您经常需要使用嵌套循环来处理它们，这意味着更多的代码和不易维护的代码。

- Bakuriu

Answer 2

似乎对元组进行哈希处理有点昂贵。比起创建新字典并在插入时进行整数查找更为耗时。

- sanyi