时间戳

首页 > 解决方案 > Java MapReduce 将 2 个字段转换为时间幻灯片

java - Java MapReduce 将 2 个字段转换为时间幻灯片

问题描述

我有以下输入：

{"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，但我不确定如何......有什么想法吗？谢谢

标签： javamapreduce

解决方案

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

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

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

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

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

在设计map函数的时候，要注意类型一定要利于reduced，同时要自然的展示结果。考虑到结果，它以 的形式表示List<Pair>。所以第一个问题的答案是List<Pair>。

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

事情变得容易了。reduce过程本身就是一个经典问题——区间合并，最经典的解决方案就是O(nlogn)算法。但这个问题是另一个版本，因为在归约时，列表本身自然是两边排序的。因此可以省略排序部分，从而导致O(n+m)一次性合并排序算法。尝试将此算法应用于app2，你会成功的。

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

推荐阅读