python dict 搜索键很慢吗？

Question

在下面的代码中，rel_column 是一个字符串，'id_map' 是一个 python 字典，它有 220 万个键值对。

if rel_column in id_map:
   node_ids = id_map[rel_column]

在调试速度瓶颈问题时，我的同事说这段代码是导致缓慢的原因。他说“if”语句需要 log(n) 时间，但我的印象是，在映射或集合中搜索键时，复杂度是常数时间 O(1)。考虑到字典的总大小只有220万个，这不应该是速度瓶颈。

我很困惑。我的同事说得对吗？

Answer 1

当有疑问时，进行基准测试。任意选择长度为 8 的随机字符串作为键和值，并使用问题中指定的大小。

import random
import string
import timeit

def randstr(N):
    return ''.join(random.choice(string.ascii_uppercase + string.digits) for _ in range(N))

id_map = {randstr(8): randstr(8) for _ in range(int(2e6))}

# key not present
x = randstr(8)
print(timeit.timeit(stmt=lambda: id_map[x] if x in id_map else None, number=1000000))

# key present, first with in/[], then with .get()
x = random.choice(list(id_map.keys()))
print(timeit.timeit(stmt=lambda: id_map[x] if x in id_map else None, number=1000000))
print(timeit.timeit(stmt=lambda: id_map.get(x, None), number=1000000))

结果：

0.11468726862221956
0.13692271895706654
0.13748164474964142

结论（Python 3.9，密钥分布均匀，数据量小，2M条目）：

• 未找到密钥比找到密钥稍快
• in接下来的[]速度与.get()
• 每次查找的时间均为 100 纳秒左右