程序员的算法课（13）-分治法

分治算法一般都比较适合用递归来实现，分治算法的递归实现中，每一层递归都会涉及这样三个操作：

分治算法能解决的问题，一般需要满足下面的这几个条件：

利用分治思想，可以将海量数据集合依据某种方法，划分成为几个小的数据集合，每个小的数据集合单独加载到内存来解决，然后再将小数据集合合并成大数据集合。

大量数据可以存储在 GFS、HDFS这样的可伸缩、高可用、高可靠的分布式文件系统上，当 大量数据被划分成多个小文件的时候，每个文件可以并行加载到多台机器上处理，最后再将结果合并在一起，这样的并行处理速度也会加快很多。

一台机器过于低效，那我们就把任务拆分到多台机器上处理。如果拆分之后的小任务之间互不干扰，独立计算，最后再将结果合并，这不就是分治思想吗？

Map 和 Reduce 其实是函数式编程中的两个语义。Map 和循环 for 类似，只不过它有返回值。比如对一个 List 进行 Map 操作，它就会遍历 List 中的所有元素，然后根据每个元素处理后的结果返回一个新的值。而 Reduce 在函数式编程的作用则是进行数据归并。Reduce 方法需要传入两个参数，然后会递归得对每一个参数执行运算。

Hadoop MapReduce 和函数式中的 Map Reduce 还是比较类似的，只是它是一种编程模型。

我们来看一个 WordCount 的例子，在WordCount中，Hadoop MapReduce 会对输入先进行切分，这一步其实就是分治中分的过程。切分后不同部分就会让不同的机器去执行 Map 操作。而后便是 Shuffle，这一阶段会将不相同的单词加到一起，最后再进行 Reduce 。

所谓 MapReduce 的意思是任何的事情只要都严格遵循 Map Shuffle Reduce 三个阶段就好。其中Shuffle是系统自己提供的而Map和Reduce则用户需要写代码。

当碰到一个任务的时候，我们需要将它解析成 Map Reduce 的处理方式然后编写 Hadoop MapReduce 代码来实现。我看过一个比喻很贴切，Hadoop MapReduce 这个东西这就像是说我们有一把大砍刀，一个锤子。世界上的万事万物都可以先砍几刀再锤几下，就能搞定。至于刀怎么砍，锤子怎么锤，那就算个人的手艺了。

MapReduce 在 Google 最大的应用是做网页的索引。大家都知道 Google 是做搜索引擎起家的，而搜索引擎的基本原理就是索引，就是爬去互联网上的网页，然后对建立 单词->文档 的索引。这样什么搜索关键字，才能找出对应网页。这也是为什么 Google 会以 WordCount 作为 MapReduce 的例子。

既然明白搜索引擎的原理，那应该就明白自 2000 年来互联网爆发的年代，单台机器肯定是不够存储大量的索引的，所以就有了分布式存储，Google 内部用的叫 Gfs，Hadoop Hdfs 其实可以说是山寨 Gfs 来的。而在 Gfs 的基础上，Hadoop MapReduce 的出现也就自然而然了。

这里不得不多说一句，Hadoop 的文件系统 Hadoop Hdfs 才是 Hadoop MapReduce 的基础，因为 Map Reduce 最实质的支撑其实就是这个 Hadoop Hdfs 。没有它， Map Reduce 不过是空中阁楼。你看，在 Hadoop MapReduce 式微的今天，Hadoop Hdfs 还不是活得好好的，Spark 或是 Hive 这些工具也都是以它为基础。不得不说，Hadoop Hdfs 才牛逼啊。

我的微信公众号：架构真经（id：gentoo666），分享Java干货，高并发编程，热门技术教程，微服务及分布式技术，架构设计，区块链技术，人工智能，大数据，Java面试题，以及前沿热门资讯等。每日更新哦！

参考资料：