分治的思维方式

算法,其本质是一种思维方式。具体实现是术,思维方式是道。对于分治算法,它对应的数学理论是数学归纳法。在程序的表现中,它 一般会和递归一起使用。

在计算机科学中,分治法是建基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”,就是把一个复杂的问题 分成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。

这是维基百科对分治法的定义。分治法的核心思想如下:

  • 找到一个(或多个,下同)比现有问题规模更小的,但本质却一样的问题
  • 找到问题的基准值(也就是最小的,不可以再切割的那个条件)
  • 把问题依次化解为更小的问题,一直到基准值为止
  • 当基准值被解决之后,递归函数一路向上返回
  • 合并递归函数返回的结果

比如在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的线程池等等。

递归的数据结构和问题

还有什么数据结构我们可以用递归的方式(因此也就可以用分治来解决)来看待呢?

  • 链表
  • 汉诺塔问题

这些我们都可以把它们拆城一个值和一个相同性质的子问题来看待,因此也就可以使用分治的思维方式去解决他们。


参考资料:


更多文章
  • Python 的继承
  • Python的yield关键字有什么作用?
  • 借助coroutine用同步的语法写异步
  • Python3函数参数中的星号
  • 使用Git Hooks
  • Token Bucket 算法
  • nginx配置笔记
  • 阅读Flask源码
  • 尤克里里
  • 学习使用Bootstrap4的栅格系统
  • 利用Github的WebHook完成自动部署
  • 使用Tornado和rst来写博客
  • Haskell do notation
  • foldl 和 foldr 的变换
  • Haskell TypeClass 笔记