为什么将键按顺序插入到python dict中比为无序编写更快

Question

我一直在创建巨大的dicts(数百万条目),我注意到如果我用密钥创建它们以便它更快.

我想它与哈希函数的冲突有关,但有人可以解释它为什么会发生,如果它在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

Answer 1

我几乎可以肯定这是正在发生的事情:当你第一次创建时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通过使用适当的键对这些字符串进行排序来构建.在我的机器上,这反转了两个测试的运行时间.