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

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

这也是我想问的问题。看起来，使用字符串作为键的字典效率更高，但访问速度其实差不多。我用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))

这是运行的结果：

Int dict lookup: 12.395361029000014
Str dict lookup: 12.097380312000041
Mix dict lookup: 12.109765773000163

Answer 2

我觉得你的测试结果其实并不能说明太多问题。

你在Dint中测试字符串的速度是最快的：一般来说，检查一个不在字典里的东西通常会很快，但这只是因为你运气好，第一次就碰到了一个空的单元格，所以查找可以很快结束。如果你运气不好，碰到一个或多个满的单元格，那可能会比实际找到东西的情况还要慢。

在字典中测试一个任意字符串时，需要计算这个字符串的哈希值。这个过程的耗时和字符串的长度成正比，但Python有个聪明的办法，只会为每个字符串计算一次哈希值。因为你在测试中反复使用同一个字符串，所以计算哈希值的时间只在第一次时消耗，后面99999999次就不会再计算了。如果你每次都用不同的字符串，结果就会大不相同。

Python对字典进行了优化，特别是当键是字符串时。总体来说，如果你多次使用相同的字符串键，速度会稍微快一些，但如果你每次都要把整数转换成字符串再查找，那你就会失去这个优势。

Answer 3

CPython中的dict（字典）实现其实是专门为字符串类型的键查找进行了优化。它有两个不同的查找函数，分别是lookdict和lookdict_string（在Python 3中是lookdict_unicode），可以用来进行查找。当你查找字符串类型的键时，Python会使用这个优化过的版本；如果你查找的不是字符串类型的数据，它就会使用一个更通用的函数。你可以下载CPython的源代码，查看dictobject.c文件，了解具体的实现。

由于这种优化，当字典中的所有键都是字符串时，查找速度会更快。