1

我有一个相当大的项目要完成，我遇到了一些死胡同。我想看看这里的伟大社区是否有任何建议。

我有一个大数据集，我正在尝试构建一个社交图。该数据包含超过 950 万个坐标到 Short 值的映射。对于 ConcurrentHashMap 中的键值，我使用的是字符串，即在其间用 ',' 连接的坐标。

本质上，我正在查找用户之间共有的组数。我有一个非常容易构建的初始哈希图，它将 GroupID 映射到 AvatarID 的向量。这部分运行良好。然后，我有 12 个线程负责他们自己的 GroupID 集和处理（将每个 groupID 中用户之间的计数加 + 1），所有访问都从 ConcurrentHashMap 完成。

在处理了大约 8000 个组后，出现访问问题。一次似乎只有一个线程处于活动状态，我不确定这是因为尺寸过大还是其他因素。这是一个问题，因为我总共需要处理 300,000 个组（并且要及时处理）。

关于我如何实现这一点以及我可以使用的任何快捷方式有什么建议吗？我认为读写同样重要，因为如果值存在（如果不创建它），我必须读取坐标，然后将值加一并写回。

我愿意根据需要提供代码，我只是不知道哪些部分与讨论相关。

谢谢你的时间，-mojavestorm

进一步说明：

两种实现及其限制：

1) 我有一个 HashMap(Integer, Vector(Integer)) preMap，其中包含一个 GroupID 作为键和一个用户 ID 向量。线程在彼此之间拆分 GroupID，并使用返回的每个 Vector(Integer)，每个线程根据坐标（即 UserID x 和 UserID y 一起属于（短）n 个组）将一个短值存储到一个 TLongShortHashMap threadMap 中，并且每个线程都拥有自己的线程映射。坐标映射到长值。每个线程完成后，将每个threadMap中对应key的值添加到combinedMap中的同一个key中，这将显示整个系统中有多少组UserID x和UserID y一起属于。

这个实现的问题是线程之间有很高的重叠，所以创建了过多的短值。例如，用户 1 和用户 2 一起属于不同的组。线程 A 和线程 B 负责他们自己的组范围，包括用户 1 和用户 2 所属的组，因此线程 A 和线程 B 都在他们的 threadMap 副本中存储坐标 (1, 2) 的长值和一个短值。如果发生过多重叠，则内存需求可能会很突出。就我而言，我分配给 Java 的所有 46GB 内存都用完了，而且速度也很快。

2）在这个实现中使用相同的preMap，每个线程都被赋予了他们负责的用户坐标范围。每个线程运行，并获取它拥有的每个坐标并遍历 preMap，检查每个 groupID 并查看 UserID x 和 UserID y 是否属于从 preMap 返回的向量。此实现消除了线程映射之间将发生的重叠。

这个问题是时间。目前，该计划正以惊人的速度运行，需要 1400 年才能完成。使用的内存在 4GB 到 15GB 左右波动，但似乎保持“低”。不完全确定它会保持在限制范围内，但是，我想它会。对我来说没有明显的改进。

希望这些描述清楚，有助于深入了解我的问题。谢谢。

4

1 回答 1

4

我会让每个线程处理自己的地图。这意味着每个线程可以相互依赖地工作。线程完成后，您可以合并所有结果。（或者可能在完成时将结果组合起来，但这可能会增加复杂性而没有太大优势）

如果您使用的是短的，我会在像TObjectIntHashMap这样的集合中使用它，它对于处理原语更有效。

在简单的情况下，您有short坐标 public static void main(String... args) throws IOException { int length = 10 * 1000 * 1000; 整数 [] x = 新整数 [长度]; 整数 [] y = 新整数 [长度]；

  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>

如果您有双坐标，则需要使用两层地图。

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 回答