python - 在 Python 中优化 Itertools 结果

Question

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

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

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

那么问题(最后)是，我怎样才能一个一个地流式传输 itertools.combinations() 的结果，这样我就可以在进行过程中检查集合并集，这样它仍然在与 python 实现几乎相同的时间运行itertools.combinations()。在回答中，如果您可以包括对新方法进行计时的结果以证明它在与 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 为其返回的内容提供生成器。要流式传输它们，只需使用

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

combinations 方法在您每次访问它时返回一个新元素:每次循环迭代一个。