优化Itertools导致Python

Question

我在python中调用itertools (见下文)。在这段代码中，snp_dic是一个以整数键和集合作为值的字典。这里的目标是找到最小的键列表，其值的合并是与set_union等价的集合的组合。(这相当于为流行的NP-硬图理论问题集的全局最优解，为感兴趣的人解决)！下面的算法可以工作，但这里的目标是优化。

我看到的最明显的优化与迭代工具有关。假设长度为r，在snp_dic中存在一个r集的组合，它的union = set_union。基本概率表明，如果这种组合存在，并且在组合上均匀地分布在某个地方，那么平均来说，它只需迭代一次就可以找到这个集合覆盖组合。然而，Itertools将返回所有可能的组合，通过每次迭代检查，花费的时间是检查set_unions的预期时间的两倍。

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

问题(最后)是，我如何逐个地流itertools.combinations()的结果，这样我就可以在进行过程中检查集合联合，这样它仍然在与itertools.combinations()的python实现几乎相等的时间运行。在一个答案中，我希望您能够包括对新方法进行计时的结果，以证明它在与python本机实现类似的时间运行。任何其他优化也是值得赞赏的。

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

迭代工具为它返回的内容提供生成器。要流它们，只需使用

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

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