7

我有一个有趣的问题。我想在 Java 中相交两组 Longs，每组有 1B 个成员 - 这是每组 4GB。这不适合我需要运行它的服务器上的内存。

我想知道有什么有趣的方法可以解决这个问题。

到目前为止，我想出的是从磁盘中读取每个原始集的子集，这些子集足够小以适合内存，然后与每个子集相交，并将它们临时写入磁盘。最后，我可以遍历并与这些子集相交。我有一种感觉，这可能会变成地图缩减工作。

也许你会有一些更好的想法:) 我怀疑我是第一个提出这个问题的人。

4

9 回答 9

8

  1. 对两组进行排序A并B分别排序。

  2. 从集合 A 中取出第一个元素，从集合 B 中取出第一个元素

  3. 如果它们相等，则添加到结果集中。

  4. 如果一组中的项目更大，则从第二组中取出下一个项目。

  5. 只要你没有达到任何一组的结尾，就转到 2。

这种方法的优点是您永远不会在内存中保留超过 2 个 long（排序除外）。可以在磁盘上有效地进行排序（合并排序）。

于 2012-10-20T18:31:21.270 回答
2

对两组进行基于磁盘的合并排序。

完成后，您可以简单地按顺序浏览排序的文件并将交叉点记录在一个新文件中。

于 2012-10-20T18:30:04.957 回答
2

这是我认为可以做到的。显然放在磁盘上。你必须对它们进行排序。

  1. 使用外部排序对它们进行排序

  2. 比较，

    if a. length < 1 or b.length < 1
  exit
else if a[0] == b[0]
  addToIntersectionSet(a[0])
  remove a[0] from a
  remove b[0] from b
else if a[0] < b[0]
   remove a[0]
else 
  remove b[0]
于 2012-10-20T18:36:06.430 回答
2

将内存或磁盘中的 2 个大位图初始化为零（bitmap1 和 bitmap2）。对于 set1 中的每个值，将第 value-th bitmap1 位置设置为 1。对于 set2 中的每个值，读取 bitmap1 位中的第 value-th 位置，如果为 1，则将第 value-th 位置的 bitmap2 设置为 1。对于中的每个设置位值bitmap2，该位置的输出值。

编辑：下面的 Jessop 在回复中指出了这个缺陷：它是 Java 64 位（8 字节）长整数，而不是 32 位架构 C 编译器 4 字节长整数。这个解决方案对于 64 位长是不切实际的。

于 2012-10-20T18:50:10.113 回答
2

一种可能比排序更有效的方法是使用散列，并将数据分成几个箱 - 并在每个箱上做一个交集。这个想法是将问题拆分为适合内存的子问题- 然后您可以在 RAM 上有效地进行交集。

假设您想找到 R,S 的交集：

for each element in R:
   write element in bucket_R[hash(element) % NUM_BUCKETS]
for each element in S:
   write element in bucket_S[hash(element) % NUM_BUCKETS]

//assuming each bucket from bucket_S or bucket_R now fits memory - proceed.
//if it doesn't, you can repeat the previous step with a new hash function.
for each i from 0 to NUM_BUCKETS:
  find bucket_S INTERSECTION bucket_R

重要提示：
bucket_S、bucket_R 或在磁盘上而不是在 RAM 中。

磁盘访问次数：

使用这种方法的磁盘读取总数为3 * (|R|+|S|)

  1. 在迭代前两个循环时读取 R 和 S 中的每个元素
  2. 将每个元素写入哈希表
  3. 阅读所有的桶

虽然任何基于排序的算法最有可能需要超过 1 次读取 + 1 次写入（以及对数据的额外遍历） - 这将产生更多3 * (|R|+|S|)

PS我目前正在准备文件系统考试（将在星期一举行），并且讲义说这是大多数数据库系统中的首选解决方案，假设您有一个磁盘。

于 2012-10-20T21:55:07.770 回答
1

这确实感觉像是一个 map reduce 工作，但你必须非常小心你选择的子集。如果您希望您的交集起作用，则必须在相同点切割原始集合的子集。例如，假设您有集合

A = {1 3 7 9}
B = {2 7 8 9}

然后你把它们分成两个子集：

A1 = {1 3} A2 = {7 9}
B1 = {2 7} B2 = {8 9}

然后你相​​交：

C1 = A1 inter B1 = {}
C2 = A2 inter B2 = {9}

然后你假设：

C = A inter B = C1 union C2 = {9}

这显然是错误的。为了让你的 map reduce 工作，你必须使用一些常数值来切割集合，例如 A1 和 B1 将包含值 <5 和 A2 和 B2 值 >=5。

您还可以从磁盘中获取集合 A 和 B 的常规部分，然后以智能方式将它们相交，这意味着逐步查看已排序的元素，并在到达两个子集之一的末尾时停止。在那一刻，您获取了一个额外的子集部分。

于 2012-10-20T18:28:47.750 回答
1

一件显而易见的事情是从磁盘上的排序集开始。然后您可以同时从两个文件中读取，找到匹配项并将它们写出。假设您从一个文件中读取 204，您会从另一个文件中读取，直到第一个数字 >= 204。此时您知道该特定数字是否属于交集。

于 2012-10-20T18:28:58.167 回答
1

您的第一步可能是对每组进行排序；对较小的块进行排序和合并排序以构建已排序的文件。

排序后，您可以遍历两组。

于 2012-10-20T18:31:11.913 回答
1

您可以轻松地保持 512 个文件处于打开状态，因此您可以将这两个文件预浏览成磁盘上的 256 个块，最多 16M 个项目，每个大小为 64 MB。您可以根据每个 Long 的最高有效字节执行此操作，从 set.A.00 到 set.B.ff

然后你可以加载每对对应的块（set.A.42包含以 0x42 开头的 Long 对应set.B.42）并使用它们来初始化一个 16M 字节数组 - 你将它初始化为全 0，当你i从第一个块中读取值时，你增加索引 i -th)。然后你读入第二个块，但这次增加了 2。

完成后，您对阵列进行扫描；0 表示该值不存在于任一块中，1 表示它仅存在于第一组中，2 仅存在于第二组中，3 表示两者都存在。并将结果写入结果文件。

即使对结果文件进行排序，您也不需要排序（因为您将按顺序检查块，并按顺序进行最终扫描）。

这一切都在 O(n) 中运行（所有步骤都以线性时间运行）并且最多需要 16M 的 RAM。

如果 512 个打开的文件太多，您可以使用前 7 个最高有效位并使用 256 个打开的文件和 32M 的 RAM。或者 128 个打开的文件和 64M 的 RAM，等等。

Longs也可以保留一系列 256 个“桶”（每个 16384大小（所以它又是 16M））（如果文件系统缓存不太好，也许效率更高）。当一个bucket接近满时，你打开磁盘上对应的chunk文件，dump目前Long找到的16384个，然后关闭文件。然后对集合 B 执行相同操作。您最终会得到 512 个文件，其中包含从 0（不太可能）到 1600 万Longs 的文件，并且一次打开的文件永远不会超过两个。

于 2012-10-20T18:43:31.827 回答