字典搜索和插入优化

问题描述 投票:4回答:3

当字典增长到数千个键时,我在使用字典时遇到了严重的减速。

我正在处理一个包含大约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_anode_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
python
3个回答
2
投票

当测试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(),也会更快。


3
投票

你不能只使用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}}

2
投票

我尝试了几种方法,这似乎是有用的。此方法使用计数器首先计算所有出现次数,然后构建字典。感谢@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。给他的信用并感谢他的代码审查。

© www.soinside.com 2019 - 2024. All rights reserved.