1

私には達成すべき非常に大きなプロジェクトがあり、いくつかの行き詰まりに直面しています。ここの素晴らしいコミュニティに何か提案があるかどうかを見たかったのです。

私は大規模なデータセットを持っており、ソーシャルグラフを作成しようとしています。データには、Short値への座標の950万を超えるマッピングが含まれています。ConcurrentHashMapのキー値には、文字列を使用しています。これは、間に「、」を連結した座標です。

基本的に、ユーザー間で共通するグループの数を見つけています。GroupIDをAvatarIDのVectorにマップする非常に簡単に作成できる初期ハッシュマップがあります。この部分は正常に動作します。次に、独自のGroupIDのセットと処理（各groupIDのユーザー間のカウントに+1を追加）を担当する12のスレッドがあり、すべてのアクセスはConcurrentHashMapから行われます。

約8000のグループが処理された後、アクセスに関する問題が発生します。一度に1つのスレッドだけがアクティブになっているように見えますが、これが巨大なサイズによるものなのか、それとも別の要因によるものなのかはわかりません。合計で（そしてタイムリーに）処理する必要がある300,000のグループがあるため、これは問題です。

これをどのように実装するか、および使用できるショートカットについてアドバイスはありますか？値が存在する場合（作成しない場合）に座標を読み取り、値に1を追加して書き戻す必要があるため、読み取りと書き込みも同様に重要であると考えています。

必要に応じてコードを提供したいと思っていますが、どの部分がディスカッションに関連するかはまだわかりません。

お時間をいただきありがとうございます、-mojavestorm

詳細な説明：

2つの実装とその制限：

1）キーとしてGroupIDとuserIDのVectorを含むHashMap（Integer、Vector（Integer））preMapがあります。スレッドはGroupIDを相互に分割し、返された各Vector（Integer）を使用して、各スレッドは座標に従って短い値を格納します（UserIDxとUserIDyは（短い）nグループに属します）。各スレッドは独自のthreadMapを所有しています。座標は長い値にマップされます。各スレッドが完了すると、各threadMapの対応するキーの値がcombinedMapの同じキーに追加されます。これにより、システム全体でUserIDxとUserIDyが一緒に属するグループの数が示されます。

この実装の問題は、スレッド間に高いオーバーラップがあるため、過度の短い値が作成されることです。たとえば、ユーザー1とユーザー2は一緒にさまざまなグループに属しています。スレッドAとスレッドBは、ユーザー1とユーザー2が属するグループを含む、独自の範囲のグループを担当します。したがって、スレッドAとスレッドBはどちらも、スレッドマップのコピーに座標（1、2）と短い値。過度のオーバーラップが発生した場合、メモリ要件が未解決になる可能性があります。私の場合、Javaに割り当てた46GBのRAMはすべて使い果たされ、すぐに使い果たされてしまいます。

2）この実装で同じpreMapを使用して、各スレッドには、担当するユーザー座標の範囲が与えられます。各スレッドは実行され、各スレッドを取得してpreMapを反復処理し、各groupIDをチェックして、UserIDxとUserIDyがpreMapから返されたベクトルに属しているかどうかを確認します。この実装により、threadMap間で発生するオーバーラップが排除されます。

これの問題は時間です。現在、このプログラムは1400年という驚異的な速度で実行されています。メモリは約4GBから15GBの揺れを使用しましたが、「低い」ままのようです。制限内に収まるかどうかは完全にはわかりませんが、そうなると思います。私には明らかな改善はありません。

うまくいけば、これらの説明が明確であり、私の問題への洞察を与えるのに役立つでしょう。ありがとう。

4

1 に答える 1

4

各スレッドに独自のマップを処理させます。これは、各スレッドが相互に依存して機能できることを意味します。スレッドが終了したら、すべての結果を組み合わせることができます。（または、完了時に結果を組み合わせることができますが、これにより複雑さが増し、あまり利点がなくなる可能性があります）

ショートを使用している場合は、プリミティブの処理により効率的なTObjectIntHashMapのようなコレクションで使用します。

単純なケースでは、short座標がありますpublic static void main（String ... args）throws IOException {int length = 10 * 1000 * 1000; int [] x = new int [length]; int [] y = new int [length];

  Random rand = new Random();
  for (int i = 0; i < length; i++) {
    x[i] = rand.nextInt(10000) - rand.nextInt(10000);
    y[i] = rand.nextInt(10000) - rand.nextInt(10000);
  }

  countPointsWithLongIntMap(x, y);
  countPointsWithMap(x, y);

}

private static Map<String, Short> countPointsWithMap(int[] x, int[] y) {
  long start = System.nanoTime();
  Map<String, Short> counts = new LinkedHashMap<String, Short>();
  for (int i = 0; i < x.length; i++) {
    String key = x[i] + "," + y[i];
    Short s = counts.get(key);
    if (s == null)
      counts.put(key, (short) 1);
    else
      counts.put(key, (short) (s + 1));
  }
  long time = System.nanoTime() - start;
  System.out.printf("Took %.3f seconds to use Map<String, Short>%n", time/1e9);

  return counts;
}

private static TIntIntHashMap countPointsWithLongIntMap(int[] x, int[] y) {
  long start = System.nanoTime();
  TIntIntHashMap counts = new TIntIntHashMap();
  for (int i = 0; i < x.length; i++) {
    int key =  (x[i] << 16) | (y[i] & 0xFFFF);
    counts.adjustOrPutValue(key, 1, 1);
  }
  long time = System.nanoTime() - start;
  System.out.printf("Took %.3f seconds to use TIntIntHashMap%n", time/1e9);
  return counts;
}

プリント

Took 1.592 seconds to use TIntIntHashMap
Took 4.889 seconds to use Map<String, Short>

座標が2つある場合は、2層マップを使用する必要があります。

public static void main(String... args) throws IOException {
  int length = 10 * 1000 * 1000;
  double[] x = new double[length];
  double[] y = new double[length];

  Random rand = new Random();
  for (int i = 0; i < length; i++) {
    x[i] = (rand.nextInt(10000) - rand.nextInt(10000)) / 1e4;
    y[i] = (rand.nextInt(10000) - rand.nextInt(10000)) / 1e4;
  }

  countPointsWithLongIntMap(x, y);
  countPointsWithMap(x, y);

}

private static Map<String, Short> countPointsWithMap(double[] x, double[] y) {
  long start = System.nanoTime();
  Map<String, Short> counts = new LinkedHashMap<String, Short>();
  for (int i = 0; i < x.length; i++) {
    String key = x[i] + "," + y[i];
    Short s = counts.get(key);
    if (s == null)
      counts.put(key, (short) 1);
    else
      counts.put(key, (short) (s + 1));
  }
  long time = System.nanoTime() - start;
  System.out.printf("Took %.3f seconds to use Map<String, Short>%n", time / 1e9);

  return counts;
}

private static TDoubleObjectHashMap<TDoubleIntHashMap> countPointsWithLongIntMap(double[] x, double[] y) {
  long start = System.nanoTime();
  TDoubleObjectHashMap<TDoubleIntHashMap> counts = new TDoubleObjectHashMap<TDoubleIntHashMap>();
  for (int i = 0; i < x.length; i++) {
    TDoubleIntHashMap map = counts.get(x[i]);
    if (map == null)
      counts.put(x[i], map = new TDoubleIntHashMap());
    map.adjustOrPutValue(y[i], 1, 1);
  }
  long time = System.nanoTime() - start;
  System.out.printf("Took %.3f seconds to use TDoubleObjectHashMap<TDoubleIntHashMap>%n", time / 1e9);
  return counts;
}

プリント

Took 3.023 seconds to use TDoubleObjectHashMap<TDoubleIntHashMap>
Took 7.970 seconds to use Map<String, Short>
于 2011-08-27T20:31:07.373 に答える