5

我一直在创建巨大的字典（数百万个条目），我注意到如果我用键创建它们，它会更快。

我想这与哈希函数的冲突有关，但有人可以解释为什么会发生这种情况，以及它在 python 版本之间是否一致？

这里有一个人为的例子：

import timeit
import random

def get_test_data(num, size):
    olist, ulist = [], []
    for _ in range(num):
        otest = [str(i) for i in range(size)]
        utest = list(otest)
        random.shuffle(utest)
        olist.append(otest)
        ulist.append(utest)
    return olist, ulist

NUM_TESTS = 20
# Precalculate the test data so we only measure dict creation time
ordered, unordered = get_test_data(NUM_TESTS, 1000000)

def test_ordered():
    dict((k, k) for k in ordered.pop())

def test_unordered():
    dict((k, k) for k in unordered.pop())

print "unordered: ",
print timeit.timeit("test_unordered()",
                    setup="from __main__ import test_unordered, test_ordered",
                    number=NUM_TESTS)
print "ordered: ",
print timeit.timeit("test_ordered()",
                    setup="from __main__ import test_unordered, test_ordered",
                    number=NUM_TESTS)

我机器中的输出始终是：

(X)$ python /tmp/test.py 
unordered:  8.60760807991
ordered:  5.1214389801

我在 ubuntu 精确 x86_64 中使用 Python 2.7.3

4

2 回答 2

8

我几乎可以肯定这是怎么回事：当你第一次创建时otest，字符串按顺序存储在内存中。当您创建utest时，字符串指向相同的内存缓冲区，除了现在这些位置是乱序的，这会破坏无序测试用例的缓存性能。

这是证据。我已经get_test_data用这个版本替换了你的函数：

def get_test_data(num, size):
    olist, ulist = [], []
    for _ in range(num):
        nums = range(size)
        random.shuffle(nums)
        utest = [str(i) for i in nums]
        otest = list(utest)
        otest.sort(key=lambda x: int(x))
        olist.append(otest)
        ulist.append(utest)
    return olist, ulist

这个想法是我现在ulist在内存中连续构建字符串，然后olist通过使用适当的键对这些字符串进行排序来构建。在我的机器上，这颠倒了两个测试的运行时间。

于 2013-08-14T06:53:00.017 回答
2

检查python dict 的源代码，您可以看到连续的字符串或整数产生较少的冲突。这与@skishore 关于更好的缓存局部性的评论相结合可能是答案。

未来的主要微妙之处：从模拟随机性的意义上说，大多数散列方案都依赖于具有“良好”的散列函数。Python 没有：它最重要的散列函数（用于字符串和整数）在常见情况下非常有规律：

>>> map(hash, (0, 1, 2, 3))
[0, 1, 2, 3]
>>> map(hash, ("namea", "nameb", "namec", "named"))
[-1658398457, -1658398460, -1658398459, -1658398462]
>>>

这不一定是坏事！相反，在大小为 2**i 的表中，将低位 i 位作为初始表索引非常快，并且对于由连续范围的 int 索引的 dicts 完全没有冲突。当键是“连续的”字符串时，情况大致相同。因此，这在常见情况下提供了优于随机的行为，这是非常可取的。

于 2013-08-18T07:00:34.903 回答