当k太大而无法容纳内存中的k个元素时，有什么有效的mapreduce算法可以从数据集中找到前k个元素？我说的是一个包含数百万个元素的数据集，k是其中的3/4。假设每个元素都有一个值，我们想找到k个值最高的元素。e、 g.表格中的数据：e1:5个e2:第10页e3:第7页e4:第8页然后，前两位是e4和e2（不关心它们的相关顺序）。当k足够小的时候，我已经看到了问题的解决方案，但是它不可伸缩。显然，使用一个减速机，将再次不实用（内存不足错误）。
bvjveswy1#
你需要一个两人工作的方法：第一份工作：在mapper中执行所描述的逻辑，以获得reducer中的分组计数。然后，reducer将count（as key）写入一个键值对（as value）。如果遇到性能问题，这里的减速器可以并联。第二份工作：Map器只是Map身份。通过定义一个反向比较器来处理降序排序。这里的单个reducer获取降序排序的数据。然后您可以简单地递增，直到达到“k”并发出值。请注意，您可能有具有相同计数的项，因此您需要将从减少的值中获得的每个值作为新的“k”进行计数。
djp7away2#
我想我找到了我要找的东西。答案就在这里：http://www.philippeadjiman.com/blog/2009/12/20/hadoop-tutorial-series-issue-2-getting-started-with-customized-partitioning/这个想法是使用totalorderparitioner。这个分区器首先需要一个采样，可以使用输入采样器（比如randomsampler）生成。我相信，这种采样用于负载平衡，以确保所有减速机获得几乎相同的工作量（数据）。默认分区器（hashpartitioner）的问题是（key，value）对将在其中结束的缩减器是基于密钥的哈希的。然后，在每个减速机的输入中进行排序。这并不能保证一个更大的密钥将由一个“跟随”的减速机处理。totalorderpartitioner保证后者，采样用于负载平衡。数据完全排序后，我们可以选择最后一个k（例如，使用 tail -k 命令的结果 hadoop dfs -getmerge )，或者使用一个反向比较器，取第一个k，就像托马斯·荣布吕特建议的那样。如果我的答案不正确，请随意评论/编辑。编辑：这里提供了一个更好的示例（在源代码方面）。编辑2：看来这个问题毕竟是一个“经典”问题，汤姆·怀特的书《hadoop最终指南》（第1版第223页）的“总体分类”一节也描述了解决方案。您也可以通过此链接进行免费预览。
tail -k
hadoop dfs -getmerge
zlhcx6iw3#
这可能不是最有效的，但它很容易理解和实施。mapreduce stage-1：将还原数设置为1。Map：读取输入（键k，值v）对并将它们发送到减速器，键为v，值为k。reduce：当数据通过网络发送时，shuffle阶段将根据数字值（因为它们是键）对数据进行排序。数据将到达reducer，reducer将按排序顺序输出单个文件。mapreduce第二阶段：不需要reduce阶段。map：读取单个排序文件并输出前k个元素。如果要选择top k，其中k是百分比，则可以在stage-1Map阶段使用hadoop计数器来计算输入文件中存在的记录数，然后在stage-2期间使用另一个计数器来选择top k百分比。
3条答案
按热度按时间bvjveswy1#
你需要一个两人工作的方法：
第一份工作：
在mapper中执行所描述的逻辑，以获得reducer中的分组计数。然后，reducer将count（as key）写入一个键值对（as value）。如果遇到性能问题，这里的减速器可以并联。
第二份工作：
Map器只是Map身份。通过定义一个反向比较器来处理降序排序。
这里的单个reducer获取降序排序的数据。然后您可以简单地递增，直到达到“k”并发出值。
请注意，您可能有具有相同计数的项，因此您需要将从减少的值中获得的每个值作为新的“k”进行计数。
djp7away2#
我想我找到了我要找的东西。答案就在这里：http://www.philippeadjiman.com/blog/2009/12/20/hadoop-tutorial-series-issue-2-getting-started-with-customized-partitioning/
这个想法是使用totalorderparitioner。这个分区器首先需要一个采样，可以使用输入采样器（比如randomsampler）生成。我相信，这种采样用于负载平衡，以确保所有减速机获得几乎相同的工作量（数据）。
默认分区器（hashpartitioner）的问题是（key，value）对将在其中结束的缩减器是基于密钥的哈希的。然后，在每个减速机的输入中进行排序。这并不能保证一个更大的密钥将由一个“跟随”的减速机处理。totalorderpartitioner保证后者，采样用于负载平衡。
数据完全排序后，我们可以选择最后一个k（例如，使用
tail -k命令的结果hadoop dfs -getmerge)，或者使用一个反向比较器，取第一个k，就像托马斯·荣布吕特建议的那样。如果我的答案不正确，请随意评论/编辑。编辑：这里提供了一个更好的示例（在源代码方面）。
编辑2：看来这个问题毕竟是一个“经典”问题，汤姆·怀特的书《hadoop最终指南》（第1版第223页）的“总体分类”一节也描述了解决方案。您也可以通过此链接进行免费预览。
zlhcx6iw3#
这可能不是最有效的，但它很容易理解和实施。
mapreduce stage-1：将还原数设置为1。
Map：读取输入（键k，值v）对并将它们发送到减速器，键为v，值为k。
reduce：当数据通过网络发送时，shuffle阶段将根据数字值（因为它们是键）对数据进行排序。数据将到达reducer，reducer将按排序顺序输出单个文件。
mapreduce第二阶段：不需要reduce阶段。
map：读取单个排序文件并输出前k个元素。
如果要选择top k，其中k是百分比，则可以在stage-1Map阶段使用hadoop计数器来计算输入文件中存在的记录数，然后在stage-2期间使用另一个计数器来选择top k百分比。