分治思维.md · 隔壁老李/编程思维

分治与抽象一样，都是人类进化里程中形成的伟大智慧，也是我们解决复杂问题的不二选择。人的思维要从一个字节大幅跨越到几百兆字节，也就是9个数量级（现阶段，后面还要再加N个零）。如此，复杂的问题域，如果不进行分治，是远远超出人类智力范围的。

分治的价值在于，我们不应该试着在赋一时间把整个问题都塞进自己的大脑，而应该试着以某种方式去组织问题，以便在一个时刻专注于一个特定的部分。这样做的目的是尽量降低思考问题的复杂度。
### 1. 分治算法
分：就是递归地将原问题分解成小问题；
治：在解决各个小问题后，合并这些小问题的解，从而得到整个问题的解。

分治法解题的步骤：
（1）分解： 将要解决的问题划分成若干规模较小的同类问题
（2）求解：当子问题划分得足够小时，用较简单的方法解决。
（3）合并：按原问题的要求，将子问题的解逐层合并，构成原问题的解。

#### 1.1 用到分治的排序算法的
+ 归并排序
+ 二分搜索
+ k选取问题

### 2. 函数分解
函数过大是典型的代码“坏味道”， 意味着这个函数可能承载着过多的职责，我们有必要“分治”一下，将大函数分解成多个短小、易读、易维护的小函数。

分解函数：
（1）函数长短是职责单一的充分不必要条件，也就是长函数往往意味着职责不单一，但是短函数也不一定意味着职责单一。
（2）在使用组合函数模式时，要注意抽象层次一致性原， 不同抽象层次的内容放在一起会给人凌乱、逻辑不协调的感觉

### 3. 写两次代码
我们不仅要写实现功能的代码，还要写容易理解的好代码。“写出好代码”除了需要好的技艺之外，还要有好的方法，优雅的代码很少是一次形成的，大部分情况要经过两次创造国第一遍实现，第二遍重构优化。

#### 第一遍实现功能
不要试图一次就写出“完美 的”代码，这样只会拖慢我们的节奏。就像写文章，第一遍可以写得粗糙一点，把大概意思写出来，然后再仔细打磨，斟酌推敲，直到达到理想的样子。

写代码也是如此，第一遍以实现功能为主， 可以允许一家的冗长和复杂，比如有过多的缩进和嵌套循环，有过长的参数列表，名称可以随意取，还会有部分重复代码。第一遍主要是为了理清逻辑。第二遍重构优化做好准备。

#### 第二遍重构优化
如果只是止步于功能实现，那么代码最多只是一个半成品，而实际情况是我们的代码库有太多这样的半成品，导致系统的复杂席不断攀升，越来越难维护。因此，我们需要有第二次创造——重构优化，即在第一遍实现功能的基础上，看一看是否可以做得更好：命名合理吗？职责单一吗？满足OCP（开闭原则）吗？函数是否过长？抽象是否合理？

第二次创造通常要第一次创造更费精力，更耗时间，所以很少有人愿意去做第二遍的事情。比如需要你的回答等于几，你凭直觉就知道是4,但是把问题换成17x519，你可能都懒得去算，在心里想着没事费这劲干嘛？这也是丹尼尔卡尼曼在《思考快与慢》说的系统一（感性）与系统二（理性）。运用系统十会耗费能量，而人类是从贫瘠的远古时代进化而来的，为了保存能量，一般默认是使用系统一思考，不到万不得已，是不会启动系统二的。
因此，最好的优化肯定不是等系统上级后再去做，因为这样往往就待于“再也不会去做”。优化工作本应该是我们编码工作的一部分，折成两步，主要对编码效率的考量。

### 4. 分冶模式
很多设计模型者用到了分治思想，比如职责链、装饰者、组合模式；我们不需要把处理一件事需要的所有职责都放在一个地方，而是放在多个地方。
这样不仅能增加可扩展性，也使得单一职责更加明确。更容易维护。

### 5. 分层设计
分层设计是架构体系设计中最常见和和重要一种一结构。分层设计最大的好处是分离关注，这样我们就可以通过分层隔离简化一个复杂的问题，让每一层只对上一层负责，从而使每一层的职责变得相对简单。

#### 5.1 分层网络模型
网络通信是互联网最重要的基础实施之一，它是一个很复杂的过程，包括TCP协议———— 在不可靠的网络上出现状况要怎么办，IP协议————把数据包传给谁。需要处理的事情有很多，我们可不可以在一个层次中都处理掉》当然是可以的，但显然不科学。因此，ISO制定了七层网络模型，每一层只处理一件事情，低层为上层提供服务，直到应用层把HTTP和FTP等方便理解和使用的协议暴露给用户。

但是，我们实际在Internet中使用的并不是七层模型，而是TCP/IP四层模型，因为七层模型过于理想化，过多的分层反而降低了效率，让问题变得更复杂。这里就涉及到加一个问题：分层是不是越多越好？ 当然不是，分层有很多好处，但也有代价。在处理复杂问题时，不能不进行分层，但只分有必要的层。

#### 5.2 分层架构
分层架构的目的是通过分离关注点来降低系统的复杂度，同时满足单一职责、高内聚、低耦合、提高可复用性的降低维护成本，也是一种典型的分治思想。

在分层架构中，分层的使用可以进行严格地限制，分层的使用可以进行严格地限制———— 分层只知道直接的下层；或者可以宽松一些————分层可以访问它之下的任何分层。

martin fowler （《重构---改善既有代码的设计》作者） 认为 使用第二种方式会更好，因为它避免了在中间分层创建代码方法（或者创建代理类），也避免成千层面的反模式。

### 6. 横切和坚切
随着互联网的发展，用户流量呈指数型增长，单体应用已经不能适应发展的需要，分布式架构正在变得越来越重要。如果你经常参加一些技术峰值，可以看到这样的分享；一个小企业人从一台应用服务器、一个数据库慢慢壮大，发展成独角兽公司，其架构也随之演变成一个大型分布式系统。

这不是偶然，而是企业架构演化的必然结果，因为只有分治才能应对高并发，实现水平扩展。

以分布式数据库为例，我们把原来放在一个数据库中的几千亿数据通过、坚切、横切（水平拆分、垂直拆分），切分成相对较小的几个或几十个小数据库，以便满足性能和可用性的要求。所谓坚切，就是按照领域将单体数据库拆分成多个数据库，比如，原来的电商数据都是放在一个库中，我们可以按照领域拆分成商品库、会员库、交易库等。
（不相同的数据表分布在不同的数据库中）

横切是通过一种数据路由算法对数据进行分片，从而减少一个数据库的中的数据量，比如，我们要将会员的交易数据切分成10个库，可以用userId 对10进行取模。（结构相同的数据表分布在不同的数据库中）

### 总结
软件产业正在变得越来越庞大和复杂，互联冈正在变得越来越激进。我们在同一时间能够关注和处理的信息有限，所以学会分治思想，很重要。学会如何对复杂问题进行分层和拆解，是我们解决复杂问题的第一步。

隔壁老李/编程思维

简介

发行版

贡献者

近期动态

隔壁老李/编程思维 .gitee-modal { width: 500px !important; }

简介

发行版

贡献者

近期动态

搜索帮助

隔壁老李/编程思维