使用整数键和字符串键访问字典的速度比较

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

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

- fallino

---

如果您使用多个键，那将更好。 - Marcin

Answer 1

CPython的dict实现实际上是针对字符串键查找进行了优化。有两个不同的函数，lookdict和lookdict_string（Python 3中为lookdict_unicode），可用于执行查找。Python将使用针对字符串优化的版本，直到搜索非字符串数据，之后才使用更通用的函数。您可以通过下载CPython的源代码并阅读dictobject.c来查看实际实现。

由于这种优化，当一个dict具有所有字符串键时，查找速度会更快。

- Zach Kelling

Answer 2

我很抱歉，你的测试结果并不能证明太多东西。在Dint中，对字符串的测试是最快的：通常情况下，对于字典中不存在的任何项进行测试都很可能很快，但这只是因为你很幸运地第一次就命中了一个空单元格，所以查找可以终止。如果你不幸选择了一个命中一个或多个已占用单元格的值，那么它可能比实际找到某些内容的情况更慢。

在字典中测试任意字符串需要计算字符串的哈希码。这需要与字符串长度成正比的时间，但Python有一个巧妙的技巧，每个字符串仅计算一次哈希码。由于您在定时测试中多次使用相同的字符串，因此用于计算哈希的时间会因仅在第一次发生而不是其他99999999次而丢失。如果每次使用不同的字符串，则会得到非常不同的结果。

Python针对字符串键的字典具有优化代码。总体而言，您应该发现在多次使用相同键的情况下使用字符串键略快，但如果您必须在查找之前将整数转换为字符串，则会失去这种优势。

- Duncan

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))

这是结果：

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

- h.nodehi

---

这段代码测量了像random.randrange、字符串转换、三元运算符等东西，因此结果是有偏差的。一般来说，整数查找比字符串查找更快。 - Mihail Slavchev

Answer 4

正如其他人所说，Python提供了专门的字典，通常整数查找比字符串查找更快。

正确的测试应该是这样的

import random
import timeit
import uuid

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

KEYS_INT = []
KEYS_STR = []
KEYS_MIX = []

for i in range(2000000):
    key_int = i
    key_str = str(i)
    key_mix = i if random.randrange(2) else str(i)
    KEYS_INT.append(key_int)
    KEYS_STR.append(key_str)
    KEYS_MIX.append(key_mix)
    DICT_INT[key_int] = uuid.uuid4().hex
    DICT_STR[key_str] = uuid.uuid4().hex
    DICT_MIX[key_mix] = uuid.uuid4().hex

def int_lookup():
    for key in KEYS_INT:
        x = key in DICT_INT

def str_lookup():
    for key in KEYS_STR:
        x = key in DICT_STR

def mix_lookup():
    for key in KEYS_MIX:
        x = key in DICT_MIX

print('Int dict lookup:', timeit.timeit(int_lookup, number=100))
print('Str dict lookup:', timeit.timeit(str_lookup, number=100))
print('Mix dict lookup:', timeit.timeit(mix_lookup, number=100))

否则，您可以测量像random.randrange、字符串转换、三元运算符等内容。

在我的机器上的结果是：

Int dict lookup: 4.126786124999999
Str dict lookup: 22.824602666999997
Mix dict lookup: 19.024495125

- Mihail Slavchev