Java MapReduce 2个字段到时间幻灯片中

Question

>我有以下输入：

{"start_time": 1, "end_time" 3, "app_name": "app1"}
{"start_time": 2, "end_time" 4, "app_name": "app2"}
{"start_time": 3, "end_time" 5, "app_name": "app1"}
{"start_time": 3, "end_time" 5, "app_name": "app2"}
{"start_time": 10, "end_time" 12, "app_name": "app1"}
{"start_time": 15, "end_time" 17, "app_name": "app2"}

我需要将此输入转换为每个应用程序的时间范围吗？ 输出应如下所示：

{app1, [{1,5}, {10,12}, app2 [{2,5}, {15,17}]]

我想过使用mapreduce，但我不确定如何... 有什么想法吗？ 谢谢

Answer 1

以下只是一种可能的解决方案，不能保证是最佳的。

上。这是我为澄清而编写的演示。如果看到这一点的人对改进有更好的想法，请通过 github 问题告诉我。

一开始，我们可以将问题分为三个部分：

0. 将map-reduce视为返回一系列键值结果，这个问题的关键是什么？
1. 如何设计地图部分的返回类型？
2. 已经映射后如何减少？

不用说，第 0 个问题的答案是app.因此，我们将输入分为两部分，一部分用于app1，另一部分用于app2。我们只研究一部分，比如app2，因为这个比app1要复杂一些。

在设计 map 函数时，我们应该注意到类型必须有利于归约，同时自然地显示结果。考虑到结果，它以List<Pair>的形式显示。所以第一个问题的答案是List<Pair>.

因此，我们使用mapToPair以(app, [(begin, end)])的形式映射每一行输入。然后我们只考虑如何减少。

事情变得更容易了。归约过程本身是一个经典问题——区间合并，最经典的解决方案是O(nlogn)算法。但这个问题是另一个版本，因为在减少时，列表本身自然是按两侧排序的。因此，可以省略排序部分，从而产生O(n+m)的单传递合并排序类算法。尝试将此算法应用于app2，您将成功。

副作用是，创建了太多List，同时Pair。一种可能的方法是使用可变设计，当省略冗余对时，正确收集它们，当需要创建新对时，只需使用收集的对。