211

除了“如何使用 MapReduce 计算长文本中的单词”任务之外，我想不出任何好的例子。我发现这并不是让其他人了解该工具的强大功能的最佳示例。

我不是在寻找代码片段，实际上只是“文本”示例。

4

4 回答 4

311

Map reduce 是一个为高效处理大量数据而开发的框架。例如，如果我们在数据集中有 100 万条记录，并且它以关系表示形式存储 - 派生值并对这些值执行任何类型的转换都是非常昂贵的。

例如，在 SQL 中，在给定出生日期的情况下，要找出一百万条记录中有多少人的年龄 > 30 岁将需要一段时间，而且当查询的复杂性增加时，这只会按数量顺序增加。Map Reduce 提供基于集群的实现，其中数据以分布式方式处理

这是一篇维基百科文章，解释了map-reduce所有内容

另一个很好的例子是通过 map reduce 找朋友可以成为理解这个概念的一个强有力的例子，也是一个很好的用例。

就个人而言，发现这个链接对于理解这个概念非常有用

复制博客中提供的解释（以防链接失效）

寻找朋友

MapReduce 是最初由 Google 开发的框架，允许跨多个域轻松进行大规模分布式计算。Apache Hadoop 是一个开源实现。

我将忽略细节，但归结为定义两个函数：map 函数和 reduce 函数。map 函数接受一个值并输出键：值对。例如，如果我们定义一个 map 函数，它接受一个字符串并输出单词的长度作为键，输出单词本身作为值，那么 map(steve) 将返回 5:steve 而 map(savannah) 将返回 8:savannah . 您可能已经注意到 map 函数是无状态的，只需要输入值来计算它的输出值。这允许我们针对值并行运行 map 函数，并提供了巨大的优势。在我们进入 reduce 函数之前，mapreduce 框架通过键将所有值组合在一起，因此如果 map 函数输出以下键：值对：

3 : the
3 : and
3 : you
4 : then
4 : what
4 : when
5 : steve
5 : where
8 : savannah
8 : research

它们被分组为：

3 : [the, and, you]
4 : [then, what, when]
5 : [steve, where]
8 : [savannah, research]

然后，这些行中的每一行都将作为参数传递给 reduce 函数，该函数接受一个键和一个值列表。在这种情况下，我们可能会试图找出存在多少特定长度的单词，因此我们的 reduce 函数将只计算列表中的项目数并输出具有列表大小的键，例如：

3 : 3
4 : 3
5 : 2
8 : 2

减少也可以并行完成，再次提供了巨大的优势。然后我们可以查看这些最终结果，发现我们的语料库中只有两个长度为 5 的单词，等等……

mapreduce 最常见的例子是计算语料库中单词出现的次数。假设您有一份互联网副本（我很幸运能够在这种情况下工作），并且您想要一份互联网上每个单词的列表以及它出现的次数。

您解决此问题的方法是标记您拥有的文档（将其分解为单词），并将每个单词传递给映射器。然后，映射器会将单词连同1. 分组阶段将获取所有键（在本例中为单词），并列出 1。然后，reduce 阶段获取一个键（单词）和一个列表（每次该键出现在 Internet 上时的 1 列表），并对列表求和。然后reducer 输出这个词，以及它的计数。当一切都说完后，您将拥有互联网上每个单词的列表，以及它出现的次数。

容易，对吧？如果您曾经读过 mapreduce，那么上面的场景并不是什么新鲜事……它是 mapreduce 的“Hello, World”。因此，这是一个真实世界的用例（Facebook 可能会或可能不会实际执行以下操作，这只是一个示例）：

Facebook 有一个朋友列表（请注意，朋友在 Facebook 上是双向的。如果我是你的朋友，你就是我的）。他们也有大量的磁盘空间，每天处理数亿个请求。他们决定在可能的情况下预先计算计算以减少请求的处理时间。一个常见的处理请求是“你和乔有 230 个共同的朋友”功能。当您访问某人的个人资料时，您会看到您的共同好友列表。该列表不会经常更改，因此每次访问配置文件时都重新计算它会很浪费（当然您可以使用不错的缓存策略，但是我将无法继续为这个问题写关于 mapreduce 的文章）。我们将使用 mapreduce 以便我们可以计算每个人 s 共同的朋友每天一次并存储这些结果。稍后它只是一个快速查找。我们有很多磁盘，很便宜。

假设好友存储为 Person->[List of Friends]，那么我们的好友列表为：

A -> B C D
B -> A C D E
C -> A B D E
D -> A B C E
E -> B C D

每行都是映射器的参数。对于好友列表中的每个好友，映射器都会输出一个键值对。关键将是与此人一起的朋友。该值将是朋友列表。密钥将被排序，以便朋友按顺序排列，导致所有朋友对都去同一个减速器。这很难用文字来解释，所以让我们这样做，看看你是否能看到模式。在所有映射器运行完毕后，您将拥有如下列表：

For map(A -> B C D) :

(A B) -> B C D
(A C) -> B C D
(A D) -> B C D

For map(B -> A C D E) : (Note that A comes before B in the key)

(A B) -> A C D E
(B C) -> A C D E
(B D) -> A C D E
(B E) -> A C D E
For map(C -> A B D E) :

(A C) -> A B D E
(B C) -> A B D E
(C D) -> A B D E
(C E) -> A B D E
For map(D -> A B C E) :

(A D) -> A B C E
(B D) -> A B C E
(C D) -> A B C E
(D E) -> A B C E
And finally for map(E -> B C D):

(B E) -> B C D
(C E) -> B C D
(D E) -> B C D
Before we send these key-value pairs to the reducers, we group them by their keys and get:

(A B) -> (A C D E) (B C D)
(A C) -> (A B D E) (B C D)
(A D) -> (A B C E) (B C D)
(B C) -> (A B D E) (A C D E)
(B D) -> (A B C E) (A C D E)
(B E) -> (A C D E) (B C D)
(C D) -> (A B C E) (A B D E)
(C E) -> (A B D E) (B C D)
(D E) -> (A B C E) (B C D)

每行将作为参数传递给减速器。reduce 函数将简单地与值列表相交，并输出与相交结果相同的键。例如，reduce((AB) -> (ACDE) (BCD)) 将输出 (AB) : (CD) 并表示朋友 A 和 B 有 C 和 D 作为共同朋友。

减少后的结果是：

(A B) -> (C D)
(A C) -> (B D)
(A D) -> (B C)
(B C) -> (A D E)
(B D) -> (A C E)
(B E) -> (C D)
(C D) -> (A B E)
(C E) -> (B D)
(D E) -> (B C)

现在当 D 访问 B 的个人资料时，我们可以快速查找(B D)并看到他们有三个共同的朋友，(A C E)。

于 2012-09-11T18:37:24.077 回答
27

类 Hadoop 的 MapReduce 实现的最佳示例之一。

请记住，尽管它们仅限于 MapReduce 思想的基于键值的实现（因此它们的适用性受到限制）。

于 2012-09-11T20:57:16.243 回答
5

您可以在 MapReduce 中执行的一组熟悉的操作是一组正常的 SQL 操作：SELECT、SELECT WHERE、GROUP BY 等。

另一个很好的例子是矩阵乘法，你传递一行 M 和整个向量 x 并计算 M * x 的一个元素。

于 2012-09-11T18:36:51.690 回答
3

我不时向人们展示 MR 概念。我发现人们熟悉的处理任务，然后将它们映射到 MR 范例。

通常我会做两件事：

  1. 分组依据/聚合。在这里，洗牌阶段的优势是显而易见的。洗牌也是分布式排序的解释+分布式排序算法的解释也有帮助。

  2. 连接两个表。使用 DB 的人熟悉这个概念及其可伸缩性问题。展示如何在 MR 中完成。

于 2012-09-12T09:49:12.220 回答