字典搜索与插入优化：大规模数据场景下的性能瓶颈排查

非常典型的字典性能陷阱问题，我结合你的测试数据和发现来逐一解答：

问题1：运行时数据是否合理？ #

完全合理！你的测试结果精准命中了Python字典使用的经典性能坑：

• 在Python 2中，dict.keys()会返回一个完整的键列表副本，每次执行node_a not in graph.keys()本质是做O(n)的线性搜索。当字典键数涨到1万级别时，这个操作的耗时会呈平方级飙升（因为每条记录要多次调用create_edge）。你看到的前100条快、字典规模1万时100条耗时15秒，完全符合这个性能退化规律。
• 而Python 3中dict.keys()返回的是视图对象（不是列表），in操作是O(1)，但你误用到了Python 2环境，直接放大了这个问题。

问题2：大规模字典（10万+键）优化建议 #

针对你的类图构建场景，给出几个关键优化方向：

1. 砍掉冗余的keys()调用（最核心的性能修复） #

直接用if node in dict代替if node in dict.keys()：

• 不管是Python 2还是3，node in dict都是直接对字典的哈希表做O(1)的存在性检查；
• 把你的create_edge函数修改为：

def create_edge(node_a, node_b, graph):
    if node_a not in graph:
        graph[node_a] = {node_b: 1}
    elif node_b in graph[node_a]:
        graph[node_a][node_b] += 1
    else:
        graph[node_a][node_b] = 1

这一步直接把你的性能从每秒20条拉回了正常水平，你实测的100条记录稳定在300ms就是最好的证明。

2. 用collections.defaultdict简化代码（可读性优先，性能持平） #

你的场景是嵌套字典统计边权重，用defaultdict可以省去手动判断键是否存在的逻辑，代码更简洁且不易出错：

from collections import defaultdict

def create_edge(node_a, node_b, graph):
    graph[node_a][node_b] += 1

# 初始化嵌套的defaultdict，自动为不存在的键创建默认值
graph = defaultdict(lambda: defaultdict(int))

从你的实测数据来看，这种写法和原生字典的性能几乎一致，但代码量减少了一半，维护成本更低。

3. 坚决使用Python 3环境 #

Python 3对字典的底层实现做了大量优化（比如紧凑字典结构、视图对象），性能比Python 2更稳定。你的测试数据也显示：Python 3.6处理100万条记录耗时约5分39秒，而Python 2.7需要6分15秒，差异明显。

优化后性能实测对比 #

原生字典（Python 3.6.3） #

graph = {}
开始时间：11:44:56
记录数：1029493
生成节点数：1231630
结束时间：11:50:35
总耗时：~05:39

defaultdict（Python 3.6.3） #

graph = defaultdict(lambda : defaultdict(int))
开始时间：11:54:52
记录数：1029493
生成节点数：1231630
结束时间：12:00:34
总耗时：~05:42

原生字典（Python 2.7.10） #

graph = {}
开始时间：12:03:25
记录数：1029493
生成节点数：1231630
结束时间：12:09:40
总耗时：~06:15

总结 #

你的性能问题完全来自两个新手常见错误：

1. 误用dict.keys()导致线性搜索，把O(1)操作降级为O(n)；
2. 错误使用Python 2环境，放大了这个性能缺陷。
   优化后完全能支撑10万+键的大规模字典场景。

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