java - 计算每个重叠间隔数的最佳 MapReduce 算法

Question

[a, b] 格式有数十亿个区间，它们都会将数字空间切割成多个单片。我打算输出所有单件，其中重叠间隔的数量在这件作品中。

例如:有3个区间，分别是:[1,7]、[2,3]、[6, 8]。它应该输出如下结果:

[-∞, 1]: 0

[1, 2]: 1

[2, 3]: 2

[3, 6]: 1

[6, 7]: 2

[7, 8]: 1

[8, +∞]: 0

如果对于单个机器(不是 MapReduce 中的分布式解决方案)，我知道解决方案可以将间隔实例分解为 start_n、end_n，排序数字并从左到右迭代并使用计数器来计算当前件和输出中的数量。但我不确定如何将此算法拆分为分布式方式。

有什么建议吗？谢谢。

Answer 1

在 mapreduce 中，最简单的方法是将对中的每个数字写入 reducer。 sort shuffle 阶段负责对数字进行排序，reducer 负责修复。

例如对于输入对 [1,7]映射器输出将是:

key: NullWritable  Value: 1
key: NullWritable  Value: 7
key: NullWritable  Value: 1_7

使用相同的模式，所有映射器的输出形式将是:

key: NullWritable  Value: 1
key: NullWritable  Value: 7
key: NullWritable  Value: 1_7
key: NullWritable  Value: 2
key: NullWritable  Value: 3
key: NullWritable  Value: 2_3
key: NullWritable  Value: 6
key: NullWritable  Value: 8
key: NullWritable  Value: 6_8

排序-洗牌步骤会将输出聚合为

Key: NullWritable  ListOfValue: [1,1_7,2,2_3,3,6,6_8,7,8]

Reducer 遍历值列表(这将是一个有序列表)和

• 将对值分离到一个单独的列表中 [1_7, 2_3, 6_8] .您可以只检查是否出现 _在文本中找出这对。

• 如下重新配对空间值。


[-infinity, 1]
[1, 2]
[2, 3]
[3, 6]
[6, 7]
[7, 8]
[8, +infinity]


• 重新配对时，只需对照上面的列表检查边界以找到计数。你可以用“_”拆分这对并通过 parse 转换成数字。功能。

例如-infinity(比如一个非常大的负 long -9999999)超出了所有对的范围，因此 reducer 输出将是

key: “[-无穷大，1]”(Text 类型)value: 0 ( IntWritable` 类型)

对 [1,2] 也类似, 1>=1 and 2<=7所以reducer输出

key: “[1, 2]”(Text 类型)value: 1 ( IntWritable` 类型)

对[6,7] , 6>=1 and 7<=7和 6>=6 and 7<=8所以reducer输出

key: “[1, 2]”(Text 类型)value: 2 ( IntWritable` 类型)

等等……

备注:NullWritable是 Java hadoop API , 仅代表 null .而不是 NullWritable ，您可以使用任何常量数据(比如 Hadoop Text 类型 Writable )。这里的要点是确保所有映射器输出都应该由于相同的映射器键而落到单个 reducer 。