1700507500
数据科学家养成手册 [:1700503581]
1700507501
数据科学家养成手册 11.4 分治法——化繁为简
1700507502
1700507503
分治法的应用在生产中更为普及，而且这种思路可以说同样是浑然天成——也是人类自己处理复杂问题的逻辑。人类在碰到一个庞大而复杂的问题时同样会想：这个问题可不可以分解成多个简单一些的小问题？每个问题获解了，整体就获解了（如图11-10所示）。
1700507504
1700507505
1700507506
1700507507
1700507508
图11-10 问题分解
1700507509
1700507510
这种思维方式的一个好处是可以降低求解难度。在日常生活中我们知道，处理1个对象事物和处理10个对象事物的成本不是10倍的关系。举个现实生活中的例子，一个人自己做饭吃，翻翻电冰箱，有些鸡蛋和西红柿，炒个鸡蛋西红柿凑合凑合就行了；而如果10个人一起聚餐，即使有足够的鸡蛋和西红柿，也不能炒10倍量的鸡蛋西红柿大家一起凑合，要采买的蔬菜和肉类多了，准备工作复杂了，花费的时间成本也就高了。这里的成本关系不是线性的，这种方式对一个人来说处理的成本太高了。怎么办？最好的办法就是事先商量好，每个参加聚餐的人都带一个做好的菜——人数越多，效果越明显。这种方式的处理结果就是每个人的时间成本略有增加，但是不会把其中一个人累死——开个玩笑。
1700507511
1700507512
在经典的单机应用场景中，也有一些算法应用了分治法。例如，二分查找、多路归并排序、大整数乘法等，都是典型的把复杂问题简化为局部与局部之间的简单问题获解进而得到全局解的思路。
1700507513
1700507514
这种思路在其他更宏观的场景中一样可以见到。例如，在一个1PB的数据集中，要查找其中的最大值。这种数据在一台计算机上怎么存储都是个问题，即使能存储，也要一部分一部分地把数据提取到内存中进行排序，找出最大值，然后将每次迭代的最大值保留，与下一次迭代的最大值相比较，保留两者中较大的值，直到遍历1PB的数据为止。
1700507515
1700507516
这种办法几乎只是理论上可行，因为它所消耗的时间成本极其高昂。而在大型的Hadoop集群中，可以在几百甚至几千个节点上分别查找，每个节点只要找到本节点上的最大值，最后找出这些值中的最大值，就能获解。这种任务的加速几乎是随着集群规模的增加而线性加快的（如图11-11所示）。对海量数据处理来说，Hadoop框架的解决方案本质上就是分治法的应用。
1700507517
1700507518
1700507519
1700507520
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