在mapreduce中从n个元素中选择k

Question

假设输入x条记录，其中n具有所需的属性(例如它们的值为正)，并且所有x都具有唯一键。

我想做的是，使用MapReduce中的map-only job，精确地发出这些n记录的k。

例如，假设这是我的输入:

(a, 10)
(g, -3)
(c, -2)
(f, 4)
(s, 2)

，我想要发出恰好2个正值的元素。本例中x为5,n为3,k为2。在工作开始之前，我知道x(我认为不需要)，k和n。问题是具有正值的记录可以由不同的映射器处理。

我想到的是，在每个映射器中使用大小为n的哈希表，并使用键的哈希值将具有正值的元素放在这个哈希表中。然后，将发出哈希表的第一个k位置中的元素。但是，如果两个记录位于同一个哈希桶中，则无法工作。替代品吗?

Answer 1

有一种方法可以使用仅映射的作业和一些顺序代码来完成它，但是它相当简陋，在大多数情况下，使用reducer更简单。

在一个更形式化的语言中，你想做一个过滤器(sql where)和一个选择(sql limit)。过滤器可以并行化，而选择不能，除非你想采用概率方法。

思路如下:

1. 在您的纯地图作业中，您可以根据您的选择标准过滤数据。
2. 您还可以跟踪关于您在映射器中过滤了多少记录的元信息。
3. 将此数字写入共享文件系统中的文件中，我猜在您的情况下是HDFS。以任务id或输出文件名加上一些后缀来命名文件。

3.应该在您的文件系统中产生一堆您可以读取的元文件，以及相应的映射输出。然后贪婪地读取一个新的元文件，直到达到k。如果您在映射输出/元文件中有更多的记录，您可以修剪输出文件(或告诉接下来的任何内容，它只需要从"溢出"文件中读取y记录)。