优化 Itertools 结果 Python

Question

我在 python 中调用 itertools（见下文）。在此代码中，snp_dic 是一个具有整数键并设置为值的字典。这里的目标是找到最小的键列表，其值的并集是等价于 set_union 的集合并集的组合。（这相当于为那些感兴趣的人解决流行的 NP-hard 图论问题集合的全局最优解）！下面的算法有效，但这里的目标是优化。

我看到的最明显的优化与 itertools 有关。假设对于长度 r，在 snp_dic 中存在 r 个集合的组合，其并集 = set_union。基本概率表明，如果此组合存在并且随机均匀分布在组合的某处，则预计平均只需要迭代组合即可找到此集合覆盖组合。然而，Itertools 将 return 所有可能的组合，通过在每次迭代中检查 set_union 来花费预期检查时间的两倍。

一个合乎逻辑的解决方案似乎只是在本地实施 itertools.combinations() 。基于 "equivalent" python itertools.combinations() 在 python 文档中的实现，但是时间大约慢两倍，因为 itertools.combinations 调用 C 级实现而不是比 python-原生的。

那么问题（最后）是，我怎样才能一个一个地流式传输 itertools.combinations() 的结果，这样我就可以在进行时检查集合并集，这样它仍然会在几乎相同的时间运行itertools.combinations() 的 python 实现。在回答中，如果您可以包括对新方法进行计时的结果以证明它在与 python-native 实现相似的时间运行，我将不胜感激。任何其他优化也表示赞赏。

def min_informative_helper(snp_dic, min, set_union):
    union = lambda set_iterable : reduce(lambda a,b: a|b, set_iterable) #takes the union of sets
    for i in range(min, len(snp_dic)):
       combinations = itertools.combinations(snp_dic, i)
       combinations = [{i:snp_dic[i] for i in combination} for combination in combinations]
       for combination in combinations:
           comb_union = union(combination.values())
           if(comb_union == set_union):
           return combination.keys()

Answer 1

itertools 为其 returns 提供生成器。要流式传输它们，只需使用

for combo in itertools.combinations(snp_dic, i):
    ... remainder of your logic

组合方法returns每次访问一个新元素：每次循环迭代一个。

优化 Itertools 结果 Python

Optimizing Itertools Results in Python

python

algorithm

optimization

set-cover