当字典增长到数千个键时,我在使用字典时遇到了严重的减速。
我正在处理一个包含大约1,000,000行数据的文件,我正在构建一个使用字典的数据结构图
这是我的瓶颈功能
def create_edge(node_a, node_b, graph):
if node_a not in graph.keys():
graph[node_a] = {node_b: 1}
elif node_b in graph[node_a].keys():
graph[node_a][node_b] += 1
else:
graph[node_a][node_b] = 1
create_edge
将创建并从node_a
到node_b
边缘,或者在它们之间已存在的边缘的重量上加1。
由于我的节点由字符串唯一ID标识,我使用字典进行存储,假设搜索是否存在密钥,并且insert平均需要O(1)。
如果我评论create_edge
我可以每秒处理大约20,000条记录,create_edge
作为我的管道的一部分,它每秒约20条记录。
前100条记录需要大约500毫秒来处理。当字典大小增加到大约10,000时 - 处理100个记录大约需要15,000ms,每个记录进程平均调用create_edge
大约4次 - 因此当字典大小为10,000时,create_edge
的400次调用需要15秒。
首先,这些运行时有意义吗?对我来说似乎很重要,如果我错了,请纠正我。
其次,非常感谢优化字典使用以获得更好的运行时间的建议。
我期望字典大小至少为100,000,以完成整个1,000,000条记录的处理。
编辑:结论
你是对的钱,在这里做了两个菜鸟错误.. :)
keys()
调用戏剧性地增加了复杂性,从每个边缘插入的恒定时间到多边形时间(平方),用if node in graph.keys()
替换if node in graph
在~300ms内产生100个记录的恒定处理时间。
第二个错误是virtualenv配置,这使我相信我使用python3而我实际上使用python2。
python3确实将keys()代码优化为常量时间搜索,这对于运行时有用,但对于正确的代码样式则更少。
在删除keys()
调用后,我执行了运行时比较。
# graph = {}
python version: 3.6.3
start time 11:44:56
Number of records: 1029493
graph created, 1231630 nodes
end time 11:50:35
total ~05:39
# graph = defaultdict(lambda : defaultdict(int))
python version: 3.6.3
start time 11:54:52
Number of records: 1029493
graph created, 1231630 nodes
end time 12:00:34
total ~05:42
# graph = {}
python version: 2.7.10
start time 12:03:25
Number of records: 1029493
graph created, 1231630 nodes
end time 12:09:40
total ~06:15
当测试dict
中是否存在密钥时,只需使用key in d
,而不是使用key in d.keys()
。提取密钥以测试成员资格否定了首先使用dict
的好处。
请尝试以下方法:
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
请注意,keys()
根本没有被调用。这应该比你现在做的快得多。
请注意,在Python 2中,keys()
检查将比Python 3慢得多,因为在Python 2中,keys()
创建了整个键集的列表。它在Python 3中的工作方式不同,但即使在Python 3中直接检查成员身份,而不使用keys()
,也会更快。
你不能只使用defaultdict(int)的defaultdict,如下所示:Python: defaultdict of defaultdict?
from collections import defaultdict
graph = defaultdict(lambda : defaultdict(int))
graph['a']['b'] += 1
graph['a']['b'] += 1
graph['a']['c'] += 1
graph
返回:
defaultdict(<function __main__.<lambda>>,
{'a': defaultdict(int, {'b': 2, 'c': 1})})
# equal to: {'a': {'b': 2, 'c': 1}}
我尝试了几种方法,这似乎是有用的。此方法使用计数器首先计算所有出现次数,然后构建字典。感谢@Stefan Pochmann提供基准脚本。我使用的是来自ideone.com/ckF0X5
我使用的是Python 3.6,结果在我的计算机上进行了测试。
from timeit import timeit
from collections import defaultdict, Counter
from random import shuffle
from itertools import product
def f(): # OP's method modified with Tom Karzes' answer above.
d = {}
for i, j in edges:
if i not in d:
d[i] = {j: 1}
elif j in d[i]:
d[i][j] += 1
else:
d[i][j] = 1
def count_first():
d = dict()
for (v, w), c in Counter(edges).items():
if v not in d:
d[v] = {w: c}
else:
d[v][w] = c
# Alternatively, (Thanks to Jean-François Fabre to point it out.)
# d = defaultdict(lambda : defaultdict(int))
# for (v, w), c in Counter(edges).items():
# d[v][w] = c
edges = list(product(range(300), repeat=2)) * 10
shuffle(edges)
# %timeit f()
270 ms ± 23.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
# %timeit count_first()
180 ms ± 15.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
声明:然而,我从ideone.com获得的count_first()
的结果比OP的答案慢,f()
在这里。
Stefan Pochmann做了一个基准实验来比较Python 2和3中的不同方法。他在Python 2中的结果可以找到here。对于Python 3,请检查this。给他的信用并感谢他的代码审查。