6

2 人のユーザーが同じグループにいる回数をカウントするプログラムを作成する必要があります。ユーザーはユーザー名で、グループは ID で指定されます。たとえば、入力 (テキスト ファイルに保存) を使用すると、次のようになります。

john 32
john 21
jim 21
jim 32
bob 32

結果が欲しい：

john-jim 2 
john-bob 1
jim-bob 1

これは些細なことに聞こえます。しかし問題は、180 万のグループと 300,000 のユーザーがいるということです。そして、多くのメンバーシップ (ユーザーあたり少なくとも平均 50、おそらくそれ以上になると予想しています)。これは、膨大な量のデータと処理を意味します。

私はこれを行う 5 つの異なるプログラムを作成しましたが、どれもデータ量を削減できませんでした: PostgreSQL クエリとしては遅すぎました。Java 作業メモリ内の Map で実行すると、メモリを消費しすぎます (最初のヒープ領域、最適化後、まれに「GC オーバーヘッド制限を超えました」)。Java からデータベースに継続的に書き込むには遅すぎます (バッチクエリを使用して最適化した場合でも)。ますます必死になって、すべてのペアを配列に書き込み、それらを並べ替え (O(n log (n)))、peu à peu をカウントするなど、よりエキゾチックなことを試しました。しかし、それでもメモリに保存するにはデータが多すぎました。

これを行うためのアルゴリズムに関するアイデアはありますか? それとも無理ですか？

4

3 に答える 3

7

RDBMS は、並べ替えなどの操作に特化しています。DB の外でこれを行うと、パフォーマンスが向上することはほとんどありません。SQLでやれ！

これは仕事をします（アップデートで簡略化されています）：

SELECT t1.usr || '-' || t2.usr, count(*) AS ct
FROM   usr_grp t1
JOIN   usr_grp t2 USING (grp_id) 
WHERE  t2.usr > t1.usr   -- prevent dupes and get sorted pair
GROUP  BY t1.usr, t2.usr;

あなたが言ったように、オーバーラップの数によっては、膨大な量の行が生成される可能性があります。したがって、これは決して高速になることはありません。

疑問が生じます: 誰も処理できない何百万もの行を生成する目的は何ですか? そもそも操作は理にかなっていますか?

それをより速くするために、あなたは..

  • アップグレード！ PostgreSQL 8.4 はかなり時代遅れです。特に、PostgreSQL 9.2 はビッグ データに重点​​を置いていました。このような仕事では、はるかに優れたパフォーマンスが期待できます。
    そして誰も8.4.0 を走らせるべきではありません。セキュリティ上の理由だけでも、多くのバグ修正を見逃しています。現在のポイント リリースは 8.4.17 です。リンク先のウェブサイトを引用します。

すべてのユーザーが、使用中のメジャー バージョンに関係なく、利用可能な最新のマイナー リリースを実行することを常にお勧めします。

  • integerユーザーの代理キーとして を使用するため、 でのみ整数を扱いますusr_grp。テーブルとインデックスを小さくし、処理を高速化します。n:m テーブル ( usr_grp) のカーディナリティが table よりもはるかに大きいusr場合、追加の結合を意味する場合でも、これは高速になるはずです。

SELECT u1.usr  || '-' || u2.usr, count(*) AS ct
FROM   usr_grp t1
JOIN   usr_grp t2 USING (grp_id) 
JOIN   usr u1 ON t1.usr_id = u1.usr_id
JOIN   usr u2 ON t2.usr_id = u2.usr_id
WHERE  t2.usr_id > t1.usr_id
GROUP  BY u1.usr_id, u2.usr_id;


    CREATE INDEX usr_grp_gu_idx ON usr_grp(grp_id, usr_id);

テストケース

@OldCurmudgeon が彼のテスト ケースについて報告した数値を参考にして、PostgreSQL で同等のテスト ケースを作成しました。

-> SQLfiddleデモ。

この公開テスト データベースでは~ 250 ミリ秒。
これが指定されていないため、結果は順序付けされません (no ORDER BY)。2.5分
と比較して、以下に報告します。係数 600。

于 2013-04-05T10:01:59.170 に答える
2

ファイルシステムにそれを任せるのはどうですか。

エントリごとに、グループ ID の名前のファイルを開き、新しいユーザーの名前を追加します。グループごとに 1 つのファイルが作成されます。

あなたは今持っています - 例えば：

Group-21.txt
 jim
 john

Group-32.txt
 bob
 jim
 john

次に、すべてのファイルを実行して、その中のすべてのユーザー名のペアを生成します (名前を並べ替えて、それらに対して標準的な組み合わせプロセスを実行します)。ペアごとに、特定の名前のファイルに「1」を追加します。

あなたは今持っています - 例えば：

User-jim-john.txt
 11

User-bob-jim.txt
 1

User-bob-john.txt
 1

これで、ファイル内にファイル名とカウント (単項なので、本当に必要なのはファイル サイズ (バイト単位) だけ) のペアができました。

フェーズ 1 はフェーズ 2 が始まる前に完了する必要がありますが、これらのほとんどすべてを並行して実行できます。速度を向上させるには、コアを追加し、より高速なディスクを購入します。メモリ制限はなく、ディスクのみです。

追加:スレッドを 1 つだけ使用して、このアルゴリズムでいくつかのシミュレーション テストを実行しました。

1800 のグループ、300 のユーザー、および 15000 のメンバーシップがすべてランダムに生成されるのに約 2.5 分かかりました。900 のグループ、150 のユーザー、および 7500 のメンバーシップに 54 秒かかりました。

于 2013-04-05T10:33:47.710 に答える
1

解決策が何であれ、複雑さは生成されるペアの数に依存し、必ずしもグループや人の数には依存しません。さまざまなグループ サイズの場合:

  • 10 メンバーのグループは C(10,2) = 45 ペアを生成します
  • 100 メンバーのグループは C(100,2) = 4950 ペアを生成します
  • 1000 人のメンバー、499,500 組のグループ...
  • 10,000 人のメンバーを擁する 1 つのグループは、5,000 万足近くのペアを生産します。したがって、1 つのグループが、残りの計算の全コストを上回ることができます。

したがって、私の最初の提案は、データセット内の非常に大きなグループを除外することです。大きなグループを省略できず、メモリに収まらないか、単一のスレッドで処理するには時間がかかることがわかった場合は、次のようにMap-Reduceを使用して計算を自動的に並列化できます。次のようなグループ メンバーシップから始める場合:

32 -> john, jim, bob
21 -> john, jim

map ステップを使用して、すべてのペアを生成できます。

john-jim -> 32, john-bob -> 32, jim-bob -> 32
john-jim -> 21

これらは、名前のペアごとに集計されます。次に、reduce で、各キーの出現回数を数えます。これは、すべてのペアを格納するための十分なディスクがあることを前提としています。

于 2013-04-05T10:41:22.630 に答える