2

私は現在、ある特定のステップで次の方法でサブセットを計算する必要があるアルゴリズムを実装しています。

整数のセット (おそらく数百万) があるとします。各セットには約 1000 個の要素が含まれる可能性があります。

Set1: [1, 3, 7]
Set2: [1, 5, 8, 10]
Set3: [1, 3, 11, 14, 15]
...,
Set1000000: [1, 7, 10, 19]

特定の入力セットを想像してください:

InputSet: [1, 7]

ここで、この InputSet がどのサブセットであるかをすばやく計算したいと思います。この特定のケースでは、Set1 と Set1000000 を返す必要があります。

さて、ブルートフォースには時間がかかりすぎます。Map/Reduce を介して並列化することもできますが、よりインテリジェントなソリューションを探しています。また、ある程度までは、メモリ効率が良いはずです。BloomFilters を使用して、入力セットが決してサブセットにならないセットをすばやく除外することで、計算を既に最適化しています。

私が見逃している賢いテクニックはありますか？

ありがとう！

4

4 に答える 4

2

ボトルネックはセットの数にあるようです。そのため、すべてを反復してセットを見つけるのではなく、要素からそれらを含むすべてのセットにマッピングすることでパフォーマンスを向上させ、検索したすべての要素を含むセットを返すことができます。為に。

これは、情報検索の分野で転置索引を検索するときに AND クエリで行うのと非常によく似ています。

あなたの例では、次のようになります。

1 -> [set1, set2, set3, ..., set1000000]
3 -> [set1, set3]
5 -> [set2]
7 -> [set1, set7]
8 -> [set2]
...

編集:
IR の逆インデックスでは、スペースを節約するためにd ギャップを使用することがあります。つまり、実際の数ではなく、ドキュメント間のオフセットを保存します。たとえば、[2,5,10]になり[2,3,5]ます。そうすることと、数値を表すためにデルタ エンコーディングを使用することは、スペースに関しては非常に役立つ傾向があります。
(もちろん、マイナス面もあります。特定のセット/ドキュメントが含まれているかどうかを確認するためにリスト全体を読み取る必要があり、バイナリ検索を使用することはできませんが、特にフィッティングの違いである場合は、価値がある場合がありますRAMへのインデックスかどうか）。

于 2013-01-02T14:21:09.893 に答える
0

  1. 入力セットの最大数 (7) から検索を開始し、他のサブセットを排除します (Set1 と Set1000000 が返されます)。

  2. 残りのセットで他の入力要素 (1) を検索します。

于 2013-01-02T15:32:09.303 に答える
0

amit のソリューションを拡張すると、実際の数値を保存する代わりに、間隔とそれに関連するセットを保存することができます。

たとえば、間隔サイズ 5 を使用すると、次のようになります。

 (1-5): [1,2,3,1000000]
 (6-10): [2,1000000]
 (11-15): [3]
 (16-20): [1000000]

(1,7) の場合、間隔 (1-5) と (5-10) を考慮する必要があります (間隔のサイズを知ることで簡単に決定できます)。これらの範囲を交差させると、[2,1000000] が得られます。セットのバイナリ検索は、(1,7) が実際に両方のセットに存在することを示しています。

ただし、各セットの最小値と最大値を確認して、間隔のサイズをより適切に把握することをお勧めします。たとえば、最小値と最大値が 1 から 100 万になる場合、5 はおそらく不適切な選択です。

バイナリ検索を使用して値を確認できるように、おそらくそれを維持する必要があるため、サブセット範囲は (最小 + 最大)/N のようにする必要があります。ここで、2N はバイナリ検索する必要がある値の最大数です。各セット。たとえば、「セット 3 には 5 から 10 までの値が含まれていますか?」これは、5 (3) と 10 (11) に最も近い値を見つけることによって行われますが、この場合はそうではありません。各セットを調べて、セット内にある可能性のある間隔値をバイナリ検索する必要があります。これは、セットが 10 までしかないときに 100 を検索しないようにすることを意味します。

範囲 (最小値と最大値) を保存することもできます。ただし、問題は、番号がクラスター化されると思われるため、あまり役に立たないことです. 前述のように、間隔の設定方法を決定するのにおそらく役立つでしょう。

使用する範囲を選択するのはまだ面倒です。大きすぎると、データ構造を構築するのに長い時間がかかります (1000 * 100 万 * log(N))。小さすぎると、スペースの問題が発生し始めます。範囲の理想的なサイズは、おそらく、各範囲に関連するセットの数がほぼ等しくなるようにすると同時に、範囲の合計数が多すぎないようにすることです。

編集: 利点の 1 つは、実際にはすべての間隔を保存する必要がなく、必要なものだけを保存できることです。ただし、未使用の間隔が多すぎる場合は、間隔を増やして現在の間隔を分割して、検索が高速になるようにすることをお勧めします。これは、処理時間が大きな問題でない場合に特に当てはまります。

于 2013-01-02T15:34:48.903 に答える
0

各数値を含むセットのリストを保存するのはどうですか?

1 -- 1, 2, 3, 1000000
3 -- 1, 3
5 -- 2
etc.
于 2013-01-02T14:21:33.577 に答える