如何交叉两组不适合内存的长？

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

我想知道有哪些有趣的方法可以解决此问题。

到目前为止，我想到的是从磁盘中读取每个原始集的子集，这些子集足以适应内存，然后将每个子集与每个子集相交，然后将它们暂时写入磁盘。最后，我可以通过这些子集并与这些子集相交。我觉得这可能会变成地图减少工作。

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

分别对A和B分别进行排序。
从集合b
如果它们相等，请添加到结果集。
如果一组项目更大，请从第二组中获取下一个项目。
只要您不到达任何集合的末端，请访问2。

这种方法的优点是，您永远不会在内存中保留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]

一种可能更有效的方法，然后排序是使用哈希，然后将数据拆分为几个垃圾箱 - 并在每个垃圾箱上进行相交。这个想法是将问题拆分为确实适合内存中的子问题 - 然后您可以在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|)

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

虽然任何基于排序的算法最有可能需要更多的1读 1写（以及在数据上进行额外的遍历） - 它会产生更多的 3 * (|R|+|S|)

P.S。目前，我正在研究文件系统考试（将于周一举行），该讲义说，这是大多数数据库系统中首选的解决方案，假设您有一个磁盘。

如果可用或磁盘，在内存中初始化2个大映射到零（BITMAP1和BITMAP2）。对于SET1中的每个值，将值thtmap1位置设置为1。对于set2中的每个值，在BITMAP1位中读取值-Th位置，如果1，则将值-TH位置设置为1。对于BitMap2中的每个集合值，该位置的输出值。

编辑：下面的杰索普在回复中指出了缺陷：是java 64位（8个字节）长int，而不是32位体系结构C编译器4字节长ints。该解决方案是不切实际的，有64位长度。

这确实感觉像是一张地图减少了工作，但是您必须非常小心您选择的子集。如果您希望您的交叉点起作用，则必须在同一点切下原始集合的子集。例如，假设您有设置

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}

显然是错误的。对于您的地图减少工作，您必须使用一些恒定值剪切集，例如A1和B1包含值＆lt; 5和a2和B2值> = 5。

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

想到的一个明显的事情是从磁盘上的分类集开始。然后，您可以同时从两个文件中读取，查找匹配项并将其写出。假设您从一个文件中读取204，您会从另一个文件中读取直到第一个数字> = 204。那时，您知道该特定数字是否属于交叉点。

您的第一步可能是对每个组进行排序；排序较小的块＆amp;合并排序以构建分类文件。

一旦分类，您就可以穿过两组。

您可以轻松地保持512个文件打开，因此您可以将这两个集合在磁盘上的256个块中，最多为1600万，每个尺寸为64兆字节。您可以根据每长的最重要字节来执行此操作，从set.a.00到set.b.ff

然后，您可以加载每个相应的块对（ set.A.42包含longs以0x42开头的longs对应于 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，依此类推。

也有可能（如果文件系统缓存不太好，也许更有效）可以保留一系列256个"存储桶"，每个16384 Longs的大小（又是16m）。当存储桶接近满足时，您可以在磁盘上打开相应的块文件，将迄今为止发现的16384 Long s转换，然后关闭文件。然后对集合B进行相同的操作。您最终得到了512个文件，其中包含0（不太可能）至1600万 Long s，一次从未保留过两个以上的文件。

相关内容

最新更新

热门标签：