分治的思维方式
算法,其本质是一种思维方式。具体实现是术,思维方式是道。对于分治算法,它对应的数学理论是数学归纳法。在程序的表现中,它 一般会和递归一起使用。
在计算机科学中,分治法是建基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”,就是把一个复杂的问题 分成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。
这是维基百科对分治法的定义。分治法的核心思想如下:
- 找到一个(或多个,下同)比现有问题规模更小的,但本质却一样的问题
- 找到问题的基准值(也就是最小的,不可以再切割的那个条件)
- 把问题依次化解为更小的问题,一直到基准值为止
- 当基准值被解决之后,递归函数一路向上返回
- 合并递归函数返回的结果
比如在Haskell中,列表求和函数可以如下实现:
mySum :: [Int] -> Int -- 函数签名
mySum [] = 0 -- 基准情况,空列表,不能再切分为子问题了
mySum (x:xs) = x + mySum xs -- 分治
我们可以把一个列表看作是一个元素和一个列表拼在一起,比如有一个列表为 [1, 2, 3]
,我们可以看成是 1 和 [2, 3]
拼在一起,
我们发现,这样可以把列表求和的问题分成一个相似的子问题,那就是1和 [2, 3]
的和,同理,[2, 3]
还可以继续细分为 2
和 [3]
的和,而 [3]
可以分为 3 和 []
的和,那么 []
就是基准情况,空列表的和是多少呢?显然是0,因此我们开始把
展开的递归层层向上收缩,得出最终的结果为6。
那有可能有人想问,为啥要这样做呢?为啥不直接迭代过去累加呢?这是两种不同的思维方式,关于分治,我们再来看很熟悉的一个 排序算法:合并排序。
合并排序
使用Python实现合并排序如下:
def merge(array):
if len(array) == 1:
return array
mid = len(array) >> 1
left = merge(array[:mid])
right = merge(array[mid:])
result = []
i, j = 0, 0
while i < len(left) and j < len(right):
if left[i] > right[j]:
result.append(right[j])
j += 1
else:
result.append(left[i])
i += 1
result.extend(left[i:])
result.extend(right[j:])
return result
同样,基准情况是当数组只有一个值的时候,这个时候原样返回;而当数组内有多个值的时候,把数组一分为二,递归处理,然后将 递归的返回值进行合并,合并方法是,将左右两边同时遍历,每次都选择最小的那个;最后将没有遍历完的那一部分拼上去。
那么为什么可以把递归的返回值直接进行合并呢?这里就涉及到分治算法一个比较难理解的地方,突破了这一点,也就掌握了分治算法。 那就是递归信任。也就是我们的目标是,将左右半部分排序的操作分别放到递归函数里去做,当递归函数返回的时候,他们必然是有序 的,为什么呢?因为所有的递归函数都执行了合并的那一部分操作。可能有些绕,但是仔细去理解一下,就会发现不难。
我们继续扩展,除了合并排序,还有什么地方是可以用分治法去解决的呢?
把大批量的数据分为n次执行
日常业务实现中,也有分治法的影子。比如,在一个数据库查询中,使用IN操作,而IN后面接了10240个值,这个时候如果直接丢到SQL 里查询,那必然是要出问题的,我们可以分为10个批次,每批次1024个值去查询,然后把他们的结果进行合并处理。
这个场景是不是很熟悉呢?再比如,线程池,进程池处理多任务的时候,如果一次发起1024个线程执行任务,那系统可能会吃不消,
这个时候我们会选择一个合适大小的线程池,让他们慢慢执行,最后我们再统一处理结果(或者忽略结果),这样的例子很多,比如
Python中的ThreadPoolExecutor,Go里的 sync.WaitGroup
,Java的线程池等等。
递归的数据结构和问题
还有什么数据结构我们可以用递归的方式(因此也就可以用分治来解决)来看待呢?
- 树
- 链表
- 汉诺塔问题
这些我们都可以把它们拆城一个值和一个相同性质的子问题来看待,因此也就可以使用分治的思维方式去解决他们。
参考资料:
- https://zh.wikipedia.org/wiki/%E5%88%86%E6%B2%BB%E6%B3%95
- https://book.douban.com/subject/4049957
- https://jiajunhuang.com/articles/2015_09_05-thinking_recursively.rst.html
更多文章
- socks5 协议详解
- zerotier简明教程
- 搞定面试中的系统设计题
- 用peewee代替SQLAlchemy
- frp 源码阅读与分析(一):流程和概念
- Golang(Go语言)中实现典型的fork调用
- DNSCrypt简明教程
- 一个Gunicorn worker数量引发的血案
- Golang validator使用教程
- Docker组件介绍(一):runc和containerd
- Docker组件介绍(二):shim, docker-init和docker-proxy
- 使用Go语言实现一个异步任务框架
- 协程(coroutine)简介 - 什么是协程?
- SQLAlchemy简明教程
- Go Module 简明教程