PythonでItertoolsの結果を最適化する

Question

私はpythonでitertoolsを呼び出しています（下記参照）。このコードでは、snp_dicは整数キーを持つ辞書であり、値として設定されています。ここでの目標は、値の和集合がset_unionに相当する集合の和集合であるキーの最小リストを見つけることです。 （これは興味のある人のための一般的なNPハードグラフ理論問題のセットカバーのためのグローバルな最適化を解決するのと同じです！）以下のアルゴリズムは動作しますが、ここでの目標は最適化です。

私が見る最も明白な最適化はitertoolsと関係があります。ある長さrに対して、union = set_unionを持つsnp_dicにr個のセットの組み合わせが存在するとしましょう。基本的な確率は、この組み合わせが存在し、その組み合わせの上にランダムに一様に分布している場合、この集合をカバーする組み合わせを見つけるために、平均して繰り返しを繰り返す必要があることが予測される。しかし、Itertoolsは可能なすべての組み合わせを返します。各反復時にチェックすることによって、set_unionsをチェックする予定の時間の2倍の時間がかかります。

論理的な解決策は、itertools.combinations（）をローカルに実装するだけのようです。しかし、itertools.combinations（）の "同等の" Python実装ではpythonのドキュメントでは、pythonのネイティブではなくCのレベルの実装が呼び出されるため、時間は約2倍遅くなります。

それでは、itertools.combinations（）の結果を1つずつストリーミングするにはどうしたらいいですか？私は一緒になって組合をチェックすることができるので、Pythonの実装とほぼ同じ時間に実行されますitertools.combinations（）のあなたが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

itertoolsは、それが返すもののために発電機を提供します。ループの繰り返しごとに1：それらをストリーミングするには、単に

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

を使用組み合わせモジュールは、1つの新しい要素にあなたがそれにアクセスするたびに返されます。