Java Mapreduce排序复合值

Question

我有一个映射器，它发出一个文本（水果名称）键和一个自定义复合值city:count。我希望在复合值到达reducer之前，根据计数对其进行排序，以便reducer可以快速确定哪个城市的计数最高。

复合值类是WritableCompable的扩展，具有检索计数和城市的方法。

我的减速机目前收到的是：

reducer 1 - oranges:<london:2, chicago:15, charleston:6>
reducer 2 - apples:<charleston:31, london:3, chicago:29>
...

我希望我的减速机收到什么：

reducer 1 - oranges:<chicago:15, charleston:6, london:2>
reducer 2 - apples:<charleston:31, chicago:29, london:3>

从逻辑上讲，我该如何做到这一点？我读过几篇关于辅助排序/排序的文章，但它们倾向于关注复合键而不是复合值。我的密钥不需要进一步分区，也不需要进一步排序。

同样，按复合值而不是复合键排序！

Answer 1

如果你只是想快速确定水果的最高含量，我想推荐另一种方法。因为在大多数情况下，排序的复杂性为O（n log n），而查找最大的条目只有O（n）其中n是您的情况下的城市数量。

1. 带内存的映射器

您可以在每个映射器中使用哈希图来确定每个映射器中每个水果的最高数量。只需使用水果作为键，城市计数作为值。当您得到一个水果时，请查看地图以比较更大的水果。如果水果不存在，您显然必须设置它。当执行所有地图步骤时，框架会调用映射器的清理方法。在清理过程中，您可以发出地图的条目。这将大大减少您必须发送和在减速器中通过的值的数量。

2.组合器

方法1有一个明显的缺点。如果你有大量不适合内存的水果，它是不可扩展的。如果是这种情况，你可以使用一个在映射器端执行的组合器。它的工作方式就像一个由相应映射器给出的较小数据集的简化器。这也将导致你发送到简化器的值数量减少的好处。

3. 二次订购

你可以通过二次订购来做到这一点。我真的很想鼓励你阅读Preeti Khurana提供的文章。尤其是Sudarshan的回答。给你一个简短的想法：使用一个水果：计数和城市：计数的值的复合键。请注意，您需要一个基于键的第一部分的特殊分区。我认为这将是一个很高的工作量，但在某些情况下，这是有用和必要的。