数学之美1 - 离散篇

柔光的暖阳◎ 2022-02-05 04:47 739阅读 0赞

## 离散篇 ##

[程序员的数学基础课][Link 1]

![006tNc79ly1g24lv8r16kj30u01hcwj0.jpg][]

*  二进制
 *  余数
 *  迭代法
 *  归纳法
 *  递归
 *  排列 & 组合
 *  动态规划
 *  DPS & BFS
 *  图
 *  时间复杂度 & 空间复杂度
 *  反码 & 补码
 *  位操作

--------------------

### 开篇词 | 作为程序员，为什么你应该学好数学？ ###

*  数学它其实是一种思维模式，考验的是一个人**归纳**、**总结**和**抽象**的能力
 *  如果编程语言是血肉，数学的思想和知识就是**灵魂**
 *  只做程序员需要学的数学知识

--------------------

### 导读：程序员应该怎么学数学？ ###

把握数学的工具属性，学习具体方法时先溯因再求果，勤于思考解决相同问题的不同方法，与解决不同问题的相同方法之间的联系与区别。

> 程序员的数学应用地图

![006tNbRwly1fyfwndve71j31400u07l3.jpg][]

--------------------

### 01 | 二进制：不了解计算机的源头，你学什么编程 ###

> 向左移位

使用’<<'表示向左移位

注意数字溢出

> 向右移位

需考虑高位补 1 还是补 0（符号位可能为 1 或 0）

逻辑右移’>>>’

逻辑右移 1 位，左边补 0 即可。

算术右移’>>’

算术右移时保持符号位不变，除符号位之外的右移一位并补符号位 1。补的 1 仍然在符号位之后。

> 位的“或”

逻辑“或”的意思是，参与操作的位中只要有一个位是 1，那么最终结果就是 1，也就是“真”。

使用’|'表示按位的“或”

> 位的“与”

参与操作的位中必须全都是 1，那么最终结果才是 1（真），否则就为 0（假）。

使用’&’ 表示按位“与”

> 位的“异或”

如果参与操作的位相同，那么最终结果就为 0（假），否则为 1（真）。

使用’^’ 表示按位“异或”

“异或”操作的本质其实就是，所有数值和自身进行按位的“异或”操作之后都为 0。作为**判断两个变量是否相等的条件**

> 学习笔记

![006tNc79ly1fywufo61opj30u01a8qoa.jpg][]

--------------------

### 02 | 余数：原来取余操作本身就是个哈希函数 ###

> 例子

*  星期
 *  分页

> 同余定理

简单来说，就是两个整数 a 和 b，如果它们除以正整数 m 得到的余数相等，我们就可以说 a 和 b 对于模 m 同余。

同余定理其实就是用来分类的

> 哈希

将任意长度的输入，通过哈希算法，压缩为某一固定长度的输出。

> 学习笔记

![006tNc79ly1fywvw1gn0aj30u015a7om.jpg][]

--------------------

### 03 | 迭代法：不用编程语言的自带函数，你会如何计算平方根？ ###

> 例子

棋盘放麦粒，每次翻倍，放满64个格子，求总的麦粒数量

> 到底什么是迭代法？

迭代法，简单来说，其实就是不断地用旧的变量值，**递推**计算新的变量值。

> 应用

*  求数值的精确或者近似解。典型的方法包括二分法（Bisection method）和牛顿迭代法（Newton’s method）。
 *  在一定范围内查找目标值。典型的方法包括二分查找。
 *  机器学习算法中的迭代。相关的算法或者模型有很多，比如 K- 均值算法（K-means clustering）、PageRank 的马尔科夫链（Markov chain）、梯度下降法（Gradient descent）等等。迭代法之所以在机器学习中有广泛的应用，是因为很多时候机器学习的过程，就是根据已知的数据和一定的假设，求一个局部最优解。而迭代法可以帮助学习算法逐步搜索，直至发现这种解。

> 计算大于 1 的正整数之平方根

比如说，我们想计算某个给定正整数 n（n>1）的平方根，如果不使用编程语言自带的函数，你会如何来实现呢？

假设有正整数 n，这个平方根一定小于 n 本身，并且大于 1。那么这个问题就转换成，在 1 到 n 之间，找一个数字等于n 的平方根。

我这里采用迭代中常见的二分法。每次查看区间内的中间值，检验它是否符合标准。

class Solution1(object):
        def mySqrt(self, x):
            """ 计算大于 1 的正整数之平方根 :type x: int :rtype: int 迭代中的二分法 """
            if x < 1:
                return x
    
            l, r = 1, x
            while l <= r:
                mid = l + (r - l) / 2
                sqrt = x / mid  # 技巧：通过取整避免解的精度问题
                if sqrt == mid:
                    return mid
                elif sqrt < mid:
                    r = mid - 1
                else:
                    l = mid + 1

> 查找某个单词是否在字典里出现

def bin_search(arr, target):
      # 查找某个单词是否在字典里出现
      # O(logn)
      l, r = 0, len(arr)
      while l <= r:
        mid = (l+r)/2
        if target == arr[mid]:
          return mid
        elif target > arr[mid]:
          l = mid + 1
        else:
          r = mid - 1

> 学习笔记

![006tNc79ly1fywyhudbenj30u0139wxm.jpg][]

--------------------

### 04 | 数学归纳法：如何用数学归纳提升代码的运行效率？ ###

> 例子

棋盘放麦粒，每次翻倍，放满64个格子，求总的麦粒数量

> 数学归纳法

数学归纳法的一般步骤是这样的：

*  证明基本情况（通常是 n=1 的时候）是否成立；
 *  假设 n=k−1 成立，再证明 n=k 也是成立的（k 为任意大于 1 的自然数）。

> 迭代法 & 归纳法

和使用迭代法的计算相比，数学归纳法最大的特点就在于“归纳”二字。它已经总结出了**规律**。只要我们能够证明这个规律是正确的，就没有必要进行逐步的推算，可以节省很多时间和资源。

迭代法是如何通过重复的步骤进行计算或者查询的。与此不同的是，数学归纳法在理论上证明了命题是否成立，而无需迭代那样反复计算，因此可以帮助我们节约大量的资源，并大幅地提升系统的性能。

> 递归调用 & 数学归纳

*  递归调用先逆向递推再正向递推的过程
 *  数据归纳的证明是由特殊到一般的过程
 *  递归把计算交给计算机，归纳把计算交给人

> 学习笔记

![006tNc79ly1fyx4ukrf18j30u013rx15.jpg][]

--------------------

### 05 | 递归（上）：泛化数学归纳，如何将复杂问题简单化？ ###

> 学习笔记

![006tNc79ly1fywu9x8wnxj30u00xr4fy.jpg][]

> 使用函数的递归（嵌套）调用，找出所有可能的奖赏组合

import copy
    
    rewards = [1, 2, 5, 10]    # 四种面额的纸币
    
    
    def get_sum_combo(total_reword, result=[]):
        """ 使用函数的递归（嵌套）调用，找出所有可能的奖赏组合 Args: total_reword: 奖赏总金额 result: 保存当前的解 Returns: void """
        if total_reword == 0:  # 证明它是满足条件的解，结束嵌套调用，输出解
    
            print(result)
            return
        elif total_reword < 0:  # 证明它不是满足条件的解，不输出
            return
        else:
            for i in range(len(rewards)):
                new_result = copy.copy(result)  # 由于有 4 种情况，需要 clone 当前的解并传入被调用的函数
    
                new_result.append(rewards[i])  # 记录当前的选择，解决一点问题
                get_sum_combo(total_reword - rewards[i], new_result)  # 剩下的问题，留给嵌套调用去解决

> 思考题

一个整数可以被分解为多个整数的乘积，例如，6 可以分解为 2x3。请使用递归编程的方法，为给定的整数 n，找到所有可能的分解（1 在解中最多只能出现 1 次）。例如，输入 8，输出是可以是 1x8, 8x1, 2x4, 4x2, 1x2x2x2, 1x2x4, ……

--------------------

### 06 | 递归（下）：分而治之，从归并排序到MapReduce ###

> 学习笔记

![006tNc79ly1fyx9syrdsgj30u015ahay.jpg][]

> 思考题

你有没有想过，在归并排序的时候，为什么每次都将原有的数组分解为两组，而不是更多组呢？如果分为更多组，是否可行？

老师讲的是最经典的2路归并排序算法，时间复杂度是O(NlogN)。如果将数组分解成更多组（假设分成K组），是K路归并排序算法，当然是可以的，比如K=3时，是3路归并排序，依次类推。3路归并排序是经典的归并排序（路归并排序）的变体，通过递归树方法计算等式T(n)= 3T(n/3)+ O(n)可以得到3路归并排序的时间复杂度为O(NlogN)，其中logN以3为底（不方便打出，只能这样描述）。尽管3路合并排序与2路相比，**时间复杂度看起来比较少，但实际上花费的时间会变得更高，因为合并功能中的比较次数会增加**。类似的问题还有二分查找比三分查找更受欢迎。

--------------------

### 07 | 排列：如何让计算机学会“田忌赛马”？ ###

> 举例

*  田忌赛马
 *  黑客窃取系统密码：暴力破解法

> 定义

*  对于 n 个元素的全排列，所有可能的排列数量就是 nx(n-1)x(n-2)x…x2x1，也就是 n!；
 *  对于 n 个元素里取出 m(0<m≤n) 个元素的不重复排列数量是 nx(n-1)x(n-2)x…x(n - m + 1)，也就是 n!/(n-m)!。

> 学习笔记

![84f9e15c857ca0dbc49837ff0e107945.jpg][]

> 思考题

假设有一个 4 位字母密码，每位密码是 a～e 之间的小写字母。你能否编写一段代码，来暴力破解该密码？（提示：根据可重复排列的规律，生成所有可能的 4 位密码。）

--------------------

### 08 | 组合：如何让计算机安排世界杯的赛程？ ###

> 举例

*  世界杯赛程
 *  多维度的数据分析
 *  自然语言处理的优化（多元文法）

> 定义

*  n 个元素里取出 m 个的组合，可能性数量就是 n 个里取 m 个的排列数量，除以 m 个全排列的数量，也就是 (n! / (n-m)!) / m!。
 *  对于全组合而言，可能性为 2^n 种。例如，当 n=3 的时候，全组合包括了 8 种情况。

> 学习笔记

![b2cbd776947f32b6a3e5e30f388e0eee.jpg][]

--------------------

### 09 | 动态规划（上）：如何实现基于编辑距离的查询推荐？ ###

![006tNc79ly1fz52sx9dtjj30u011d4ke.jpg][]

--------------------

### 10 | 动态规划（下）：如何求得状态转移方程并进行编程实现？ ###

> 什么时候该用动态规划？

首先，如果一个问题有很多种可能，看上去需要使用排列或组合的思想，但是最终求的只是某种**最优解**（例如最小值、最大值、最短子串、最长子串等等），那么你不妨试试是否可以使用动态规划。

其次，**状态转移方程**是个关键。你可以用**状态转移表**来帮助自己理解整个过程。如果能找到准确的转移方程，那么离最终的代码实现就不远了。

> 学习笔记

![006tNc79ly1fzbubw7pb4j30u010rqo6.jpg][]

--------------------

### 11 | 树的深度优先搜索（上）：如何才能高效率地查字典？ ###

> 前缀树（prefix tree）或者叫字典树（trie）

![f4cffbdefa0cd94eda18294c47bf8e34.jpg][]

> 图论

前缀树是一种有向树。那什么是有向树？顾名思义，有向树就是一种树，特殊的就是，它的边是有方向的。而树是没有简单回路的连通图。

![bb472743016ead750fc7a80d8fc6bf7d.jpg][]

![e666c8cd453d503b62dc246c1ab005c0.jpg][]

有向树：顾名思义，有向树是一种特殊的树，其中的边都是有向的，而且它满足以下几个条件：

*  有且仅有一个结点的入度为 0，这个结点被称为根；
 *  除根以外的所有结点，入度都为 1。从树根到任一结点有且仅有一条有向通路。

![366d75b7566adfb09f71f3ae4ad7dd13.jpg][]

> 前缀树的构建和查询

*  构建前缀树

![d06e56e85242f66552672d0f7ada7b26.jpg][]

![950f2b49edf271a36a5f96cf2187638f.jpg][]

*  查询前缀树

假设我们已经使用牛津词典，构建完了一个完整的前缀树，现在我们就能按照开篇所说的那种方式，查找任何一个单词了。从前缀树的根开始，查找下一个结点，顺着这个通路走下去，一直走到到某个结点。如果这个结点及其前缀代表了一个存在的单词，而待查找的单词和这个结点及其前缀正好完全匹配，那就说明成功找到了一个单词。否则，就表示无法找到。

这里还有几种特殊情况，需要注意。

1.  如果还没到叶子结点的时候，待查的单词就结束了。这个时候要看最后匹配上的非叶子结点是否代表一个单词；如果不是，那说明被查单词并不在字典中。
2.  如果搜索到前缀树的叶子结点，但是被查单词仍有未处理的字母。由于叶子结点没有子结点，这时候，被查单词不可能在字典中。
3.  如果搜索到一半，还没到达叶子结点，被查单词也有尚未处理的字母，但是当前被处理的字母已经无法和结点上的字符匹配了。这时候，被查单词不可能在字典中。

前缀树的构建和查询这两者在本质上其实是一致的。构建的时候，我们需要根据当前的前缀进行查询，然后才能找到合适的位置插入新的结点。而且，这两者都存在一个不断重复迭代的查找过程，我们把这种方式称为深度优先搜索（Depth First Search）。

*  深度优先搜索（Depth First Search）

所谓树的深度优先搜索，其实就是从树中的某个结点出发，沿着和这个结点相连的边向前走，找到下一个结点，然后以这种方式不断地发现新的结点和边，一直搜索下去，直到访问了所有和出发点连通的点、或者满足某个条件后停止。

如果到了某个点，发现和这个点直接相连的所有点都已经被访问过，那么就回退到在这个点的父结点，继续查看是否有新的点可以访问；如果没有就继续回退，一直到出发点。由于单棵树中所有的结点都是连通的，所以通过深度优先的策略可以遍历树中所有的结点，因此也被称为深度优先搜索。

![fdc74a1d4797eee2b397e7c6fe5992f9.jpg][]

> 小结

![79701ece6ee3d1a7efdcba51c5684e09.jpg][]

--------------------

### 12 | 树的深度优先搜索（下）：如何才能高效率地查字典？ ###

> 如何使用数据结构表达树？

*  我们再来看**树**的特点。树的结点及其之间的边，和链表中的结点和链接在本质上是一样的，因此，我们可以模仿链表的结构，用编程语言中的指针或对象引用来构建树。
 *  除此之外，我们其实还可以用**二维数组**。用数组的行或列元素表示树中的结点，而行和列共同确定了两个树结点之间是不是存在边。可是在树中，这种二维关系通常是非常稀疏的、非常动态的，所以用数组效率就比较低下。

> 如何使用递归和栈实现深度优先搜索？

深度优先搜索的过程和**递归调用**在逻辑上是一致的

在查询的过程中，至少有三种情况是无法在字典里找到被查的单词的。于是，我们需要在递归的代码中做相应的处理。

*  第一种情况：被查单词所有字母都被处理完毕，但是我们仍然无法在字典里找到相应的词条。
 *  第二种情况：搜索到前缀树的叶子结点，但是被查单词仍有未处理的字母，就返回查找失败。
 *  第三种情况：搜索到中途，还没到达叶子结点，被查单词也有尚未处理的字母，但是当前被处理的字母已经无法和结点上的 label 匹配，返回查找失败。是不是叶子仍然通过结点对象的 sons 变量来判断。

尽管函数递归调用非常直观，可是也有它自身的弱点。函数的每次嵌套，都可能产生新的变量来保存中间结果，这可能会消耗大量的内存。所以这里我们可以用一个更节省内存的数据结构，**栈（Stack）**。

![5391e9f266cb795cec532cc54928b8c1.jpg][]

深度优先搜索时候的例子

![900c981c816375268eefdf274cb149b7.jpg][]

然后，我们用栈来实现一下这个过程。

![893203ec268e095397966b58e1c71d45.jpg][]

从上面的步骤来看，**栈先进后出的特性，可以模拟函数的递归调用**。实际上，计算机系统里的函数递归，在内部也是通过栈来实现的。如果我们不使用函数调用时自动生成的栈，而是手动使用栈的数据结构，就能始终保持数据的副本只有一个，大大节省内存的使用量。

> 小结

在归并排序的数据分解阶段，初始的数据集就是树的根结点，二分之前的数据集代表父节点，而二分之后的左半边的数据集和右半边的数据集都是父结点的子结点。分解过程一直持续到单个的数值，也就是最末端的叶子结点，很明显这个阶段可以用树来表示。如果使用递归编程来进行数据的切分，那么这种实现就是深度优先搜索的体现。

![5410fb301ffce57355ad7ef074e8fd12.jpg][]

在排列中，我们可以把空集认为是树的根结点，如果把每次选择的元素作为父结点，那么剩下可选择的元素，就构成了这个父结点的子结点。而每多选择一个元素，就会把树的高度加 1。因此，我们也可以使用递归和深度优先搜索，列举所有可能的排列。

![98df21876ad52195217709e298707515.jpg][]

从这两个例子，我们可以看出有些数学思想都是相通的，例如递归、排列和深度优先搜索等等。

我来总结一下，其实深度优先搜索的核心思想，就是按照当前的通路，不断地向前进，当遇到走不通的时候就回退到上一个结点，通过另一个新的边进行尝试。如果这一个点所有的方向都走不通的时候，就继续回退。这样一次一次循环下去，直到到达目标结点。树中的每个结点，既可以表示某个子问题和它所对应的抽象状态，也可以表示某个数据结构中一部分具体的值。

![aeef1d5f6be9b5d09618a189520055c7.jpg][]

--------------------

### 13 | 树的广度优先搜索（上）：人际关系的六度理论是真的吗？ ###

> 社交网络中的好友问题

LinkedIn、Facebook、微信、QQ 这些社交网络平台都有大量的用户。在这些社交网络中，非常重要的一部分就是人与人之间的“好友”关系。

在数学里，为了表示这种好友关系，我们通常使用图中的结点来表示一个人，而用图中的边来表示人和人之间的相识关系，那么社交网络就可以用图论来表示。而“相识关系”又可以分为单向和双向。

![26d0c89c9d6b968a9cd3fb889663f752.jpg][]

![3da7b008f235bfde1ca29ff8d66415cb.jpg][]

这些被推荐的候选人，和我都有不少的共同连接，也就是共同好友。所以他们都是我的二度好友。但是，他们和我之间还没有建立直接的联系，因此不是一度好友。也就是说，对于某个当前用户，LinkedIn 是这么来选择好友推荐的：

*  被推荐的人和当前用户不是一度好友；
 *  被推荐的人和当前用户是二度好友。

那为什么我们不考虑“三度“甚至是“四度”好友呢？我前面已经说过，两人之间最短的通路长度，表示他们是几度好友。那么三度或者四度，就意味着两人间最短的通路也要经历 2 个或更多的中间人，他们的关系就比较疏远，互相添加好友的可能性就大大降低。

> 深度优先搜索面临的问题

这种情况下，你可能会想到上一篇介绍的深度优先搜索。深度优先搜索不仅可以用在树里，还可以应用在图里。不过，我们要面临的问题是图中可能存在回路，这会增加通路的长度，这是我们在计算几度好友时所不希望的。所以在使用深度优选搜索的时候，一旦遇到产生回路的边，我们需要将它过滤。具体的操作是，判断新访问的点是不是已经在当前通路中出现过，如果出现过就不再访问。

如果过滤掉产生回路的边，从一个用户出发，我们确实可以使用深度优先的策略，搜索完他所有的 n 度好友，然后再根据关系的度数，从二度、三度再到四度进行排序。这是个解决方法，但是效率太低了。为什么呢？

**六度理论告诉我们，你的社会关系会随着关系的度数增加，而呈指数级的膨胀**。这意味着，在深度搜索的时候，每增加一度关系，就会新增大量的好友。但是你仔细回想一下，当我们在用户推荐中查看可能的好友时，基本上不会看完所有推荐列表，最多也就看个几十个人，一般可能也就看看前几个人。所以，如果我们使用深度优先搜索，把所有可能的好友都找到再排序，那效率实在太低了。

> 什么是广度优先搜索？

更高效的做法是，我们只需要先找到所有二度的好友，如果二度好友不够了，再去找三度或者四度的好友。这种好友搜索的模式，其实就是我们今天要介绍的广度优先搜索。

广度优先搜索（Breadth First Search），也叫宽度优先搜索，是指从图中的某个结点出发，沿着和这个点相连的边向前走，去寻找和这个点距离为 1 的所有其他点。只有当和起始点距离为 1 的所有点都被搜索完毕，才开始搜索和起始点距离为 2 的点。当所有和起始点距离为 2 的点都被搜索完了，才开始搜索和起始点距离为 3 的点，如此类推。

例子

![8feed421333ad442eb8dec4e574eb4d4.jpg][]

广度优先搜索其实就是**横向搜索**一颗树。

> 如何实现社交好友推荐？

需要用到队列这种先进先出（First In First Out）的数据结构。

![b2962dffa28a5c2f3b51bd6039242da1.jpg][]

那么在广度优先搜索中，队列是如何工作的呢？这主要分为以下几个步骤。

*  首先，把初始结点放入队列中。然后，每次从队列首位取出一个结点，搜索所有在它下一级的结点。接下来，把新发现的结点加入队列的末尾。重复上述的步骤，直到没有发现新的结点为止。

我以上面的树状图为例，并通过队列实现广度优先搜索。

![bf8188bd3eccee22dcdda1b2a939c790.jpg][]

> 小结

![2b985dc5dba11a41d968cca57254d640.jpg][]

--------------------

### 14 | 树的广度优先搜索（下）：为什么双向广度优先搜索的效率更高？ ###

> 如何更高效地求两个用户间的最短路径？

双向广度优先搜索。它巧妙地运用了两个方向的广度优先搜索，大幅降低了搜索的度数。

![b665fdbd81e7d0fb3245fbcd3b21230e.jpg][]

你可以同时实现单向广度优先搜索和双向广度优先搜索，然后通过实验来比较两者的执行时间，看看哪个更短。如果实验的数据量足够大（比如说结点在 1 万以上，边在 5 万以上），你应该能发现，双向的方法对时间和内存的消耗都更少。为什么双向搜索的效率更高呢？我以平均好友度数为 4，给你举例讲解。

![1518aaa073b379b20ba3dca8dde08d5b.jpg][]

左边的图表示从结点 a 单向搜索走 2 步，右边的图表示分别从结点 a 和 双向搜索各走 1 步。很明显，左边的结点有 16 个，明显多于右边的 8 个结点。而且，随着每人认识的好友数、搜索路径的增加，这种差距会更加明显。

我们假设每个地球人平均认识 100 个人，如果两个人相距六度，单向广度优先搜索要遍历 100^6=1 万亿左右的人。如果是双向广度优先搜索，那么两边各自搜索的人只有 100^3=100 万。

当然，你可能会说，**单向广度优先搜索之后查找匹配用户的开销更小**啊。的确如此，假设我们要知道结点 a 和 b 之间的最短路径，单向搜索意味着要在 a 的 1 万亿个好友中查找 b。如果采用双向搜索的策略，从结点 a 和 b 出发进行广度优先搜索，每个方向会产生 100 万的好友，那么需要比较这两组 100 万的好友是否有交集。假设我们使用哈希表来存储 a 的 1 万亿个好友，并把搜索 b 是否存在其中的耗时记作 x，而把判断两组 100 万好友是否有交集的耗时记为 y，那么通常 x<y。

> 如何实现更有效的嵌套型聚合？

广度优先策略可以帮助我们大幅优化数据分析中的聚合操作。聚合是数据分析中一个很常见的操作，它会根据一定的条件把记录聚集成不同的分组，以便我们统计每个分组里的信息。目前，SQL 语言中的 GROUP BY 语句，Python 和 Spark 语言中 data frame 的 groupby 函数，Solr 的 facet 查询和 Elasticsearch 的 aggregation 查询，都可以实现聚合的功能。

我们可以嵌套使用不同的聚合，获得层级型的统计结果。但是，实际上，针对一个规模超大的数据集，聚合的嵌套可能会导致性能严重下降。这里我来谈谈如何利用广度优先的策略，对这种问题进行优化。

我们假设这个社交网有 5 万用户，每位用户平均在 5 家公司工作过，而用户在每家公司平均有 10 名共事的同事，那么针对用户的计数器有 5 万个，针对“每个用户 + 每个公司”的计数器有 25 万个，而到了“每个用户 + 每个公司 + 每位同事”的计数器，就已经达到 250 万个了，三个层级总共需要 280 万计数器。

![61dc9b211bf5f7e4f33bf24b1dba9cd8.jpg][]

我们假设一个计数器是 4 个字节，那么 280 万个计数器就需要消耗超过 10M 的内存。对于高并发、低延迟的实时性服务，如果每个请求都要消耗 10M 内存，很容易就导致服务器崩溃。另外，实时性的服务，往往只需要前若干个结果就足以满足需求了。在这种情况下，完全基于排列的设计就有优化的空间了。

从刚才那张图中，其实我们就能想到一些优化的思路。

对于只需要返回前若干结果的应用场景，我们可以对图中的树状结构进行剪枝，去掉绝大部分不需要的结点和边，这样就能节省大量的内存和 CPU 计算。

比如，如果我们只需要返回前 100 个参与项目最多的用户，那么就没有必要按照深度优先的策略，去扩展树中高度为 2 和 3 的结点了，而是应该使用广度优先策略，首先找出所有高度为 1 的结点，根据项目数量进行排序，然后只取出前 100 个，把计数器的数量从 5 万个一下子降到 100 个。

以此类推，我们还可以控制高度为 2 和 3 的结点之数量。如果我们只要看前 100 位用户，每位用户只看排名第一的公司，而每家公司只看合作最多的 3 名同事，那么最终计数器数量就只有 50000+100x5+100x1x10=51500。只有文字还是不太好懂，我画了一张图，帮你理解这个过程。

![8183dff98d2f84b053ca103cb26566d6.jpg][]  
![86e89d1df417e7e1d364e1416855b625.jpg][]

如果一个项目用到排列组合的思想，我们需要在程序里使用大量的变量，来保存数据或者进行计算，这会导致内存和 CPU 使用量的急剧增加。在允许的情况下，我们可以考虑使用广度优先策略，对排列组合所生成的树进行优化。这样，我们就可以有效地缩减树中靠近根的结点数量，避免之后树的爆炸性生长。

> 学习笔记

![d735ed146cac3ca1f81df5acbe634664.jpg][]

--------------------

### 15 | 从树到图：如何让计算机学会看地图？ ###

> 基于广度优先或深度优先搜索的方法

我画了一张图，方便你理解多条通路对最终结果的影响。这张图中有 A、B、C、D、E 五个结点，分别表示不同的地点。

![c155d6b1babe59e0c42928337686f9b2.jpg][]

从这个图中可以看出，从 A 点出发到到目的地 B 点，一共有三条路线。如果你直接从 A 点到 B 点，度数为 1，需要 50 分钟。从 A 点到 C 点再到 B 点，虽然度数为 2，但总共只要 40 分钟。从 A 点到 D 点，到 E 点，再到最后的 B 点，虽然度数为 3，但是总耗时只有 35 分钟，比其他所有的路线更优。这种情形之下，使用广度优先找到的最短通路，不一定是最优的路线。所以，对于在地图上查找最优路线的问题，无论是广度优先还是深度优先的策略，都需要遍历所有可能的路线，然后取最优的解。

> 一个优化的版本：Dijkstra 算法

Dijkstra 算法的核心思想是，对于某个结点，如果我们已经发现了最优的通路，那么就无需在将来的步骤中，再次考虑这个结点。Dijkstra 算法很巧妙地找到这种点，而且能确保已经为它找到了最优路径。

[漫画：图的 “最短路径” 问题][Link 2]

> 小结

我们使用 Dijkstra 算法来查找地图中两点之间的最短路径，而今天我所介绍的 Dijkstra 使用了更为抽象的“权重”。如果我们把结点作为地理位置，边的权重设置为路上所花费的时间，那么 Dijkstra 算法就能帮助我们找到，任意两个点之间耗时最短的路线。

除了时间之外，你也可以对图的边设置其他类型的权重，比如距离、价格，这样 Dijkstra 算法可以让用户找到地图任意两点之间的最短路线，或者出行的最低价格等。有的时候，边的权重越大越好，比如观光车开过某条路线的车票收入。对于这种情况，Dijkstra 算法就需要调整一下，每次找到最大的 mw，更新邻近结点时也要找更大的值。所以，你只要掌握核心的思路就可以了，具体的实现可以根据情况去灵活调整。

![48b3029c0e5310bf9b5f2e5564463a9f.jpg][]

--------------------

### 16 | 时间和空间复杂度（上）：优化性能是否只是“纸上谈兵”？ ###

> 算法复杂度

算法复杂度是一个比较抽象的概念，通常只是一个估计值，它用于衡量程序在运行时所需要的资源，用于比较不同算法的性能好坏。同一段代码处理不同的输入数据所消耗的资源也可能不同，所以分析复杂度时，需要考虑三种情况，最差情况、最好情况和平均情况。

复杂度分析会考虑性能的各个方面，不过我们最关注的是两个部分，时间和空间。时间因素是指程序执行的耗时多少，空间因素是程序占用内存或磁盘存储的多少。因此，我们把复杂度进一步细分为时间复杂度和空间复杂度。

渐进时间复杂度：表示程序运行时间随着问题复杂度增加而变化的规律。

渐进空间复杂度：表示程序所需要的存储空间随着问题复杂度增加而变化的规律。

我们可以使用大 O 来表示这两者。

> 6 个通用法则

*  四则运算法则

对于时间复杂度，代码的添加，意味着计算机操作的增加，也就是时间复杂度的增加。如果代码是平行增加的，就是加法。如果是循环、嵌套或者函数的嵌套，那么就是乘法。

比如二分查找的代码中，第一步是对长度为 n 的数组排序，第二步是在这个已排序的数组中进行查找。这两个部分是平行的，所以计算时间复杂度时可以使用加法。第一步的时间复杂度是 O(nlogn)，第二步的时间复杂度是 O(logn)，所以时间复杂度是 O(nlogn)+O(logn)。

对于空间复杂度，同样如此。需要注意的是，空间复杂度看的是对内存空间的使用，而不是计算的次数。如果语句中没有新开辟空间，那么无论是平行增加还是嵌套增加代码，都不会增加空间复杂度。

*  主次分明法则

这个法则主要是运用了数量级和运算法则优先级的概念。在刚刚介绍的第一个法则中，我们会对代码不同部分所产生的复杂度进行相加或相乘。使用加法或减法时，你可能会遇到不同数量级的复杂度。这个时候，我们只需要看最高数量级的，而忽略掉常量、系数和较低数量级的复杂度。

*  齐头并进法则

这个法则主要是运用了多元变量的概念，其核心思想是复杂度可能受到**多个因素的影响**。在这种情况下，我们要同时考虑所有因素，并在复杂度公式中体现出来。

我在之前的文章中，介绍了使用**动态规划解决的编辑距离问题**。从解决方案的推导和代码可以看出，这个问题涉及两个因素：参与比较的第一个字符串的长度 n 和第二个字符串的长度 m。代码使用了两次嵌套循环，第一层循环的长度是 n，第二层循环的长度为 m，根据乘法法则，时间复杂度为 O(n*m)。而空间复杂度，很容易从推导结果的状态转移表得出，也是 O(n*m)。

*  排列组合法则
 *  一图千言法则

归并排序、二分查找、动态规划（状态转移表）

*  时空互换法则

对于这个规则最直观的例子就是缓存系统。在没有缓存系统的时候，每次请求都要服务器来处理，因此时间复杂度比较高。如果使用了缓存系统，那么我们会消耗更多的内存空间，但是降低了请求相应的时间。

> 小结

![af160564e13906e8ed99e127df4830b1.jpg][]

--------------------

### 17 | 时间和空间复杂度（下）：如何使用六个法则进行复杂度分析？ ###

> 案例分析一：广度优先搜索

在有关图遍历的专栏中，我介绍了单向广度优先和双向广度优先搜索。当时我提到了通常情况下，双向广度优先搜索性能更好。那么，我们应该如何从理论上分析，谁的效率更高呢？

> 案例分析二：全文搜索

搜索引擎你一定用的很多了，它最基本的也最重要的功能，就是根据你输入的关键词，查找指定的数据对象。这里，我以文本搜索为例。要查找某个关键词是不是出现在一篇文章里，最基本的处理方式有两种。

第一，把全文作为一个很长的字符串，把用户输入的关键词作为一个子串，那这个搜索问题就变成了子串匹配的问题。假设字符串平均长度为 n 个字符，关键词平均长度为 m 个字符，使用最简单的暴力法，就是把代表全文的字符串的每个字符，和关键词字符串的每个字符两两相比，那么时间复杂度就是 O(n\*m)。

第二，对全文进行分词，把全文切分成一个个有意义的词，那么这个搜索问题就变成了把输入关键词和这些切分后的词进行匹配的问题。

为了降低搜索引擎在查询时候的时间复杂度，我们要引入**倒排索引**（或逆向索引），这就是典型的牺牲空间来换取时间。如果你对倒排索引的概念不熟悉，我打个比方给你解释一下。

假设你是一个热爱读书的人，当你进入图书馆或书店的时候，怎样快速找到自己喜爱的书籍？没错，就是看书架上的标签。如果看到一个架子上标着“极客时间 - 数学专栏”，那么恭喜你，离程序员的数学书就不远了。而倒排索引做的就是\*\*“贴标签”\*\*的事情。

为了实现倒排索引，对于每篇文章我们都要先进行分词，然后将分好的词作为该篇的标签。让我们看看下面三篇样例文章和对应的分词，也就是标签。其中，分词之后，我也做了一些标准化的处理，例如全部转成小写、去掉时态等。

![188f28947e82254de3a6bb8e5b022a33.png][]

上面这个表格看上去并没有什么特别。好，体现“倒排”的时刻来了。我们转换一下，不再从文章的角度出发，而是从标签的角度出发来看问题。也就是说，从每个标签，我们能找到哪些文章？通过这样的思考，我们可以得到下面这张表。

![7d4f5ee599916f96aad9910ab10a0bf8.png][]

你看看，有了这张表格，想知道查找某个关键词在哪些文章中出现，是不是很容易了呢？整个过程就像在哈希表中查找一样，时间复杂度只有 O(1) 了。当然，我们所要付出的成本就是倒排索引这张表。假设有 n 个不同的单词，而每个单词所对应的文章平均数为 m 的话，那么这种索引的空间复杂度就是 O(n\*m)。好在 n 和 m 通常不会太大，对内存和磁盘的消耗都是可以接受的。

--------------------

### 18 | 总结课：数据结构、编程语句和基础算法体现了哪些数学思想？ ###

> 数据结构

*  数组

一定是你经常使用的数据结构。它的特点你应该很清楚。数组可以通过下标，直接定位到所需的数据，因此**数组特别适合快速地随机访问**。它常常和循环语句相结合，来实现迭代法，例如二分查找、斐波那契数列等等。

另外，我们将要在“线性代数篇”介绍的矩阵，也可以使用多维数组来表示。不过，数组只对稠密的数列更有效。如果**数列非常稀疏，那么很多数组的元素就是无效值，浪费了存储空间**。此外，**数组中元素的插入和删除也比较麻烦，需要进行数据的批量移动**。

*  链表

那么对于稀疏的数列而言，什么样的数据结构更有效呢？答案是**链表**。链表中的结点存储了数据，而链表结点之间的相连关系，在 C 和 C++ 语言中是通过指针来实现的，而在 Java 语言中是通过对象引用来实现的。

链表的特点是不能通过下标来直接访问数据，而是必须按照存储的结构逐个读取。这样做的优势在于，不必事先规定数据的数量，也不再需要保存无效的值，表示稀疏的数列时可以更有效的利用存储空间，同时也利于数据的动态插入和删除。但是，相对于数组而言，链表无法支持快速地随机访问，进行读写操作时就更耗时。

和数组一样，链表也可以是多维的。对于非常稀疏的矩阵，也可以用多维链表的结构来表达。此外，在链表结构中，点和点之间的连接，分别体现了图论中的顶点和边。因此，我们还可以使用指针、对象引用等来表示图结构中的顶点和边。常见的图模型，例如多叉树、无向图和有向图等，都可以用指针或引用来实现。

*  哈希

哈希表就可以通过数组和链表来构造。在很多编程语言中，哈希表的实现采用的是**链地址哈希表**。这种方法的主要思想是，先分配一个很大的数组空间，而数组中的每一个元素都是一个链表的头部。随后，我们就可以根据哈希函数算出的哈希值（也叫哈希的 key），找到数组的某个元素及对应的链表，然后把数据添加到这个链表中。

之所以要这样设计，是因为存在**哈希冲突**。对于不同的数据，哈希函数可能产生相同的哈希值，这就是哈希冲突。如果数组的每个元素都只能存放一个数据，那就无法解决冲突。如果每个元素对应了一个链表，那么当发生冲突的时候，我们就可以把多个数据添加到同一个链表中。可是，把多个数据存放在一个链表，就代表访问效率不高。所以，我们要尽量找到一个合理的哈希函数，减少冲突发生的机会，提升检索的效率。

在第 2 讲中，我还提到了使用求余相关的操作来实现哈希函数。我这里举个例子。你可以看我画的这幅图。

![834ad2a0c5aefd05e0c57aa6d0528fc2.jpg][]

我们把对 100 求余作为哈希函数。因此数组的长度是 100。对于每一个数字，通过它对 100 求余，确定它在数组中的位置。如果多个数字的求余结果一样，就产生冲突，使用链表来解决。我们可以看到，表中位置 98 的链表没有冲突，而 0、1、2、3 和 99 位置的链表都有冲突。

*  栈

说完了哈希，我们来看看栈这种数据结构。我在介绍树的深度优先搜索时讲到栈。它是**先进后出**的。在我们进行函数递归的时候，**函数调用和返回的顺序，也是先进后出**，所以，栈体现了**递归**的思想，可以实现基于递归的编程。实际上，计算机系统里的函数递归，在内部也是通过栈来实现的。虽然直接通过栈来实现递归不如函数递归调用那么直观，但是，由于**栈可以避免过多的中间变量，它可以节省内存空间的使用**。

*  队列

我在介绍广度优先搜索策略时，谈到了队列。队列和栈最大的不同在于，它是一种**先进先出**的数据结构，先进入队列的元素会优先得到处理。队列模拟了日常生活中人们排队的现象，其思想已经延伸到很多大型的数据系统中，例如消息队列。

在消息系统中，生产者会源源不断地推送新的数据，而消费者会对这些消息进行处理。可是，有时消费者的处理速度会慢于生产者推送的速度，这会带来很多复杂的后续问题，因此我们可以通过队列实现消息的缓冲。新产生的数据会先进入队列，直到消费者处理它。经过这样的异步处理，消息的队列实现了生产者和消费者的松耦合，对消费者起到了保护作用，使它不容易被数据洪流冲垮。

*  图

比哈希表，队列和栈更为复杂的数据结构是基于图论中的各种模型，例如各种二叉树、多叉树、有向图和无向图等等。通常，这些模型表示了顶点和顶点之间的稀疏关系，所以它们常常是基于指针或者对象引用来实现的。我在讲前缀树、社交关系图和交通地图的案例中，都使用了这些模型。另外，树模型中的多叉树、特别是二叉树体现了递归的思想。之前的递归编程的案例中的图示也可以对应到多叉树的表示。

> 编程语句

*  条件语句

条件语句的一个关键元素是布尔表达式。它其实体现了逻辑代数中逻辑和集合的概念。逻辑代数，也被称为布尔代数，主要包括了逻辑表达式及其相关的逻辑运算，可以帮助我们消除自然语言所带来的歧义，并严格、准确地描述事物。

当然，逻辑代数在计算机中的应用，远不止条件语句。例如 SQL 语言中的 Select 语句和布尔检索模型。Select 是 SQL 查询语言中十分常用的语句。这个语句将根据指定的逻辑表达式，在一个数据库中进行查询并返回结果，而返回的结果就是满足条件的记录之集合。类似地，布尔检索模型利用逻辑表达式，确定哪些文档满足检索的条件并把它们作为结果返回。

这里顺便提一下，除了条件语句中的布尔表达式，逻辑代数还体现在编程中的其他地方。例如，SQL 语言中的 Join 操作。Join 有多种类型，每种类型其实都对应了一种集合的操作。

1.  内连接（inner join）：假设被连接的两张数据表分别是左表和右表，那么内连接查询能将左表和右表中能关联起来的数据连接后返回，返回的结果就是两个表中所有相匹配的数据。如果认为左表是集合 A，右表是集合 B，那么从集合的角度来说，内连接产生的结果是 A、B 两个集合的交集。
2.  外连接（outer join）：外连接可以保留左表，右表或全部表。根据这些行为的不同，可分为左外连接、右外连接和全连接。无论哪一种，都是对应于不同的集合操作。

*  循环语句

循环语句可以让我们进行有规律性的重复性操作，直到满足某个条件。这和迭代法中反复修改某个值的操作非常一致。所以循环常用于迭代法的实现，例如二分或者牛顿法求解方程的根。在之前的迭代法讲解中，我经常使用循环来实现编码。另外，循环语句也会经常和布尔表达式相结合。嵌套的多层循环，常常用于比较多个元素的大小，或者计算多个元素之间的相似度等等，这也体现了排列组合的思想。

*  函数的调用

至于函数的调用，一个函数既可以调用自己，也可以调用其他不同的函数。如果不断地调用自己，这就体现了递归的思想。同时，函数的递归调用也可以体现排列组合的思想。

> 基础算法

*  分治与哈希

介绍分治思想的时候，我谈及了 MapReduce 的**数据切分**。在分布式系统中，除了数据切分，我们还要经常处理的问题是：如何确定服务请求被分配到哪台机器上？这就引出了负载均衡算法。

常见的包括轮询或者源地址哈希算法。轮询算法把请求按顺序轮流地分配到后端服务器上，它并不关心每台服务器当前的负载。如果我们对每个请求标上一个自动增加的 ID，我们可以认为轮询算法是对请求的 ID 进行求余操作（或者是求余的哈希函数），被除数就是可用服务器的数量，余数就是接受请求的服务器 ID。而源地址哈希进一步扩展了这个思想，扩展主要体现在：

1.  它可以对请求的 IP 或其他唯一标识进行哈希，而不一定是请求的 ID；
2.  哈希函数的变换操作不一定是求余。

不管是对何种数据进行哈希变换，也不管是何种哈希函数，只要能为每个请求确定哈希 key 之后，我们就能为它查找对应的服务器。

*  迭代法和哈希

字符串的编辑距离，但是没有涉及字符串匹配的算法。知名的 RK（Rabin-Karp）匹配算法，在暴力匹配（Brute Force）基础之上，充分利用了迭代法和哈希，提升了算法的效率。

首先，RK 算法可以根据两个字符串哈希后的值。来判断它们是不是相同。如果哈希值不同，则两个字符串肯定不同，不用再比较；此外，RK 算法中的哈希设计非常巧妙，让相邻两个子字符串的哈希值产生了固定的联系，让我们可以通过前一个子串的哈希值，推导出后一个子串的哈希值，这样就能使用迭代法来计算每个子串的哈希值，大大减少了用于哈希函数的计算。

*  回溯

除了分治和动态规划，另一个常用的算法思想是回溯。我们可以使用回溯来解决的问题包括八皇后和 0/1 背包等等。回溯实际上体现了递归和排列的思想。不过，它对搜索空间做了一些优化，提前排除了不可能的情况，提升了算法整体的效率。当然，既然回溯体现了递归的思想，也可以把整个搜索状态表示成树，而对结果的搜索就是树的深度优先遍历。

> 小结

不同的数据结构，都是在编程中运用数学思维的产物。每种数据结构都有自身的特点，有利于我们更方便地实现某种特定的数学模型。

--------------------

### 数学专栏课外加餐（一） | 我们为什么需要反码和补码？ ###

> 什么是符号位？为什么要有符号位？

符号位是有符号二进制数中的最高位，我们需要它来表示负数。

> 如何让计算机理解哪些是正数，哪些是负数呢?

为此，人们把二进制数分为有符号数（signed）和无符号数（unsigned）。

有些编程语言，比如 Java，它所有和数字相关的数据类型都是有符号位的；而有些编程语言，比如 C 语言，它有诸如 unsigned int 这种无符号位的数据类型。

> 什么是溢出？

对于 n 位的数字类型，符号位是 1，后面 n-1 位全是 0，我们把这种情形表示为 -2^(n-1) ，而不是 2^(n-1)。一旦某个数字超过了这些限定，就会发生溢出。如果超出上限，就叫**上溢出**（overflow）。如果超出了下限，就叫**下溢出**（underflow）。

> 溢出之后会发生什么呢？

n 位数字的最大的正值，其符号位为 0，剩下的 n-1 位都为 1，再增大一个就变为了符号位为 1，剩下的 n-1 位都为 0。而符号位是 1，后面 n-1 位全是 0，我们已经说过这表示 -2^(n-1)。

![10974fab2acf1ebd3cd3938387b65c36.jpg][]

那么就是说，上溢出之后，又从下限开始，最大的数值加 1，就变成了最小的数值，周而复始，这不就是余数和取模的概念吗？下面这个图可以帮助你的理解。

![57e275c509cb477588b8c19b63df0b71.jpg][]

其中右半部分的虚线表示已经溢出的区间，而为了方便你理解，我将溢出后所对应的数字也标在了虚线的区间里。由此可以看到，所以说，\*\*计算机数据的溢出，就相当于取模。\*\*而用于取模的除数就是数据类型的上限减去下限的值，再加上 1，也就是 (2(n-1)-1)-(-2(n-1))+1=2x2(n-1)-1+1=2n-1+1。

你可能会好奇，这个除数为什么不直接写成 2^n 呢？这是因为 2^n 已经是 n+1 位了，已经超出了 n 位所能表示的范围。

> 二进制的原码、反码及补码

**原码**就是我们看到的二进制的原始表示。对于有符号的二进制来说，原码的最高位是符号位，而其余的位用来表示该数字绝对值的二进制。所以 +2 的原码是 000…010，-2 的的原码是 100.…010。  
\*  
那么我们是不是可以直接使用负数的原码来进行减法计算呢？答案是否定的。

如果负数的原码并不适用于减法操作，那该怎么办呢？这个问题的解答还要依赖计算机的溢出机制。

我刚刚介绍了溢出以及取模的特性，我们可以充分利用这一点，对计算机里的减法进行变换。假设有 i-j，其中 j 为正数。如果 **i-j 加上取模的除数，那么会形成溢出，并正好能够获得我们想要的 i-j 的运算结果**。如果我说的还是不太好理解，你可以参考下面这张图。

![d3788c6ecac1f8d8eee9552c7452ca4f.jpg][]

我们把这个过程用表达式写出来就是 i-j=(i-j)+(2n-1+1)=i+(2n-1-j+1)。

其中 2^n-1 的二进制码在不考虑符号位的情况下是 n-1 位的 1，那么 2^n-1-2 的结果就是下面这样的：

![413470413ff2fe1ce02fa51f07884c0e.jpg][]

从结果可以观察出来，所谓 2^n-1-j 相当于对正数 j 的二进制原码，除了符号位之外按位取反（0 变 1，1 变 0）。由于负数 -j 和正数 j 的原码，除了符号位之外都是相同的，所以，**2^n-1-j 也相当于对负数 -j 的二进制原码，除了符号位之外按位取反**。我们把 2^n-1-j 所对应的编码称为负数 -j 的**反码**。所以，-2 的反码就是 1111…1101。

有了反码的定义，那么就可以得出\*\* i-j=i+(2^n-1-j+1)=i 的原码 +(-j 的反码)+1\*\*。

如果我们把 -j 的反码加上 1 定义为 -j 的**补码**，就可以得到 **i-j=i 的原码 +(-j 的补码)**。

由于正数的加法无需负数的加法这样的变换，因此正数的原码、反码和补码三者都是一样的。最终，我们可以得到 i-j=i 的补码 +(-j 的补码)。

换句话说，计算机可以通过补码，正确地运算二进制减法。

--------------------

### 数学专栏课外加餐（二） | 位操作的三个应用实例 ###

> 位操作的应用实例

*  验证奇偶数

仔细观察，你会发现偶数的二进制最后一位总是 0，而奇数的二进制最后一位总是 1，因此对于给定的某个数字，我们可以把它的二进制和数字 1 的二进制进行按位“与”的操作，取得这个数字的二进制最后一位，然后再进行判断。

*  交换两个数字

你应该知道，要想在计算机中交换两个变量的值，通常都需要一个中间变量，来临时存放被交换的值。不过，利用异或的特性，我们就可以避免这个中间变量。具体的代码如下：

x = 1
    y = 2
    x = (x ^ y)
    y = x ^ y
    x = x ^ y
    
    print x,y

*  集合操作

集合和逻辑的概念是紧密相连的，因此集合的操作也可以通过位的逻辑操作来实现。

假设我们有两个集合\{1, 3, 8\}和\{4, 8\}。我们先把这两个集合转为两个 8 位的二进制数，从右往左以 1 到 8 依次来编号。

如果某个数字在集合中，相应的位置 1，否则置 0。那么第一个集合就可以转换为 10000101，第二个集合可以转换为 10001000。那么这两个二进制数的按位与就是 10000000，只有第 8 位是 1，代表了两个集合的交为\{8\}。而这两个二进制数的按位或就是 10001101，第 8 位、第 4 位、第 3 位和第 1 位是 1，代表了两个集合的并为\{1, 3, 4, 8\}。

说到这里，不禁让我想起 Elasticsearch 的 BitSet。我曾经使用 Elasticsearch 这个开源的搜索引擎来实现电商平台的搜索。

当时为了提升查询的效率，我使用了 Elasticsearch 的 Filter 查询。我研究了一下这个 Filter 查询的原理，发现它并没有考虑各种文档的相关性得分，因此它可以把文档匹配关键字的情况，转换成了一个 BitSet。

你可以把 BitSet 想成一个巨大的位数组。每一位对应了某篇文档是否和给定的关键词匹配，如果匹配，这一位就置 1，否则就置 0。每个关键词都可以拥有一个 BitSet，用于表示哪些文档和这个关键词匹配。那么要查看同时命中多个关键词的文档有哪些，就是对多个 BitSet 求交集。利用上面介绍的按位与，这点是很容易实现的，而且效率相当之高。

> 二分查找时的两个细节

*  第一个是关于**中间值的计算**

int middle = left + (right - left) / 2;
    
    // 这两处改动的初衷都是一样的，是为了避免溢出。

从理论上来说，(left+right)/2=left+(right-left)/2。可是，我们之前说过，计算机系统有自身的局限性，无论是何种数据类型，都有一个上限或者下限。一旦某个数字超过了这些限定，就会发生溢出。

对于变量 left 和 right 而言，在定义的时候都指定了数据类型，因此不会超出范围。可是，left+right 的和就不一定了。从下图可以看出，当 left 和 right 都已经很接近某个数据类型的最大值时，两者的和就会超过这个最大值，发生上溢出。这也是为什么最好不用通过 (left+right)/2 来求两者的中间值。

![35e891800614511659e0cbf11060b5cc.jpg][]

*  第二个是关于误差百分比和绝对误差。在 Lesson3\_2 中有这么一行：

double delta = Math.abs((square / n) - 1);

这里我使用了误差的百分比，也就是误差值占输入值 n 的比例。其实绝对误差也是可以的，不过我在这里考虑了 n 的大小。比如，如果 n 是一个很小的正整数，比如个位数，那么误差可能要精确到 0.00001。但是如果 n 是一个很大的数呢？比如几个亿，那么精确到 0.00001 可能没有多大必要，也许精确到 0.1 也就可以了。所以，使用误差的百分比可以避免由于不同的 n，导致的迭代次数有过大差异。

由于这里 n 是大于 1 的正整数，所以可以直接拿平方值 square 去除以 n。否则，我们要单独判断 n 为 0 的情况，并使用绝对误差。

> 关于迭代法、数学归纳法和递归

迭代法和递归都是通过不断反复的步骤，计算数值或进行操作的方法。**迭代一般适合正向思维**，而**递归一般适合逆向思维**。而递归回溯的时候，也体现了正向递推的思维。它们本身都是抽象的流程，可以有不同的编程实现。

对\*\*于某些重复性的计算，数学归纳法可以从理论上证明某个结论是否成立。如果成立，它可以大大节约迭代法中数值计算部分的时间。\*\*不过，在使用数学归纳法之前，我们需要通过一些数学知识，假设命题，并证明该命题成立。

对于那些无法使用数学归纳法来证明的迭代问题，我们可以通过编程实现。这里需要注意的是，广义上来说，递归也是迭代法的一种。不过，在计算机编程中，我们所提到的迭代是一种具体的编程实现，是指使用循环来实现的正向递推，而递归是指使用函数的嵌套调用来实现的逆向递推。当然，两种实现通常是可以相互转换的。

**循环的实现很容易理解，对硬件资源的开销比较小**。不过，循环更适合“单线剧情”，例如计算 2^n，n!，1+2+3+…+n 等等。而对于存在很多“分支剧情”的复杂案例而言，使用递归调用更加合适。

**利用函数的嵌套调用，递归编程可以存储很多中间变量**。我们可以很轻松地跟踪不同的分支，而所有这些对程序员基本是透明的。如果这时使用循环，我们不得不自己创建并保存很多中间变量。当然，正是由于这个特性，递归比较消耗硬件资源。

**递归编程本身就体现了分治的思想**，这个思想还可以延伸到集群的分布式架构中。最近几年比较主流的 **MapReduce 框架**也体现了这种思想。

综合上面说的几点，你可以大致遵循这样的原则：

*  如果一个问题可以被迭代法解决，而且是有关数值计算的，那你就看看是否可以假设命题，并优先考虑使用数学归纳法来证明；
 *  如果需要借助计算机，那么优先考虑是否可以使用循环来实现。如果问题本身过于复杂，再考虑函数的嵌套调用，是否可以通过递归将问题逐级简化；
 *  如果数据量过大，可以考虑采用分治思想的分布式系统来处理。

> 在 1 到 n 的数字中，有且只有唯一的一个数字 m 重复出现了，其它的数字都只出现一次。请把这个数字找出来。提示：可以充分利用异或的两个特性。

方法1：暴力查找，两层循环遍历，时间复杂度为O(n^2)，空间复杂度为O(1)

方法2：用快排先进行排序，然后遍历一次，比较前一个数和后一个数，若相等，则查找完成，时间复杂度O(nlogn)，空间复杂度为O(1)

方法3：利用hash表(或set)，进行一次遍历，同时将遍历到的数放入hash表，放入之前判断hash表是否存在，若存在，则找到了重复的数，时间复杂度为O(n)，空间复杂度为O(n)

方法4：使用位向量，遍历给到的n个数，对于出现的数，将对应位标记为1，如果已经是1则查找成功，时间复杂度为O(n)，空间复杂度为(n)，这种方法类似方法3，虽然渐进的空间复杂度和方法3相同，但是其实小很多很多，毕竟只要用1bit就能表示有或无

方法5：利用异或的两个特性

原始数据: 1,2...m,m,...n (是否有序对此题不重要)
    
    所有数字: 1,2,...m,...n
    
    因为 x^x = 0
    
    令a = 1^2...^m...^n
    
       b = 1^2...^m^m...^n
    
    则有: a^b = (1^2...^m...^n)^(1^2...^m...^n)^m = 0^m = m

--------------------

### 数学专栏课外加餐（三）：程序员需要读哪些数学书？ ###

> 数学领域涉及的面很广，相关的书籍也很多。程序员常用的数学知识，包括离散数学、概率和统计和线性代数。

*  基础思想篇推荐书籍：《离散数学及其应用》
 *  概率统计篇推荐书籍：《概率统计》
 *  线性代数篇推荐书籍：《线性代数及其应用》

> 入门、通识类书籍推荐

*  《程序员的数学》
 *  《程序员的数学：概率统计》
 *  《程序员的数学：线性代数》
 *  《数学之美》

[Link 1]: https://time.geekbang.org/column/143
[006tNc79ly1g24lv8r16kj30u01hcwj0.jpg]: https://ws1.sinaimg.cn/large/006tNc79ly1g24lv8r16kj30u01hcwj0.jpg
[006tNbRwly1fyfwndve71j31400u07l3.jpg]: https://ws1.sinaimg.cn/large/006tNbRwly1fyfwndve71j31400u07l3.jpg
[006tNc79ly1fywufo61opj30u01a8qoa.jpg]: https://ws3.sinaimg.cn/large/006tNc79ly1fywufo61opj30u01a8qoa.jpg
[006tNc79ly1fywvw1gn0aj30u015a7om.jpg]: https://ws1.sinaimg.cn/large/006tNc79ly1fywvw1gn0aj30u015a7om.jpg
[006tNc79ly1fywyhudbenj30u0139wxm.jpg]: https://ws3.sinaimg.cn/large/006tNc79ly1fywyhudbenj30u0139wxm.jpg
[006tNc79ly1fyx4ukrf18j30u013rx15.jpg]: https://ws3.sinaimg.cn/large/006tNc79ly1fyx4ukrf18j30u013rx15.jpg
[006tNc79ly1fywu9x8wnxj30u00xr4fy.jpg]: https://ws1.sinaimg.cn/large/006tNc79ly1fywu9x8wnxj30u00xr4fy.jpg
[006tNc79ly1fyx9syrdsgj30u015ahay.jpg]: https://ws1.sinaimg.cn/large/006tNc79ly1fyx9syrdsgj30u015ahay.jpg
[84f9e15c857ca0dbc49837ff0e107945.jpg]: /images/20220205/d2f98da202bb4dc8970f790c25634452.png
[b2cbd776947f32b6a3e5e30f388e0eee.jpg]: /images/20220205/7701daf182f94d63bf87650cad93d04b.png
[006tNc79ly1fz52sx9dtjj30u011d4ke.jpg]: https://ws3.sinaimg.cn/large/006tNc79ly1fz52sx9dtjj30u011d4ke.jpg
[006tNc79ly1fzbubw7pb4j30u010rqo6.jpg]: https://ws2.sinaimg.cn/large/006tNc79ly1fzbubw7pb4j30u010rqo6.jpg
[f4cffbdefa0cd94eda18294c47bf8e34.jpg]: /images/20220205/2ce19d8406fa41918089fcd9d883d6bd.png
[bb472743016ead750fc7a80d8fc6bf7d.jpg]: /images/20220205/e9dbdba6957e4e6b9482f59a1f32fac8.png
[e666c8cd453d503b62dc246c1ab005c0.jpg]: /images/20220205/897bbc183a8e496a9345fc0a8e6a444a.png
[366d75b7566adfb09f71f3ae4ad7dd13.jpg]: /images/20220205/020e0a2a7d3848b897892dcd08ce5eb5.png
[d06e56e85242f66552672d0f7ada7b26.jpg]: /images/20220205/f5e8a775e4a04716ade046a6b921d140.png
[950f2b49edf271a36a5f96cf2187638f.jpg]: /images/20220205/77306d0d8048424abb77cbd44eaa53d4.png
[fdc74a1d4797eee2b397e7c6fe5992f9.jpg]: /images/20220205/80f916f055e647608c9506362b7973e3.png
[79701ece6ee3d1a7efdcba51c5684e09.jpg]: /images/20220205/02e959ff3a5c4fd09a73732610b751cc.png
[5391e9f266cb795cec532cc54928b8c1.jpg]: /images/20220205/4a3be924c7204cbd916c5e316a2f58d3.png
[900c981c816375268eefdf274cb149b7.jpg]: /images/20220205/5499fd5d11254fa798dc62976f5b24ef.png
[893203ec268e095397966b58e1c71d45.jpg]: /images/20220205/eb3d540235c94aada9c204d90c701342.png
[5410fb301ffce57355ad7ef074e8fd12.jpg]: /images/20220205/c7e58dd455014b819fcc044062b9fdae.png
[98df21876ad52195217709e298707515.jpg]: /images/20220205/5be296e9dabc466fb42f040ca4384b9a.png
[aeef1d5f6be9b5d09618a189520055c7.jpg]: /images/20220205/af3f1db598814578ba12a062b5a40935.png
[26d0c89c9d6b968a9cd3fb889663f752.jpg]: /images/20220205/88bbca720544426fae971be5161a9def.png
[3da7b008f235bfde1ca29ff8d66415cb.jpg]: /images/20220205/a0241109442240b49bc5f036047e7abc.png
[8feed421333ad442eb8dec4e574eb4d4.jpg]: /images/20220205/951766ccd1024f94a661f5c3d2763183.png
[b2962dffa28a5c2f3b51bd6039242da1.jpg]: /images/20220205/d54687d4467c43fb872029faa8da42a7.png
[bf8188bd3eccee22dcdda1b2a939c790.jpg]: /images/20220205/c41ae4f8aa554c7391d260d2fc9081cb.png
[2b985dc5dba11a41d968cca57254d640.jpg]: /images/20220205/7295bc37f4cd424dbe9f47b0edf6a3fc.png
[b665fdbd81e7d0fb3245fbcd3b21230e.jpg]: /images/20220205/5409bea508f14bf7a27f8759bd03dcc5.png
[1518aaa073b379b20ba3dca8dde08d5b.jpg]: /images/20220205/8ff51f6fb9d54d58acc59a05499fe575.png
[61dc9b211bf5f7e4f33bf24b1dba9cd8.jpg]: /images/20220205/14e0e558beb445d3b5c682193ddeb4f2.png
[8183dff98d2f84b053ca103cb26566d6.jpg]: /images/20220205/4cb64c9c4d1e4f44b05b5392857f1ad0.png
[86e89d1df417e7e1d364e1416855b625.jpg]: /images/20220205/9aafe0f6825143a4abe464811380760a.png
[d735ed146cac3ca1f81df5acbe634664.jpg]: /images/20220205/4e49562054e647acafa034cea81d8a1d.png
[c155d6b1babe59e0c42928337686f9b2.jpg]: /images/20220205/f8e4c87557d7467ea9c590bd49537c9d.png
[Link 2]: https://mp.weixin.qq.com/s/lsd2YxZmr9LND6NIc7X-pQ
[48b3029c0e5310bf9b5f2e5564463a9f.jpg]: /images/20220205/cbb012d85069436ead531ffb94e031e7.png
[af160564e13906e8ed99e127df4830b1.jpg]: /images/20220205/1161538a9e27447198986af4f5f3d111.png
[188f28947e82254de3a6bb8e5b022a33.png]: /images/20220205/693aa7f0db1848408bf4ac34fd5d456c.png
[7d4f5ee599916f96aad9910ab10a0bf8.png]: /images/20220205/842f3ad8962d40e88a46f746015f27f5.png
[834ad2a0c5aefd05e0c57aa6d0528fc2.jpg]: /images/20220205/42fc5723354847bf9b5a658c437ab9d8.png
[10974fab2acf1ebd3cd3938387b65c36.jpg]: /images/20220205/7eabf211a6154786858def4e421ec35f.png
[57e275c509cb477588b8c19b63df0b71.jpg]: /images/20220205/adc06310f8644a02868d7234a2e40d96.png
[d3788c6ecac1f8d8eee9552c7452ca4f.jpg]: /images/20220205/2de8cdaa2e164a4cbc6bfc0f722b16d4.png
[413470413ff2fe1ce02fa51f07884c0e.jpg]: /images/20220205/5b9789db0fb643759440ae78b604fbe6.png
[35e891800614511659e0cbf11060b5cc.jpg]: /images/20220205/68a5781a53c742ea8de2cc5e26a36357.png