1700507521
图11-11 Hadoop中各map/reduce分治执行任务
1700507522
1700507523
不仅如此，程序员熟悉的OOP技术（Object Oriented Programming，面向对象编程）和过去使用的POP技术（Procedure Oriented Programming，面向过程编程）的设计思路也有分治思想的深刻烙印。
1700507524
1700507525
在一个类的设计中，除了在必要的对外服务功能部分用public的方式暴露出来以外，其他的内容都在内部用protected方式或private方式进行保护（如表11-5所示）。
1700507526
1700507527
表11-5 面向对象的不同使用权限
1700507528
1700507529
1700507530
1700507531
1700507532
而且，面向对象的设计几乎将一切调用细节全部推给了编译器和虚拟机软件，把返回功能结果的要求推给了类和方法的提供者，OOP语言仅关心当前编程人处理流程中最为核心的部分，而当前编程人也以同样的方式服务于其他人，颇有点“人人为我，我为人人”的社会大分工互利共赢的意思。
1700507533
1700507534
分治法的思路在处理很多大而复杂的问题时都可以使用，而且形式灵活，只要使用得当，确实能够“化不可能为可能”。不过要注意，这种问题的模型必须是一种可分治的模型，如果问题设计本身无法通过多个局部获解而使得全局获解，分治法的思路就行不通了。
1700507535
1700507536
在分布式环境中使用全局去重的命令时就无法应用分治思想。例如，在包含N个节点的Hive或者Spark-SQL环境中使用DISTINCT进行全局去重，要实现这个功能有两种方法。
1700507537
1700507538
第一种方法是把DISTINCT命令发送到所有节点。这个求解的指令发送到任何一个节点之后，做的都是同样的事情，每个节点要先拿谓词“where”在本地进行过滤。在过滤后的集合中，把每一条数据Xi拿到其他N-1个节点进行询问，如果Xi出现在其他节点，就需要通过一种协商机制要求对方节点在输出结果集的时候对Xi做不输出处理。某节点为其他节点询问到的Xi，如果已经询问其他节点并决定做输出处理时，应通知对方做不输出处理。这种方式可以保证在全局范围内以声明的时间戳为准决定最后在全局输出哪些Xi记录。这种相互之间的询问和应答会引发节点间大量的信息传递，并诱发网络风暴（如图11-12所示），导致全网瘫痪。
1700507539
1700507540
1700507541
1700507542
1700507543
图11-12 网络风暴
1700507544
1700507545
如果不这么做，就只能使用第二种方法了。把所有数据（Xi）都传送到一个节点上，在这个节点上做哈希排重（单机无序输入排重效率最高的方式）。可以看到，当局部子问题严重依赖其他局部子问题的时候，分治法就不适用了。分治法只适用于那些可以简化为使用高内聚、低耦合方式解决的问题。
1700507546
1700507547
1700507548
1700507549
1700507550
数据科学家养成手册 [:1700503582]
1700507551
数据科学家养成手册 11.5 回溯法——能省则省
1700507552
1700507553
回溯法（探索与回溯法）是一种选优搜索法，又称“试探法”，有些参考资料上也称其为“剪枝法”。回溯法的核心思路是，按选优条件向前搜索，以达到目标。当搜索到某一步时，发现原先的选择不优或达不到目标，就退回一步重新选择。这种走不通就退回再走的方法称为“回溯法”，而满足回溯条件的状态点称为“回溯点”。
1700507554
1700507555
这种思路的“上一步”实际上是穷举解空间的思路。在对空间进行穷举的过程中，发现按照当前的穷举路径前进，剩下的解都不可能是所求解，在这种情况下，就放弃当前穷举路径下的所有待选解并回退。所以，在绝大多数情况下都只尝试了穷举空间中的一小部分解，而不是全部解。
1700507556
1700507557
例如，写一个算法来模拟走出迷宫的过程。这个算法可以用递归来写，也可以用非递归的遍历方法来写。如图11-13所示是一个20×20的迷宫，在迷宫的每个方格中都有4个方向可以“走”，除了过来的方向（走过的格子），还有3个方向可以“走”。那么，在遍历的过程中，理论上的计算成本为
1700507558
1700507559
1700507560
1700507561
1700507562
图11-13 迷宫问题
1700507563
1700507564
1700507565
1700507566
1700507567
大约是3.5×10190。在这样的情况下，使用穷举法显然会消耗一段我们无法忍受的时长，而且使用分治法的思路也不明确，无法简化成“局部获解而全局获解”的问题。
1700507568
1700507569
但是，我们可以很容易地发现，迷宫中很多方格的4个方向其实并非全部有效：有的是“墙”，过不去；有的是走到某一步会发现，从这一步开始的所有解树叶节点都不用尝试了，这种情况下，会把“树”上的所有子枝全部剪掉，以节省大量的空间和时间成本，所以叫“剪枝法”也是非常形象的（如图11-14所示）。
1700507570