3

整数のセットであるNアイテムのセットがあります。それが順序付けられていると仮定して、 と呼びましょうI[1..N]。セットが与えられた場合、との空でない共通部分を持つcandidateサブセットを見つける必要があります。Icandidate

たとえば、次の場合:

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 は項目 1 に含まれ、2 は項目 1 と 2 に含まれ、2 は項目 2 に含まれ、3 は項目 2 に含まれ、4 と 5 は項目 3 に含まれます。

そうすれば、定義できますvalid_items(I, candidate) = union(items_containing[n] for n in candidate)。

このユニオンの結果をキャッシュするための (妥当なサイズの) より効率的なデータ構造はありますか? スペースの明らかな例は2^N受け入れられませんが、受け入れられるNでしょN*log(N)う。

4

2 に答える 2

2

実際のパフォーマンスを向上させる可能性のあるマイクロ最適化手法がありますが、現在のソリューションは最適な大規模なものだと思います。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;
}

しかし、それらは Big-O のパフォーマンスを実際には変えません。

于 2010-04-06T23:11:03.583 に答える
1

役立つ可能性のある表現の 1 つは、集合 I をサイズ n のベクトル V として格納することです。そのエントリ V(i) は、i が V にない場合は 0 で、それ以外の場合は正です。次に、2 つのベクトルの交点を取るには項を乗算し、結合を取るには項を追加します。

于 2010-04-06T23:07:39.693 に答える