Python で itertools を呼び出しています (以下を参照)。このコードでsnp_dicは、 は整数のキーとセットを値として持つ辞書です。ここでの目標は、値の和集合が集合の和集合の組み合わせであり、set_union. (これは、興味のある方のために、人気のある NP 硬グラフ理論問題セットカバーのグローバル最適解を解くことと同じです)! 以下のアルゴリズムは機能しますが、ここでの目標は最適化です。
私が目にする最も明白な最適化は itertools に関するものです。長さ r の場合、snp_dic には、union = set_union である r セットの組み合わせが存在するとします。基本確率は、この組み合わせが存在し、組み合わせ全体にわたってランダムに一様に分布している場合、平均して、このセットをカバーする組み合わせを見つけるために組み合わせを反復処理するだけでよいと予想されます。ただし、Itertools はすべての可能な組み合わせを返し、各反復でチェックすることにより set_unions をチェックする予想時間の 2 倍の時間がかかります。
論理的な解決策は、単純に itertools.combinations() をローカルに実装することです。python docs の itertools.combinations() の「同等の」python 実装に基づいていますが、 itertools.combinations は python ネイティブのものではなく C レベルの実装を呼び出すため、時間は約 2 倍遅くなります。
(最後に) 問題は、どのように itertools.combinations() の結果を 1 つずつストリーミングして、進むにつれてセット ユニオンをチェックして、 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()