サブセットであるセットを削除する

Question

整数セットのリストが2つあるとします。それらをAとBと呼んでください。Aのすべての集合はBの集合の1つに含まれることができます.Aのすべての要素を見つけるアルゴリズムはどれもありません。

Answer 1

検索スペースを調整したり削除したりするには、検索の一部としていくつかのチェックとフィルタを試すことができます。

1: A: {0,1}, B: {1,2} 
2: A: {0} , B: {0,1,2} 
3: A: {2} , B: {0} 
4: A: {1,2}, B: {0,1} 
5: A: {} , B: {2} 
6: A: {} , B: {2} 
7: A: {2} , B: {} 

：セットの相互相関インデックスを指すキーとしてセットでユニークな要素のO（n）を列挙して、コメントで

A = [{1,2},{1,4},{3,4,7}] 
B = [{2,3,4},{1,2,4},{1,2,5,6}]  

スタートをあなたの例を取るために、彼らはに属しています

Aの3番目のセットなど、Bにはない要素を含むAのセットをすぐに取り除くことができます。

ここで、除外されていないA内の各セットを走査し、Bに少なくとも1セットの対応する完全な交差があるかどうかを調べます。ケース内のセットインデックスの数は、最初にBを全体的に走査するのではなく、Bの検査をセクションのそれぞれに分割して、それぞれkのセット、例えば1024を設定します。さらに、1024個のセットインデックスを表すために、それぞれ64ビットの16ビットセットに分割しますビット単位でANDしてもよい（&）。

set A[0] => elements 1,2 => set-index-intersection in B: b110 & b111 => match 
set A[1] => elements 1,4 => set-index-intersection in B: b110 & b11 => match 

全体的に、セクションごとに作業、我々は約10 * 16の操作を見ている：ゼロのAND演算結果があれば、この横断中の任意の時点で

、我々は早期終了の恩恵を受けるAのセットがk Bセットの現在のセクションのセットの1つに含まれているかどうかを確認してください。言い換えれば、Aの1セット（Bの100万セットあたり）の完全なチェックのために、操作の数を10,000,000から160,000に減らしました。それは62の要素です。