3

我注意到，在许多情况下，从嵌套字典中检索数据比从带有元组键的字典中检索数据要快得多。这似乎与这里所说的相矛盾。谁能解释一下是什么原因造成的？我的问题是，更快的方法似乎不那么“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

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

4

2 回答 2

2

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

我得到的时间是：

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），因此它们需要最少的时间来散列，元组必须计算所有元素的散列并将它们连接在一起。

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

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

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

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

于 2013-08-29T08:41:57.127 回答
0

似乎散列元组有点昂贵。不仅仅是创建一个新的字典并在插入时进行整数锁定。

于 2013-08-29T08:37:40.450 回答