functional-programming - MapReduce与函数式编程中map-reduce组合的区别

Question

我在 http://en.wikipedia.org/wiki/MapReduce 阅读了 mapreduce ，了解了如何在许多“文档”中获取“单词”计数的示例。但是我不明白以下行:

Thus the MapReduce framework transforms a list of (key, value) pairs into a list of values. This behavior is different from the functional programming map and reduce combination, which accepts a list of arbitrary values and returns one single value that combines all the values returned by map.

有人可以再详细说明一下区别吗(MapReduce 框架 VS map 和 reduce 组合)？特别是，reduce 函数式编程有什么作用？

非常感谢。

Answer 1

主要区别在于 MapReduce 显然是可专利的。 (忍不住了，抱歉……)

更严肃地说，我记得 MapReduce 论文描述了一种以大规模并行方式执行计算的方法。这种方法建立在多年前众所周知的 map/reduce 结构的基础上，但超出了诸如分发数据等问题的范围。此外，对所使用的函数所操作和返回的数据结构施加了一些限制。 map喜欢和reduce - 类似于计算的部分(关于键/值对列表中的数据的事情)，所以你可以说 MapReduce 是一个大规模并行友好的 专业的map & reduce组合。

至于维基百科对函数式编程中映射函数的评论map/reduce构造为每个输入生成一个值...好吧，当然可以，但是这里 对所述值的类型没有任何限制 .特别是，它可能是一个复杂的数据结构，例如可能是您将再次应用 map 的事物列表。/reduce转型。回到“计算单词”的例子，你很可能有一个函数，它可以为文本的给定部分生成一个数据结构，将单词映射到出现次数，map超过您的文档(或大块文档，视情况而定)和 reduce结果。

事实上，这正是 this article 中发生的事情。菲尔·哈格尔伯格。这是在 Clojure 中使用 map 实现的类似 MapReduce 单词计数的计算的有趣且极其简短的示例。和等效于 reduce 的东西((apply + (merge-with ...)) 位 -- merge-with 是根据 clojure.core 中的 reduce 实现的)。这与 Wikipedia 示例之间的唯一区别在于，被计数的对象是 URL 而不是任意单词——除此之外，您已经使用 map 实现了计数单词算法。和 reduce ，MapReduce 风格，就在那里。它可能不完全符合作为 MapReduce 实例的条件的原因是不涉及复杂的工作负载分布。这一切都发生在一个盒子上……尽管是在盒子提供的所有 CPU 上。

深度治疗reduce函数 -- 也称为 fold -- 见格雷厄姆赫顿的 A tutorial on the universality and expressiveness of fold .它是基于 Haskell 的，但即使您不了解该语言，也应该是可读的，只要您愿意随时查找一两个 Haskell 东西...像 ++ 之类的东西= 列表连接，没有深层次的 Haskell 魔法。