0

我在 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() 的结果，以便我可以检查集合联合，因此它仍然在与 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()
4

1 回答 1

3

itertools为它返回的东西提供了生成器。要流式传输它们，只需使用

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

每次访问时，组合方法都会返回一个新元素：每次循环迭代一个。

于 2016-11-22T22:54:52.503 回答