什么是map/reduce?

从谷歌的摘要 MapReduce 研究出版物页面:

MapReduce是一个编程模型, 的关联实现 处理和生成大数据 集合。用户指定映射函数 将密钥/值对处理为 生成一组中间文件 键/值对,以及一个reduce函数 合并所有中间值 与同一中间物关联 关键。

MapReduce的优点是可以在多个处理节点(多个服务器)上并行执行处理,因此它是一个可以很好地扩展的系统。

因为它是基于 functional programming 模型 map 和 reduce 每个步骤都没有任何副作用(状态和结果来自 地图 进程不依赖于另一个进程),因此被映射和缩减的数据集可以在多个处理节点上分离。

乔尔 Can Your Programming Language Do This? 这篇文章讨论了如何理解函数式编程对于谷歌开发支持其搜索引擎的MapReduce至关重要。如果您不熟悉函数式编程以及它如何允许可伸缩代码,那么这是一个非常好的读物。

参见: Wikipedia: MapReduce

相关问题: Please explain mapreduce simply

map是一个函数,它将另一个函数应用于列表中的所有项,以生成另一个包含所有返回值的列表。(另一种说法是“将f应用到x”是“调用f,传递x”。所以有时候说“应用”而不是“调用”听起来更好。)

这就是地图可能是用C(它叫 Select 在标准库中):

public static IEnumerable<R> Select<T, R>(this IEnumerable<T> list, Func<T, R> func)
{
    foreach (T item in list)
        yield return func(item);
}

因为你是一个Java的家伙,Joel Spolsky喜欢对蹩脚的Java是多么的不公平的谎言(实际上,他不是撒谎,它是蹩脚的,但是我想赢你),这是我对Java版本的粗略尝试(我没有Java编译器,我模糊地记得Java版本1.1!):

// represents a function that takes one arg and returns a result
public interface IFunctor
{
    object invoke(object arg);
}

public static object[] map(object[] list, IFunctor func)
{
    object[] returnValues = new object[list.length];

    for (int n = 0; n < list.length; n++)
        returnValues[n] = func.invoke(list[n]);

    return returnValues;
}

我相信这可以在一百万方面得到改善。但这是基本的想法。

reduce是一个将列表中的所有项转换为单个值的函数。为此,需要给它另一个函数 func 将两个项目转换为一个值。把前两项交给 芬克 . 然后是第三项的结果。然后是第四项的结果,以此类推,直到所有的项都消失了,我们只剩下一个值。

在c中,称为reduce Aggregate 在标准库中。我将直接跳转到Java版本:

// represents a function that takes two args and returns a result
public interface IBinaryFunctor
{
    object invoke(object arg1, object arg2);
}

public static object reduce(object[] list, IBinaryFunctor func)
{
    if (list.length == 0)
        return null; // or throw something?

    if (list.length == 1)
        return list[0]; // just return the only item

    object returnValue = func.invoke(list[0], list[1]);

    for (int n = 1; n < list.length; n++)
        returnValue = func.invoke(returnValue, list[n]);

    return returnValue;
}

这些Java版本需要添加泛型,但我不知道如何在Java中实现。但是您应该能够通过匿名的内部类来提供函数:

string[] names = getLotsOfNames();

string commaSeparatedNames = (string)reduce(names, 
   new IBinaryFunctor {
       public object invoke(object arg1, object arg2)
           { return ((string)arg1) + ", " + ((string)arg2); }
   }

希望仿制药可以摆脱这些铸造。c中的类型安全等价物是:

string commaSeparatedNames = names.Aggregate((a, b) => a + ", " + b);

为什么这个“酷”?将较大的计算拆分为较小的部分,以便以不同的方式将它们重新组合在一起的简单方法总是很酷的。谷歌应用这一理念的方式是并行化,因为地图和reduce都可以在多台计算机上共享。

但关键的要求不是您的语言可以将函数视为值。任何OO语言都可以做到。并行化的实际要求是 芬克 传递给map和reduce的函数不能使用或更新任何状态。它们必须返回仅依赖于传递给它们的参数的值。否则,当您试图并行运行整个事件时,结果将完全搞砸。

MapReduce Explained .

它比我能解释的更好。有帮助吗?

在对冗长的华夫饼或很短的模糊的博客文章感到沮丧之后,我最终发现了这一点。 very good rigorous concise paper .

然后我继续进行,并通过转换成scala使其更加简洁,在这里我提供了一个最简单的例子,用户只需指定 map 和 reduce 部分应用程序。严格来说,在hadoop/spark中,使用了一个更复杂的编程模型,要求用户明确地指定这里概述的4个函数: http://en.wikipedia.org/wiki/MapReduce#Dataflow

import scalaz.syntax.id._

trait MapReduceModel {
  type MultiSet[T] = Iterable[T]

  // `map` must be a pure function
  def mapPhase[K1, K2, V1, V2](map: ((K1, V1)) => MultiSet[(K2, V2)])
                              (data: MultiSet[(K1, V1)]): MultiSet[(K2, V2)] = 
    data.flatMap(map)

  def shufflePhase[K2, V2](mappedData: MultiSet[(K2, V2)]): Map[K2, MultiSet[V2]] =
    mappedData.groupBy(_._1).mapValues(_.map(_._2))

  // `reduce` must be a monoid
  def reducePhase[K2, V2, V3](reduce: ((K2, MultiSet[V2])) => MultiSet[(K2, V3)])
                             (shuffledData: Map[K2, MultiSet[V2]]): MultiSet[V3] =
    shuffledData.flatMap(reduce).map(_._2)

  def mapReduce[K1, K2, V1, V2, V3](data: MultiSet[(K1, V1)])
                                   (map: ((K1, V1)) => MultiSet[(K2, V2)])
                                   (reduce: ((K2, MultiSet[V2])) => MultiSet[(K2, V3)]): MultiSet[V3] =
    mapPhase(map)(data) |> shufflePhase |> reducePhase(reduce)
}

// Kinda how MapReduce works in Hadoop and Spark except `.par` would ensure 1 element gets a process/thread on a cluster
// Furthermore, the splitting here won't enforce any kind of balance and is quite unnecessary anyway as one would expect
// it to already be splitted on HDFS - i.e. the filename would constitute K1
// The shuffle phase will also be parallelized, and use the same partition as the map phase.  
abstract class ParMapReduce(mapParNum: Int, reduceParNum: Int) extends MapReduceModel {
  def split[T](splitNum: Int)(data: MultiSet[T]): Set[MultiSet[T]]

  override def mapPhase[K1, K2, V1, V2](map: ((K1, V1)) => MultiSet[(K2, V2)])
                                       (data: MultiSet[(K1, V1)]): MultiSet[(K2, V2)] = {
    val groupedByKey = data.groupBy(_._1).map(_._2)
    groupedByKey.flatMap(split(mapParNum / groupedByKey.size + 1))
    .par.flatMap(_.map(map)).flatten.toList
  }

  override def reducePhase[K2, V2, V3](reduce: ((K2, MultiSet[V2])) => MultiSet[(K2, V3)])
                             (shuffledData: Map[K2, MultiSet[V2]]): MultiSet[V3] =
    shuffledData.map(g => split(reduceParNum / shuffledData.size + 1)(g._2).map((g._1, _)))
    .par.flatMap(_.map(reduce))
    .flatten.map(_._2).toList
}

MapReduce和/或SQL:

http://www.data-miners.com/blog/2008/01/mapreduce-and-sql-aggregations.html

http://www.data-miners.com/blog/

对MapReduce的批评

http://www.databasecolumn.com/2008/01/mapreduce-a-major-step-back.html

http://www.databasecolumn.com/2008/01/mapreduce-continued.html

map是可以应用于数组的本地JS方法。它创建了一个新的数组,这是映射到原始数组中每个元素的函数的结果。因此,如果您映射了一个函数(元素)返回元素*2;,它将返回一个新的数组,每个元素都加倍。原始数组将保持不变。

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/map

reduce是一个本地JS方法,也可以应用于数组。它将一个函数应用于一个数组,并有一个称为累加器的初始输出值。它循环遍历数组中的每个元素,应用一个函数,并将它们减少到一个值(以累加器开始)。它很有用,因为你可以有任何你想要的输出,你只需要从那类累加器开始。所以,如果我想把某个东西简化成一个对象,我将从一个累加器开始。

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/Reduce?v=a