什么是Map/Reduce？

我听说过很多关于map/reduce的内容,特别是在谷歌大规模并行计算系统的背景下.究竟是什么？

1> coobird..：

---

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

MapReduce是一种编程模型,是处理和生成大型数据集的相关实现.用户指定处理键/值对以生成一组中间键/值对的映射函数,以及合并与相同中间键关联的所有中间值的reduce函数.

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

因为它是从基于功能编程模型中,map和reduce步骤各不具有(从每个子部分的状态和结果的任何副作用map过程不依赖于另一个),因此数据集被映射的,并且减少了可以各自分开在多个处理节点上.

Joel的编程语言能做到吗？这篇文章讨论了如何理解函数式编程在Google中提出MapReduce的必要性,MapReduce为其搜索引擎提供支持.如果您不熟悉函数式编程以及它如何允许可伸缩代码,那么这是一个非常好的阅读.

另见:维基百科:MapReduce

相关问题:请简单解释mapreduce

---

出色地解释道.对于Software Monkey来说,一旦你理解了M/R就可以很容易地实现它,并且不仅限于这里给出的例子.有几种方法可以解决它,人们会认为它是收藏家和漏斗.

2> Srikanth..：

---

MapReduce解释.

它解释得比我能做得更好.有帮助吗？

3> Daniel Earwi..：

---

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

这就是map可能用C#编写的(它被调用Select并且在标准库中):

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

因为你是一个Java家伙,Joel Spolsky喜欢告诉GROSSLY UNFAIR LIES关于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,将两个项转换为单个值.它可以通过给出前两个项目来实现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);

为什么这个"酷"？将更大的计算分解成更小的部分的简单方法,因此它们可以以不同的方式重新组合在一起,总是很酷.Google应用这种想法的方式是并行化,因为map和reduce都可以通过多台计算机共享.

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

---

总的来说,一个好的答案,值得+1; 虽然不喜欢Java上的jab - 但是自从从C迁移到Java之后我就错过了函数值,并且同意他们在Java中的可用性早就应该了.