素早くセットのリストの非空の交差点を見つけるためのデータ構造とは何ですか？

Question

私は整数の集合であるNアイテムのセットを持って、聞かせてのは、それが注文していますと仮定してI[1..N]それを呼び出します。 candidateセットを考えると、私はIと非空の交差点を持つcandidateのサブセットを見つける必要があります。

ですから、例えば、もします：

I = [{1,2}, {2,3}, {4,5}]

私はそのようなことを、valid_items(items, candidate)を定義するために探しています

valid_items(I, {1}) == {1}
valid_items(I, {2}) == {1, 2}
valid_items(I, {3,4}) == {2, 3}

私はセットIと変数candidateセット指定されたもののために最適化しようとしています。現在、私はitems_containing[n] = {the sets which contain n}をキャッシュすることで、これをやっています。上記の例では、それは次のようになります。

items_containing = [{}, {1}, {1,2}, {2}, {3}, {3}]

つまり0 1 3は、項目2に含まれ、2項目2に含まれ、2 itmes 1及び2に含まれている、項目1に含まれている、ない項目に含まれ、図4および図5は、中に含まれる、あります項目3.

そのように、私はvalid_items(I, candidate) = union(items_containing[n] for n in candidate)を定義することができます。

この組合の結果をキャッシュする（合理的なサイズの）任意のより効率的なデータ構造はありますか？宇宙2^Nの明白な例は、許容できるものではなく、NまたはN*log(N)は以下のようになります。

Answer 1

私は、その実際のパフォーマンスを向上させることができ、マイクロ最適化手法がありますが、あなたの現在のソリューションは、最適なビッグO賢明だと思います。そのような有効なアイテムセットとセットitem_containingに選択されたセットをマージする際にビット演算を使用するなど。

すなわち。

：あなたはこのようitems_containingを保存します

items_containing = [0x0000, 0x0001, 0x0011, 0x0010, 0x0100, 0x0100]

と、あなたのvalid_itemsは次のようにマージするビット単位のORを使用することができます：

int valid_items(Set I, Set candidate) {
    // if you need more than 32-items, use int[] for valid 
    // and int[][] for items_containing
    int valid = 0x0000;
    for (int item : candidate) {
        // bit-wise OR
        valid |= items_containing[item];
    }
    return valid;
}

しかし、彼らは本当にビッグOのパフォーマンスを変更しないでください。

Answer 2

iはVで正さもなければない場合

かもしれないヘルプがIエントリVサイズnのベクトルVとしてセットを記憶していることを1つの表現は、（i）は0です。そして、乗算あなた項2つのベクトルの交点を取るために、あなたが用語を追加組合を取るます。