字典访问速度与字符串键的整数键比较

Question

我有一本很大的字典,我必须多次查阅这些字典.我的键是整数,但代表标签,所以不需要添加,减去等...我最终试图评估字符串键和整数键字典之间的访问时间,这是结果.

from timeit import Timer

Dint = dict()
Dstr = dict()

for i in range(10000):
    Dint[i] = i
    Dstr[str(i)] = i


print 'string key in Dint',
print(Timer("'7498' in Dint", "from __main__ import Dint").timeit(100000000))
print 'int key in Dint',
print(Timer("7498 in Dint", "from __main__ import Dint").timeit(100000000))
print 'string key in Dstr',
print(Timer("'7498' in Dstr", "from __main__ import Dstr").timeit(100000000))
print 'int key in Dstr',
print(Timer("7498 in Dstr", "from __main__ import Dstr").timeit(100000000))

每次重现的运行之间产生轻微变化:

string key in Dint 4.5552944017
int key in Dint 7.14334390267
string key in Dstr 6.69923791116
int key in Dstr 5.03503126455

它是否证明使用带字符串的字典作为键比使用整数作为键更快？

Answer 1

CPython的dict实现实际上是针对字符串键查找进行了优化的.有两种不同的功能,lookdict和lookdict_string(lookdict_unicode在Python 3),其可以被用于执行查找.Python将使用字符串优化版本,直到搜索非字符串数据,之后使用更通用的函数.您可以通过下载CPython的源代码并阅读来查看实际实现dictobject.c.

作为此优化的结果,当dict具有所有字符串键时,查找更快.

Answer 2

我担心你的时代并没有真正证明.

你在Dint中对字符串的测试是最快的:一般来说,测试任何不在字典中的东西很可能很快,但这只是因为你很幸运并且第一次点击一个空单元格以便查找可以终止.如果你运气不好并且选择了一个达到一个或多个完整单元格的值,那么它最终会比实际找到某些东西的情况慢.

在字典中测试任意字符串必须计算字符串的哈希码.这需要时间与字符串的长度成比例,但Python有一个巧妙的技巧,只为每个字符串计算一次.由于您在计时测试中反复使用相同的字符串,因此计算哈希值所花费的时间会丢失,因为它只会在第一次发生而不会发生在其他99999999次.如果你每次使用不同的字符串,你会得到一个非常不同的结果.

Python已经优化了字典代码,其中键是字符串.总的来说,您应该发现使用字符串键多次使用相同的键会稍快一些,但如果您必须在查找之前将整数转换为字符串,那么您将失去这一优势.

Answer 3

这也是我的问题。显然，带有字符串键的字典效率更高，但访问时间非常接近。我使用 Python 3 运行了以下代码：

import random
import timeit
import uuid

DICT_INT = dict()
DICT_STR = dict()
DICT_MIX = dict()

for i in range(2000000):
    DICT_INT[i] = uuid.uuid4().hex
    DICT_STR[str(i)] = uuid.uuid4().hex
    DICT_MIX[i if random.randrange(2) else str(i)] = uuid.uuid4().hex

def int_lookup():
    int_key = random.randrange(len(DICT_INT))
    str_key = str(int_key)
    mix_key = int_key if int_key % 2 else str_key
    return int_key in DICT_INT

def str_lookup():
    int_key = random.randrange(len(DICT_STR))
    str_key = str(int_key)
    mix_key = int_key if int_key % 2 else str_key
    return str_key in DICT_STR

def mix_lookup():
    int_key = random.randrange(len(DICT_MIX))
    str_key = str(int_key)
    mix_key = int_key if int_key % 2 else str_key
    return mix_key in DICT_MIX

print('Int dict lookup: ', end='')
print(timeit.timeit('int_lookup', 'from __main__ import int_lookup', number=1000000000))
print('Str dict lookup: ', end='')
print(timeit.timeit("str_lookup", 'from __main__ import str_lookup', number=1000000000))
print('Mix dict lookup: ', end='')
print(timeit.timeit("mix_lookup", 'from __main__ import mix_lookup', number=1000000000))

这是结果：

import random
import timeit
import uuid

DICT_INT = dict()
DICT_STR = dict()
DICT_MIX = dict()

for i in range(2000000):
    DICT_INT[i] = uuid.uuid4().hex
    DICT_STR[str(i)] = uuid.uuid4().hex
    DICT_MIX[i if random.randrange(2) else str(i)] = uuid.uuid4().hex

def int_lookup():
    int_key = random.randrange(len(DICT_INT))
    str_key = str(int_key)
    mix_key = int_key if int_key % 2 else str_key
    return int_key in DICT_INT

def str_lookup():
    int_key = random.randrange(len(DICT_STR))
    str_key = str(int_key)
    mix_key = int_key if int_key % 2 else str_key
    return str_key in DICT_STR

def mix_lookup():
    int_key = random.randrange(len(DICT_MIX))
    str_key = str(int_key)
    mix_key = int_key if int_key % 2 else str_key
    return mix_key in DICT_MIX

print('Int dict lookup: ', end='')
print(timeit.timeit('int_lookup', 'from __main__ import int_lookup', number=1000000000))
print('Str dict lookup: ', end='')
print(timeit.timeit("str_lookup", 'from __main__ import str_lookup', number=1000000000))
print('Mix dict lookup: ', end='')
print(timeit.timeit("mix_lookup", 'from __main__ import mix_lookup', number=1000000000))