18

多数のユーザー ID (整数) があり、数百万になる可能性があります。これらのユーザーはすべて、さまざまなグループ (整数のセット) に属しており、約 1,000 万のグループがあります。

この例を単純化して本質を理解するために、すべてのグループに 20 のユーザー ID が含まれていると仮定します。

交差が 15 以上の整数セットのペアをすべて見つけたいと考えています。

セットのすべてのペアを比較する必要がありますか? (ユーザー ID をセット メンバーシップにマップするデータ構造を維持する場合、これは必要ありません。) これを行う最も簡単な方法は何ですか? つまり、整数セットを表すために、基礎となるデータ構造はどうあるべきでしょうか? ソートされたセット、ソートされていない---ハッシュは何らかの形で役立ちますか? そして、集合交差を計算するためにどのアルゴリズムを使用する必要がありますか? C/C++ (特に STL) に関連する回答を好みますが、より一般的なアルゴリズムの洞察も歓迎します。

更新 また、これを共有メモリ環境で並行して実行することに注意してください。そのため、並行ソリューションにきれいに拡張するアイデアが優先されます。

また、大部分のセット ペアの交差サイズは 0 であることに注意してください。つまり、ユーザー ID をセットにマップしたデータ構造を使用して、セットのすべてのペアの交差を計算することを回避することが有利な場合があります。

4

4 に答える 4

6

私はあなたが提案したことを正確に行います: ユーザーをグループにマップします。つまり、すべてのユーザーのグループ ID のリストを保持します。次に、次のアルゴリズムを使用します。

foreach group:
  map = new Map<Group, int>  // maps groups to count
  foreach user in group:
    foreach userGroup in user.groups:
      map[userGroup]++
      if( map[userGroup] == 15 && userGroup.id > group.id )
        largeIntersection( group, userGroup )

Gそれぞれ平均してユーザーを含むグループがUあり、これらのユーザーが平均してグループに属しているとすればg、これは で実行されO( G*U*g )ます。これは、あなたの問題を考えると、で実行されるグループの単純なペアごとの比較よりもおそらくはるかに高速ですO(G*G*U)。

于 2010-04-23T09:27:44.803 に答える
4

交差の大部分が 0 の場合、空でない交差の数が比較的少ないことを意味します。これを試してください：

  • 開始する前に、サイズが 15 未満のすべてのセットを破棄します
  • ユーザーIDからルックアップを計算します->それが属するセットのリスト
  • 作成するmap<pair<userset, userset>, int>
  • ユーザーごとに、(必要に応じて作成した後に)n*(n-1)/2そのマップのエントリを増やします。ここで、n はユーザーが属するセットの数です。
  • それが完了したら、マップをスキャンして、値が 15 より大きいエントリを探します。

すべての交点を計算する単純な方法よりも多くのメモリを使用します。実際、それは実行可能なものに対して実行されます: 各セットが平均して 10 個の他のセットと交差する場合、おそらく非常に小さな交差点で、マップには 50M のエントリが必要であり、これは大量の RAM になり始めます。また、ひどくキャッシュフレンドリーではありません。

O(n^2) 項は、セットの数ではなく、空でない交差の数と各ユーザーが属するグループの数に関連するため、すべてのセット交差を実行するよりも高速である可能性があります。

巨大なマップで競合が発生するため、並列化は簡単ではありません。ただし、それを各スレッドのマップにシャードし、定期的に 1 つのスレッドに新しい空のマップを与えて、これまでの結果を合計結果に追加することができます。異なるスレッドは、ほとんどの場合、完全に独立して実行され、それぞれに処理するユーザーのリストが与えられます。

于 2010-04-23T09:17:43.970 に答える
2

セットのすべてのペアを比較する必要がありますか? (ユーザー ID をメンバーシップにマップするデータ構造を保持する場合、これは必要ありません。)

交差度を数えるには、ユーザーが持っている他のグループにアクセスする必要がありますが、これはまだ立方体です。カウントするハッシュ テーブルまたはその他のスパース配列を使用できますが、それでも、各ユーザーが属するグループのペアごとに各ユーザーの増分が必要になるだけです。 group と各ユーザーが属するグループの数 T を比較すると、グループの各ペアを比較するために G G S/2 が得られ、ユーザーからグループへのインデックスがある場合はN T T が得られます。T = G S/N なので N T T=G G SS/N; S=20 と数百万の N の場合、利点があるはずです。残念ながら、交差カウント用に少なくとも G*G 個のストレージ (4 ビットの非スパース カウンターの場合は 25 TB 程度) も必要であり、構造を並行してインクリメントできるようにする必要があります。

20 人からなる 1,000 万のグループに属する 100 万人のユーザーの場合、ユーザーが特定のグループに所属する確率はほぼ 2e-6 であり、2 つのグループがユーザーを共有する確率は 40e-6 であるため、25 TB は 1 GB になります。データであるため、通常のサイズのコンピューターのスパース配列では不可能ではありません。

ただし、共通の 15 要素に対して 20 要素のセットを比較すると、より明白な最適化が得られます。

  • グループがソートされている場合、作業用ストレージは必要ありません。入力グループ間の差異の程度を直接出力するだけです。
  • ほとんどのメモリ アクセスは連続したメモリ領域で線形になり、結果はデー​​タ セット全体の合計に依存するのではなく、比較される 2 つのセットのみに依存します。メイン メモリにランダムにアクセスすると、線形にアクセスするよりも大幅に遅くなります。バス ロックを使用してメイン メモリをランダムに変更すると、バスをロックせずにキャッシュにアクセスするよりも桁違いに遅くなります (ただし、コアあたり数 GB のメモリがある場合は、同期を行わなくてもユーザー -> グループ アプローチを使用できます)。
  • セット間で異なる 5 つの要素のみをカウントする必要があります。データがランダムな場合、ほとんどのセットは互いに素であるため、アクセスされる要素の平均数は少なくなります。
  • 差を距離として扱うことにより、特定のグループをすばやく割り引くことができます (A が B と 11 異なっており、C が B と 5 異なっている場合、C は A と 6 から 16 の間の差であるため、A と C を比較せずに割り引くことができます)。直接）。ほとんどのセットは完全にバラバラなので、これはあまり役に立ちません。

user->group マップを使用してグループ間の比較を行うハイブリッド アプローチのオプションもあります。これには、共有データ構造のインクリメントを必要としないという利点があります。

  • ユーザーが属するグループのペアごとに、そのペアをリストに追加して調査します。
  • 少なくとも 1 人のユーザーが共通するグループのペアのリストを並べ替えます。
  • リスト内の各ペアの出現回数は、共通のユーザーの数です。

マージソートを使用すると、これは純粋なストリーミングユニットに並列化するのに非常に便利です。約 20*200*1000 万/2 = 200 億のグループ ID ペア (20 ユーザーの各グループ×各ユーザーが属するグループ数/2) をソートします。

于 2010-04-23T10:08:34.040 に答える
1

1 つの方法は、距離関数が一致しないエントリの数であり、半径が であるメトリック空間 半径検索r = max(number of elements in sets) - number of equal問題として問題を確認することです。Set に十分な値があることを確認するには、見つかった要素をフィルタリングする必要があります。したがって、誰かが直接使用できるメトリック関数を考え出さない限り、このソリューションには多くの制約があります。

メトリック検索のデータ構造の 1 つに、文字列類似検索に使用できるBK-Treeがあります。

あなたの問題の候補は、 VP ツリーと M ツリーです。

O(log n * n) でツリーを構築し、O で検索するときに距離 > m (セット内の要素の最大数) を検索している場合、メトリック ツリーの最悪のケースは O(n^2) です。 (n^2)。

それとは別に、実際のランタイムの複雑さは、検索の実行中にメトリック ツリーのサブツリーをプルーニングする能力に依存します。メトリクス ツリーでは、ピボット要素から検索要素までの距離がピボット要素の半径よりも大きい場合、サブツリーをスキップできます (これは少なくとも祖先からピボット要素までの最大距離です)。エントリ セットがかなり分離している場合、実行時間全体はメトリック ツリー O(log n * n) の構築時間によって支配されます。

于 2010-04-23T09:27:13.997 に答える