毕业论文 构思 Map/Reduce

又要毕业了，毕业论文难搞。

研究下Map/reduce 看能有所利用不。

版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明
http://dreamhead.blogbus.com/logs/2617482.html

MapReduce是Google的一项重要技术，它是一个编程模型，用以进行大数据量的计算。对于大数据量的计算，通常采用的处理手法就是并行计算。至少现阶段而言，对许多开发人员来说，并行计算还是一个比较遥远的东西。MapReduce就是一种简化并行计算的编程模型，它让那些没有多少并行计算经验的开发人员也可以开发并行应用。在我看来，这也就是MapReduce的价值所在，通过简化编程模型，降低了开发并行应用的入门门槛。相对于现在普通的开发而言，并行计算需要更多的专业知识，有了MapReduce，并行计算就可以得到更广泛的应用。

MapReduce的名字源于这个模型中的两项核心操作：Map和Reduce。也许熟悉Functional Programming的人见到这两个词会倍感亲切。简单的说来，Map是把一组数据一对一的映射为另外的一组数据，其映射的规则由一个函数来指定，比如对[1, 2, 3, 4]进行乘2的映射就变成了[2, 4, 6, 8]。Reduce是对一组数据进行归约，这个归约的规则由一个函数指定，比如对[1, 2, 3, 4]进行求和的归约得到结果是10，而对它进行求积的归约结果是24。

Map操作是独立的对每个元素进行操作，在FP中，操作是没有副作用的，换句话说，Map操作将产生一组全新的数据，而原来的数据保持不变。因此，它是高度并行的。Reduce操作虽然不如Map操作并行性那么好，但是它总会得到一个相对简单的结果，大规模运算也相对独立，因此也是比较适合并行的。

无论是Map还是Reduce都是以另外的函数作为参数，在FP中，这样的函数被称为高阶函数（high-order function）。正是因为它们可以同其它函数相结合，所以，我们只要把Map和Reduce这两个高阶函数进行并行化处理，而无需面面俱到的把所有的函数全部考虑到。这样便形成了一个以Map和Reduce为基础的框架，具体应用相关代码写在用户代码中，之后与MapReduce结合获得并行处理的能力。当然，这么做的前提是按照这个框架的要求，把计算归结为Map和Reduce操作。为什么是Map和Reduce？从前面的内容我们可以看出，在Map过程中，我们将数据并行，也就是将数据分开，而Reduce则把分开的数据合到了一起，换句话说，Map是一个分的过程，Reduce则对应着合，这一分一合便在不知不觉中完成了计算。所以，站在计算的两端来看，与我们通常熟悉的串行计算没有任何差别，所有的复杂性都在中间隐藏了。

所有这些并行化能力的获得都与FP有着密不可分的关系。事实上，不仅仅是MapReduce从FP中获得了灵感，其它一些并行编程模型也走上了同样的道路。FP中有很多的好东西，比如自动内存管理，比如动态类型。在遥远的年代里，因为机器性能的原因，它们无法得到广泛应用，当机器性能不再是瓶颈，这些东西便逐渐复活了。

前面提到过，并行计算对于普通开发人员来说，有一个比较高的门槛。从前我们或许可以不理会并行计算，但是随着Intel开始将多核带入人们的日常生活，并行计算将会变得更加平民化，毕竟谁也不希望自己机器里面的多核只有一个在干活。现在的许多操作系统会把多核视为多处理器，但那也得有多任务才能在CPU处多分得一杯羹。对于服务器端应用来说，拥有多任务的能力是一个正常的现象。但对于很多桌面应用来说，一条道跑到黑的情况比较多见。而且，多任务并非为并行计算专门准备的，所以，控制粒度是很大的。如果需要更细粒度的并行计算，至少从表达能力上来说，多任务就有些麻烦了。

并行计算进入日常开发的难度就在于编程模型，太复杂的东西会被人唾弃的，CORBA在这方面已经是个反面教材了。MapReduce已经为我们演示了一种可以接受的编程模型，接下来，变化还会有，Intel和AMD都在努力。不过，具体的进程得取决于多核CPU占领市场的进度。

===================

附上另外一个人blog上面的片段

计算样本数据中每个词语出现的频率。我的计算步骤就是先分词，然后用hash表处理。要是碰到TB的数据，我的赛扬CPU可是吃不消。那么放在MapReduce下面会是什么样子呢？

    下面是一个伪实现：
第一步：
    map(String key, String value):
    // key: 文档名称
    // value: 文档内容
    for each word w in value:
        EmitIntermediate(w, "1");
第二步：
    reduce(String key, Iterator values):
    // key: 一个词
    // values: 关于这个词的频率数据
    int result = 0;
        for each v in values:
            result += ParseInt(v);
        Emit(AsString(result));