Python无序字典查找为何比有序查找慢10倍？如何优化？

问题描述 #

遍历整数列表进行Python字典查找时，发现无序列表的查找速度仅为有序列表的1/10。原始数据条目既无序也不连续，并非某个范围内的所有整数都存在于列表中。想明确两个问题：

• 如何加速无序场景下的字典查找？
• 造成这种时间差异的核心原因是什么？

实验过程 #

import random

dummy_dict = {i:i for i in range(10000000)}

# 有序列表
a = [i for i in range(10000000)] 

# 无序列表
b = [i for i in range(10000000)] 
random.shuffle(b)

# 排序后的无序列表
c = b[:]
c.sort() 

# 随机值列表
e = [random.randint(0,9999999) for i in range(10000000)]

实验结果 #

字典查找耗时 #

[dummy_dict[i] for i in a]  # 耗时：0.7s
[dummy_dict[i] for i in b]  # 耗时：6.7s
[dummy_dict[i] for i in c]  # 耗时：0.7s
[dummy_dict[i] for i in e]  # 耗时：6.3s

仅遍历列表耗时 #

["" for i in a]  # 耗时：0.3s
["" for i in b]  # 耗时：0.9s
["" for i in c]  # 耗时：0.3s
["" for i in e]  # 耗时：0.3s

原因分析 #

1. 列表遍历的耗时差异 #

Python列表存储的是对象引用，遍历本质是访问这些引用指向的对象：

• 有序列表a和排序后的c：元素对应的整数对象是连续创建的，内存地址接近连续，CPU的缓存预取机制会提前加载后续内存块，缓存命中率极高，因此遍历速度快。
• 打乱后的列表b：虽然整数对象的内存地址依然连续，但遍历是按乱序访问这些地址，属于随机内存访问，缓存频繁失效，导致耗时增加。
• 随机值列表e：生成随机整数时，Python内存分配器会连续分配内存给新创建的int对象，因此即使数值随机，对象内存地址仍接近连续，遍历缓存命中率高，耗时与有序列表一致。

2. 字典查找的耗时差异 #

Python字典基于哈希表实现，理论上查找时间复杂度为O(1)，但实际性能受缓存命中率影响：

• 有序键场景（a、c）：整数键的哈希值等于自身，字典的哈希槽位与键的顺序对应，查找时连续访问哈希表的槽位，缓存预取生效，命中率高，因此速度快。
• 无序键场景（b、e）：键的哈希值分布随机，查找时需要跳跃访问哈希表的不同槽位，缓存频繁失效，导致查找速度大幅下降。

优化方法 #

针对无序、不连续整数键的字典查找场景，可通过以下方式加速：

• 用列表替代字典：如果键的范围已知，直接用列表存储值，缺失的键用特殊值（如None）填充。列表的连续内存布局天生缓存友好，访问速度远高于字典，示例：

  # 假设键的最大范围是10^7
  dummy_list = [i if i in dummy_dict else None for i in range(10000000)]
  # 查找时直接索引
  [dummy_list[i] for i in b]
  

• 使用NumPy数组：NumPy数组采用连续内存存储，比Python原生列表更节省内存，缓存效率更高，适合大规模整数键场景。
• 按哈希值排序后查找：将需要查找的键按哈希值排序，使字典查找时连续访问哈希槽位，提升缓存命中率。
• 使用array模块：array.array存储原始整数类型（而非对象引用），内存占用更小，缓存效率优于普通列表。

内容的提问来源于stack exchange，提问作者tommi123