Python 比循环更有计算效率的东西

Question

我正在尝试使用以下代码从 python 中的字典创建图边列表：

graph= []
for key, value in dic_test.items():
    for x in range (0,len(value)):
        if (x+1) < len(value):
            for y in range (1,len(value)):
                if y != x and y>x:
                    graph.append([value[x],value[y]])

这得到了我想要的，例如，如果我得到这个测试字典：

dic_test= {1: ['A', 'E','F','G'], 2: ['B', 'D','X'], 3: ['C',"Y"],4:[],5:['f','h']}

我得到以下输出：

[['A', 'E'],
 ['A', 'F'],
 ['A', 'G'],
 ['E', 'F'],
 ['E', 'G'],
 ['F', 'G'],
 ['B', 'D'],
 ['B', 'X'],
 ['D', 'X'],
 ['C', 'Y'],
 ['f', 'h']]

问题是当我运行一个大字典时它运行直到内核崩溃，我有什么想法可以使这段代码更有效率吗？

Answer 1

您可以使用itertools.combinations()
（参见 how to get all combinations of a list's elements）：

import itertools
dic_test= {1: ['A', 'E','F','G'], 2: ['B', 'D','X'], 3: ['C',"Y"],4:[],5:['f','h']}

_combinations = []
for _value in dic_test.values():
    _combinations.extend(list(itertools.combinations(_value, 2)))

print(_combinations)

[('A', 'E'),
 ('A', 'F'),
 ('A', 'G'),
 ('E', 'F'),
 ('E', 'G'),
 ('F', 'G'),
 ('B', 'D'),
 ('B', 'X'),
 ('D', 'X'),
 ('C', 'Y'),
 ('f', 'h')]

因为你导入了itertools，使用itertools.chain()可以做下面的一行：

list(itertools.chain(*[list(itertools.combinations(_value, 2)) for _value in dic_test.values()]))

注意

1.性能问题：
- list.extend()：每个循环 7.23 µs
- itertools.chain()：每个循环 8.15 µs

2。巨大，非常巨大，非常非常非常巨大的词典：
由于您对每个键执行的操作彼此独立，因此您可以并行化您的任务（multiprocessing documentation 如果需要）

Answer 2

Itertools 在这里可能对您有所帮助，因为每条边只是每个子列表中顶点的 2 项组合：

import itertools

output = []
for links in dic_test.values():
    output += map(list, itertools.combinations(links, 2))

Answer 3

for val in dic_test.values():
     a=itertools.combinations(val,2)
     for c in a:
         print(c)

给出输出

('A', 'E')
('A', 'F')
('A', 'G')
('E', 'F')
('E', 'G')
('F', 'G')
('B', 'D')
('B', 'X')
('D', 'X')
('C', 'Y')
('f', 'h')

Answer 4

除了提供 itertools 的建议之外，值得注意的是您还有多组不相交的点击。这意味着您不需要一次完成所有这些计算，当然也不需要同时将所有结果存储在内存中。这也意味着您可以 parallelize.

Python 比循环更有计算效率的东西

Python something more computational efficient than a loop

python

performance

loops

dictionary

edges