セットの集合を考えるとA1,A2、...、An。私は、これらのセットのどれが異なるセットのサブセットであるかを見つける最も効率的なアルゴリズムを決定したいと考えています。Bどのセットが大きなセットのサブセットであるかを決定するための効率的な検索アルゴリズム
例えば、アルゴリズムの入力であるとする。
A1 = [1 2]
A2 = [2 3 4]
A3 = [1 3]
B = [1 2 3]
アルゴリズムが返すべき：
output = [1 3]
A1とA3ためBのサブセットであるが、A2ではありません。
単純なO（N）答え：両方のリストをソートして開始します。より短いリストを選び、各エントリについて、それが相手側に存在するかどうかをチェックします。他のリストをすばやく検索する必要はありません。ポインタを保持して、ターゲット番号を見つけたり渡したりするまで増分するだけです。
一方、コンピュータの各ステップを簡単にすることで、 "O（N）"操作を高速化できます。たとえば、いくつの数字が共通であるかだけを計算する必要がある場合は、bitmask
のように多くのリストを1つの特別なリストと比較する場合、ほとんどの数字は共通ではありませんが、 Bloom Filterを作成することができます。これは、 "番号XはセットYにはありません"ということを非常に迅速に伝えることができます。番号が存在するかどうかはわかりません。手動でその番号を再確認する必要があります。 MOSTの数字がミスであると思われる場合は、スピードが上がります。
答えをありがとう！私は2つの質問があります：1）ビットマスクアプローチの場合、A1 = [1 2]とB = [1 2 3] 'がわかっていて、操作によって2つの要素が共通していることがわかります。 A1には2つの要素しかないので、A1がBになければならないことがわかります。同様に、 'B = [1 3]'とすると、共通の要素は1つだけで、 'A1'は' B'の部分集合ではありません。つまり、要約すると、数字を共通に比較するだけでサブセットを確認できますか？ I. （A1とBとの間の）共通の要素の数は、A1がBのサブセットでない場合にのみ、A1の要素の数よりも少ない。 – jonem
2）引用符で囲まれたテキストを「集合Xが集合Yではない」と一般化するには、XがYの部分集合であるかどうかを判定するために、 2つのリストを直接比較するだけでは、これがどのように効率化に役立つかはわかりません。 – jonem
あなただけがあなたのデータをよく知っていて、どのショートカットが貴重なものかを知ることができます。たとえば、「Aの中の最大の要素はBの最小要素よりも小さいですか」と聞くことができます。データが重複していると、無駄になることがあります。これはほとんど仕事をスキップするためです。しかし、データがほとんど重複しないことに気がついた場合、勝利につながる可能性があります。 – BraveNewCurrency
巧妙な最適化が必要な場合は、この操作をコンテキストに入れなければなりません。それだけでは、あなたができることはあまりありません。 'B'からハッシュテーブルをソートしたりビルドしたりして、対応する標準の包含テストを実行することができます。 – user2357112
@ user2357112こんにちは、ありがとうございます。もう少しコンテキストを与えるために、セットBには、セット1から約1000または10000までの整数の選択肢（重複なし）が含まれています.1から3の整数だけを含む1000のオーダーの多くのセットAがあります同じセット（1から1000または10000）から（重複しないで）再設定します。 – jonem