是python字典非常慢的搜索键?

Question

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

if rel_column in id_map:
node_ids = id_map[rel_column]

在调试速度瓶颈问题时，我的同事说这段代码是导致速度缓慢的原因。他说if语句需要log(n)的时间，但我的印象是，在map或set中搜索一个键，复杂度一直是常数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()
相同
• 两者都在每次查找100ns的量级

Answer 2

Python中的字典平均在0(1)中找到键。但是复杂性并不是影响执行时间的唯一因素。例如，通过索引访问列表项也是O(1)，但它比通过键访问字典要快得多。

我试着用

替换你的代码

node_ids = id_map.get(rel_column,node_ids)

认为它可以通过只进行一次字典访问来加速进程，但它根本没有提高性能(实际上它更慢)。

为了证明字典键访问不是O(logN)，我对从不同大小的字典中访问现有键和缺失键进行了基准测试。如果在内部使用二分查找，性能会随着大小而下降，丢失键将是最坏的情况，因此需要比现有键更多的时间(它们不需要):

id_map1 = {str(i):str(i+1) for i in range(2_000_000)} # LogN = 20
id_map2 = {str(i):str(i+1) for i in range(100_000)}   # LogN = 16
id_map3 = {str(i):str(i+1) for i in range(5_000)}     # LogN = 12
highHits = ["-1","0","1000","2000","2"]*10000     # 50,000
lowHits  = ["-1","0","-1000","-2000","-2"]*10000  # 50,000
from timeit import timeit
print("2M/high  ",timeit(lambda: [id_map1[k] if k in id_map1 else None for k in highHits],number=1))
print("100K/high",timeit(lambda: [id_map2[k] if k in id_map2 else None for k in highHits],number=1))
print("5K/high  ",timeit(lambda: [id_map3[k] if k in id_map3 else None for k in highHits],number=1))
print("2M/low   ",timeit(lambda: [id_map1[k] if k in id_map1 else None for k in lowHits],number=1))
print("100K/low ",timeit(lambda: [id_map2[k] if k in id_map2 else None for k in lowHits],number=1))
print("5K/low   ",timeit(lambda: [id_map3[k] if k in id_map3 else None for k in lowHits],number=1))

结果:

# existing keys
2M/high   0.003838191999999907
100K/high 0.004719815000000072
5K/high   0.0046313949999996495
# Missing keys
2M/low    0.003382090999999754
100K/low  0.003280908000000249
5K/low    0.0034408550000000204

因此，性能不会随着字典的大小而下降(如果有的话，它会有所提高)。缺失键的识别速度比现有键快，这就排除了二分查找。因此，Python字典对于键访问没有O(logN)复杂度。