算法 & 数据结构

大部分算法书的问题在于作者并不是真正的程序员, 因此他们不懂得如何写出更容易理解的代码.

这些书里充满了味道糟糕的示例代码:

  • 意义不明的短变量名
  • 省略花括号的编码风格
  • 一个函数负责完成多件事
  • 几乎每一本书对同一种算法的实现都有所不同, 缺乏权威性

此外, 这类书籍倾向于学术化语言, 即使很简单的算法也会被描绘得很复杂.

算法复杂度表示规模增长时算法耗时(步骤)的增速, 大O表示法表示算法的最糟情况.
大O表示法会省略一些常数值.

O(n) 表示线性时间增长, 当n是一个很大的值时, 算法耗时也会同步增长, 例如n=64时, 增速为64.
O(logn) 表示对数时间增长, 当n是一个很大的值时, 算法耗时只会根据幂次进行增长, 例如n=64时, 增速为6.

log10(100) 即"求10的几次幂为100", 答案是2: 10^2 = 100

在大O表示法里讨论算法的复杂度时, log指log2.
拿二分查找举例, 其算法复杂度为logn, 被查找的有序数组包含8个元素, 最多只需检查3个元素即可找到目标(log2(8) = 3).
因此, 二分查找(O(logn))是一种比简单查找(遍历所有元素, O(n))在需要处理的元素数量增长时耗时增长更低的算法.

O(1) 常数的
O(log(n)) 对数的
O(log(n))c) 对数多项式的
O(n) 线性的
O(n^2) 二次的, 很慢的算法
O(nlog(n)) 快速排序
O(n^c) 多项式的
O(c^n) 指数的
O(n!) 阶乘的, 非常慢的算法, 穷举所有排列组合是这种算法的代表

数据结构 一般情况 最差情况
随机访问 插入 删除 搜索 插入 删除 搜索
数组/栈/队列 支持 O(1) O(1) O(n) O(n) O(n) O(n)
链表/双向链表 不支持 O(1) O(1) O(n) O(1) O(1) O(n)
哈希表 O(1) O(1) O(1) O(n) O(n) O(n)
二分搜索树 O(log(n)) O(log(n)) O(log(n)) O(n) O(n) O(n)
AVL树 O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n))
节点/边的管理方式 存储空间 增加顶点 增加边 删除顶点 删除边 轮询
邻接表 O(abs(V)+abs(E)) O(1) O(1) O(abs(V)+abs(E)) O(abs(E)) O(abs(V))
邻接矩阵 O(abs(V)^2) O(abs(V)^2) O(1) O(abs(V)^2) O(1) O(1)
算法(用于数组) 时间复杂度
最好情况 一般情况 最差情况
冒泡排序 O(n) O(n^2) O(n^2)
选择排序 O(n^2) O(n^2) O(n^2)
插入排序 O(n) O(n^2) O(n^2)
归并排序 O(nlog(n)) O(nlog(n)) O(nlog(n))
快速排序 O(nlog(n)) O(nlog(n)) O(n^2)
堆排序 O(nlog(n)) O(nlog(n)) O(nlog(n))
桶排序 O(n+k) O(n+k) O(n^2)
基数排序 O(nk) O(nk) O(nk)
算法 数据结构 最差情况
顺序搜索 数组 O(n)
二分搜索 已排序的数组 O(log(n))
深度优先搜索(DPS) 顶点(节点)数为abs(V), 边数为abs(E)的图 O(abs(V)+abs(E))
广度优先搜索(BFS) 顶点(节点)数为abs(V), 边数为abs(E)的图 O(abs(V)+abs(E))
  • 分而治之 Divide and Conquer(D&C): 递归式问题解决方法
  • 贪心策略: 每一步都采取局部最优解(尽管最后得到的可能不是全局最优解)
  • 动态规划 Dynamic Programming: 从解决小问题着手, 逐步解决大问题.
    动态规划之所以成立, 是因为子问题是独立和离散的, 并且子问题的答案可以被用来解决更大的问题.

排序的稳定性指的是重复元素在排序完成后能否维持其之前的相对位置关系.
比如元素A和元素B的某个属性都是10, 元素A位于元素B之前,
在按此属性排序这两个元素后, 如果元素A总是能保证位于元素B之前, 那么这个排序算法就是稳定的.

计数排序只需要一个一维数组就可以完成的非比较排序, 是在不可避免遍历每一个元素的情况下最快的排序算法.

计数排序的原理是"统计元素的出现次数", 然后"按统计还原出新的数组".

当桶排序(Bucket sort)的存储桶大小为1的时候, 就会退化为计数排序.

计数排序的缺点在于由于它基于统计, 所以只能排序整数数字.

遍历并交换左右两值

在内循环中遍历找到最小值, 与外循环索引位置的元素进行交换, 然后进入外循环的下一个元素.

特征:

  • 耗时与输入无关(即使集合已经排序过, 仍然会消耗同样的时间, 因为总是要遍历剩余的所有元素)
  • 原地排序(最左侧是已经排序的集合)

在内循环中倒序遍历之前的元素, 将每一项与外循环索引位置之前的元素进行比较, 如果更小, 就交换两个元素.
特征:

  • 在小数组情况下优于冒泡和选择排序
  • 原地排序(最左侧是已经排序的集合)

插入排序的改进版本.

原理很复杂: 使数组中任意间隔为h的元素都有序.

特征:

  • 即使是排序大型数组, 性能也可接受(尽管还是慢于能在生产中使用的排序算法)
// 来自: 维基百科
public static void shellSort(int[] arr) {
int length = arr.length;
int temp;
for (int step = length / 2; step >= 1; step /= 2) {
for (int i = step; i < length; i++) {
temp = arr[i];
int j = i - step;
while (j >= 0 && arr[j] > temp) {
arr[j + step] = arr[j];
j -= step;
}
arr[j + step] = temp;
}
}
}

O(nlogn)

归并排序会从数组中间将数组分成两半分别排序, 最后将两个有序的数组合并成一个更大的有序数组.

归并排序是一种分而治之的排序, 将大问题拆分为局部的问题:
如果它能排序两个子数组, 那么也通过进一步拆分子数组进行排序.

归并排序分为两个函数, 一个函数完成归并(merge, 将两个子数组合并成完成排序的数组, 该函数在归并排序中起排序作用),
一个函数完成拆分(split, 把数组拆成小数组, 然后用merge函数归并回来, 该函数在归并排序中起分而治之的作用).

非原地归并(merge):
创建一个额外数组, 遍历这个额外数组以确定每个索引应该插入哪一个子数组索引里的元素
(分别以变量i和j表示子数组的索引, 插入成功则自增1).
原地归并实现起来比较复杂.

  • 自顶向下的归并排序 TopDownMergeSort (递归): 将大数组分割成小数组, 递归这一过程, 最终完成归并.
  • 自底向上的归并排序 BottomUpMergeSort (循序渐进):
    从元素数量为2的小数组开始排序,
    完成一遍之后再从头开始排序元素数量为4的数组(上一轮的两个小数组), 以此类推, 最后完成最大数组的排序.
    此方法比较适合链表结构.

特点:

  • 分而治之

应用最广泛的排序算法.
平均 O(nlogn)
最糟(在数组已经有序的情况下) O(n^2)

与归并排序对比:

  • 归并排序的数组拆分先于数组内容, 总是从中间拆分.
    快速排序的数组拆分后于数组内容, 拆分的位置取决于数组的内容.
  • 虽然归并排序的算法复杂度稳定为O(nlogn), 但归并排序的速度慢于快速排序.
    若将算法复杂度误认为算法的速度, 就会被误导.

特点:

  • 分而治之
  • 可原地排序
  • 高性能

看代码比解释起来更方便, 此版本只需要生成数组并递归:

# 来自算法图解
def quicksort(array):
if len(array) < 2:
return array
else:
pivot = array[0]
less = [i for i in array[1:] if i <= pivort]
greater = [i for i in array[1:] if i > pivot]
return quicksort(less) + [pivot] + quicksort(greater)

挑选一个基准元素(默认使用的基准元素是第一个元素或最后一个元素), 执行以下步骤:

  1. 1.
    从距离基准元素最远的元素开始向基准元素遍历.
  2. 2.
    当发现比基准元素小的元素A时停止.
  3. 3.
    从基准元素向元素A遍历.
  4. 4.
    当发现比基准元素大的元素B时停止.
  5. 5.
    交换元素A和元素B.
  6. 6.
    以元素A和元素B的位置为范围, 继续执行1~5的步骤, 直到没有可遍历的元素(没有符合条件的元素A或没有符合条件的元素B).
    按基准元素的索引分割出两个子数组, 在这两个子数组上递归先前的步骤.
// 来自geeksforgeeks.org
void quicksort(int arr[]) {
sort(arr, 0, arr.length - 1)
}
void sort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
sort(arr, low, pi - 1);
sort(arr, pi + 1, high);
}
}
// 实际起排序作用的部分
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
# 来自geeksforgeeks.org
def partition(arr, low, high):
i = low - 1
pivot = arr[high]
for j in range(low, high):
if arr[j] < pivot:
i = i + 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
def quickSort(arr, low, high):
if low < high:
pi = partition(arr, low, high)
quickSort(arr, low, pi - 1)
quickSort(arr, pi + 1, high)
  • 二分搜索 Binary Search (数组, 链表)
  • 回溯法 Backtracking
  • 双指针 Two Pointers
  • 扫描线 Scan-line algorithm
  • 拓扑排序 (DAG): 基于深度优先搜索

O(V+E)
基于Queue, 逐渐向外延伸的搜索算法.
该算法是一种贪心算法.

可用于解决以下问题:

  • 一个节点到另一个节点的路径是否存在
  • 求一个节点到另一个节点的最短路径(shortest-path problem)

在实现时需要使用队列(Queue), 用于存储待搜索的节点.

基本实现:

  1. 1.
    创建一个队列, 存储待搜索的节点(当前节点的所有邻近节点)
  2. 2.
    从队列中弹出一个节点
  3. 3.
    检查弹出的节点是否是搜索的目标.
    在此处可能会因为图的环状结构构成循环(即无限次检查同一个节点),
    因此要再创建一个散列表/数组保存已经检查过的节点或为节点增加一个属性用以表示已被访问, 以跳过这些节点.
    • 是搜索的目标, 搜索完成, 返回
    • 不是搜索的目标, 将这个节点的所有邻近节点加入队列, 回到步骤2
  4. 5.
    队列为空, 即没有找到搜索目标

求最短路径:

  1. 1.
    在基本实现的"将待搜索节点加入队列"时:
    • 用一个散列表记录前溯点(表示该待搜索节点B由当前节点A搜索得到, 如果在后续搜索中被覆盖也没关系, 因为最短路径只有一条).
  2. 3.
    在BFS搜索完成后返回当前节点, 根据前溯点可得出最短路径(因为是广度优先搜索, 所以搜索返回时走的那条路径一定是最短路径).

可以视作是BFS的 有向无环图(directed acyclic graph, DAG) 版本, 此算法的边(路径)可以加权,
因此"最短路径"的含义从"中间节点数量最少/边的条数最少"变成了"边的权重合计最少".
该算法是一种贪心算法.

加权图(weighted graph): 带有权重(weight)的图, 例如地图上走过不同路径需要不同的时间(权重).
在具体的代码实现上, 加权图需要额外记录节点到另一个节点的权重, 这可以用二维的散列表来表示:

负权边: 权重可以为负值, 带有负权重值的边被称为负权边, 狄克斯特拉算法 不支持 负权边.
支持负权边的算法: 贝尔曼-福德算法(Bellman-Ford algorithm).

该算法首先遍历完所有的节点, 得出节点的开销表, 最后通过开销表得出最短路径.

开销表(costs):
一张用来记录从起点节点到特定节点最少权重(合计)值的表格, 表格项(节点)的默认值为无穷大.
为了能得出最短路径, 还需要记录节点的前一个节点, 单独创建一个表或者直接记录在开销表里都行.
与BFS一样, 为了避开那些已经走过的节点, 需要一个散列表记录已经走过的节点.

步骤:

  1. 1.
    找出权重值最低的节点
  2. 2.
    对该节点的邻近节点,
    检查是否存在前往邻近节点的更短路径(该操作被称为边的松弛relaxation), 如果有就更新开销表
  3. 3.
    重复此过程, 直到遍历完全部节点
  4. 4.
    计算最终路径

基于Stack(递归), 不撞南墙不回头的搜索算法.

在实现时需要使用栈(Stack), 用于存储搜索时下探的路径, 如果使用递归, 则栈由编程语言自身实现.

根据节点访问顺序的不同, 可分为三种模式:

  • 前序/先序(preorder)
  • 中序(inorder, 在二叉树中出现),
  • 后序(postorder)

造成不同访问顺序的原因在于递归过程中调用回调函数(执行对树的操作)的时机不同:

  • 前序/先序: 在递归后代之前调用回调
  • 中序(二叉树): 递归left, 调用回调, 递归right
  • 后序: 在递归后代之后调用回调

Hash的本质是将大范围值单向映射到小范围值上.

h(k) = k mod m

值域为 [0, m-1]

可以通过取余运算将大整数值映射到特定的小范围整数上.
该方法的主要缺点是计算机执行除法运算的性能不佳.

在取m值时, 一般会选取一个质数, 并且此值应该远离2的幂.

h(k) = floor(m(kA mod 1))
常数A需要满足 0<A<1

值域为 [0, m-1]

其中, kA mod 1 是取出 kA 的小数部分.
m一般取2的幂.

该算法可以通过位运算来加速, 因此是速度最快的散列函数之一.

可以通过前一项的哈希值和当前项快速算出当前项哈希值的哈希算法.

常见于rsync, Dropbox等增量内容传输工具.

n 被搜索字符串的长度
m 模式的长度

遍历字符串, 从每个字符开始移动指针进行匹配, 当匹配失败(失配)时指针回溯到开始匹配的字符的下一个字符.

一般情况的时间复杂度为O(n+m), 最差情况的时间复杂度为O(nm).

KMP的核心思想是在朴素搜索时通过已知信息来跳过一些字符, 从而减少最坏情况下浪费掉的匹配时间.

在字符串匹配失败时(也称为"失配"), KMP基于以下公式计算指针回溯后的移动位数, 而不是像朴素搜索那样固定移动1位:
KMP匹配失败时的移动位数 = 最后一个成功匹配的字符的部分匹配值 +1

时间复杂度稳定为O(n+k), 其中O(k)为构建PMT的时间复杂度.

在搜索开始前, 需要先从搜索词里创建一张部分匹配表(<<PMT>>, partial match table).
例如:

搜索词 ABCDABD
部分匹配值 0000120

一个字符的部分匹配值是"从字符串的首个字符其到此字符的字符串"的"前缀集合"和"后缀集合"的最长共有元素的长度.
部分匹配值实际代表的是 字符串起始部分开始与当前字符相关的重复模式(overlap)的长度.

以字符串"ABCDABD"为例:

索引 字符 字符串 前缀集合 后缀集合 共有元素 最长共有元素的长度
0 A A [] [] [] 0
1 B AB [A] [B] [] 0
2 C ABC [A, AB] [BC, B] [] 0
3 D ABCD [A, AB, ABC] [BCD, CD, D] [] 0
4 A ABCDA [A, AB, ABC, ABCD] [BCDA, CDA, DA, A] [A] 1
5 B ABCDAB [A, AB, ABC, ABCD, ABCDA] [BCDAB, CDAB, DAB, AB, B] [AB] 2
6 D ABCDABD [A, AB, ABC, ABCD, ABCDAB] [BCDABD, CDABD, DABD, ABD, BD, D] [] 0

在实现KMP算法时, 预先计算好的指针跳跃位置的索引值被存储为next数组.

function computeNext(pattern: string): number[] {
const next: number[] = new Array(pattern.length).fill(0)
if (pattern.length === 1) return next
for (let i = 2; i < str.length; i++) {
if (pattern[i - 1] === pattern[next[i - 1]]) {
next[i] = next[i - 1] + 1
}
}
return next
}
void ComputeNext(char *pattern, int patternLength, int next[]) {
next[0] = 0;
if (patternLength <= 1) return;
next[1] = 0;
int jump = 2;
while (jump < patternLength) {
if (pattern[jump - 1] == pattern[next[jump - 1]]) {
next[jump] = next[jump - 1] + 1;
} else {
next[jump] = 0;
}
jump++;
}
}

Boyer-Moore是高效率字符串搜索算法, 被用于各种单模式搜索.
该算法从模式的尾部开始匹配.

详见 https://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html

在搜索前需要构造出DFA.

非常快, 时间复杂度为O(n).

基于模式构造出以TF表(二维数组)表示的DFA, 根据每个字符决定下一个状态.
当下一个字符与模式匹配时, 会在当前状态码上自增1, 从而得到下一个状态.
当下一个字符与模式不匹配时, 会"跳转到首个状态"或"利用先前的重复模式从而跳转到某个匹配的中间状态".

例如以下为模式ACACACGA的TF表:

状态(码) 字符
A C G T
0 1 0 0 0
1 1 2 0 0
2 3 0 0 0
3 1 4 0 0
4 5 0 0 0
5 1 4 6 0
6 7 0 0 0
7 1 2 0 0

多模式搜索当然也可以用于单模式搜索, 但很可能是用牛刀杀鸡.

通过滚动哈希进行匹配.

一般情况的时间复杂度为O(n+m), 最差情况的时间复杂度为O(nm).

被用于单模式搜索时效率不如KMP.

为敏感词字典创建Trie, 然后进行搜索.

在中文互联网中流传的一种基于HashMap的有限自动机, 而该方法实际上是用HashMap实现的字典树方法.

字典可以动态增减.

随着字典的增长, Trie数据结构可能占用较大的内存空间.

一种多模式搜索算法.
在搜索前需要按字典编译出一个自动机.

一般情况的时间复杂度为O(n+m), 最差情况的时间复杂度为O(n^2).

  1. 1.
    先根据要匹配的元素构建字典树(Trie)
  2. 2.
    将字典树里加上fail指针.
    fail指针: 当前字符匹配失败时, 应该跳转到新的节点, 这个跳转的指针就叫做fail指针.
    fail指针的存在是为了加速不匹配情况下的查询速度.

举例来说, 有以下两条Trie子树A和B:
A: s->h->e->i
B: h->i->s
->e->r->s

两条子树都具有h->e段, 当A树的s->h->e匹配成功, 但在i节点上失败时,
根据fail指针, 可以将e节点跳转到B树h->e段的e节点上, 从而节省下了再次匹配共有前缀h->e的时间.

加上fail指针后, 即可得到AC自动机.

执行一般的Trie匹配操作, 但在失败时根据fail指针进行移动.
在自动机中, 如果fail指针最终指回根节点, 说明当前字符没有可匹配的项, 放弃当前字符, 匹配下一个字符.

时间复杂度近似于线性.

每次修改字典都需要重新编译自动机.

hyperscan是一个高性能多模式正则表达式库, 目前是世界上最快的正则表达式库.
hyperscan在内部使用自动机.

指数退避算法被用于乐观并发控制的重试机制.
客户端会根据因子(factor)计算下次重试的时间, 此时间是随着重试次数而指数增长的.

Math.min(factor ** retries * minTimeout, maxTimeout)

一般情况下, factor的值取2.
第一次重试(retries = 0): minTimeout
第二次重试(retries = 1): minTimeout * 2
第三次重试(retries = 2): minTimeout * 4

无抖动的指数退避被认为对于解决惊群问题(thundering herd problem)的作用十分有限, 因此出现了带抖动的指数退避.
抖动指的是在算法中引入随机值, 从而大幅降低客户端发生竞争的可能性.

增量抖动指的是在指数退避值的基础上, 增加一个随机值.
这种抖动的缺点在于进一步延长了退避的时间.

randomTimeout是一个取值范围为[0, 1000]的随机毫秒值.

return Math.min(factor ** retries * minTimeout + randomIntInclusive(0, 1000), maxTimeout)

randomTimeout取值上限是以当前指数退避的结果乘以一个百分数(例如20%)得来的,
然后再根据[0, upperBound]得到随机毫秒值.

这种方法在重试次数较小时有较小的随机范围, 在重试次数较大时有较大的随机范围.

const temp = factor ** retries * minTimeout
return Math.min(temp + randomIntInclusive(0, temp * 0.2), maxTimeout)

非增量抖动指的是以指数退避值为上限的随机抖动.

对半抖动是在指取指数退避值的一半进行抖动, 即[0, timeout / 2].

const temp = Math.min(factor ** retries * minTimeout)
return Math.floor(temp / 2 + randomInclusive(0, temp / 2))

完全抖动是指完全将指数退避的计算结果作为随机数上限, 将0作为下限的抖动, 即[0, timeout].

在AWS被认为是最佳的抖动方式:
https://aws.amazon.com/blogs/architecture/exponential-backoff-and-jitter/

return randomIntInclusive(0, Math.min(factor ** retries * minTimeout, maxTimeout))

设定一个计数器, 周期起始时间点和固定时间窗口内请求的阈值, 达到阈值即拒绝请求.
在超过指定的时间后, 重置计数器和更新周期起始时间点.

符合直觉, 同时也符合各类API服务常见的限流描述: 在X时间内允许Y个请求.

流量可能在时间段的开始处就被消耗完, 其余的时间处于空载状态.
这迫使时间窗口被设定为较小的值.

这是对固定时间窗口的改进.
滑动时间窗口记录了当前设定的时间窗口里每个请求到达时的时间点,
因此在检查阈值时, 可以根据当前时间点向前滑动时间窗口动态确定周期起始时间点,
而不必使用固定的周期起始时间点.

突发的大流量(例如大量请求)可能导致计数器快速到达阈值, 从而使其余的时间处于空载状态.

令牌桶是一个存放令牌的桶, 其容量是恒定的(记为M, 可当作系统允许的瞬时最大流量, 这种最大流量不可持续).
令牌桶会以恒定速度产生令牌(意为T秒内允许总计消耗N个令牌的操作), 并把令牌放进令牌桶中.

当令牌桶的容量满了, 多余的令牌就会被放弃.
当处理请求时, 申请从令牌桶里取出相应数量的令牌, 如果令牌桶中的令牌数量不足, 则拒绝该请求.

令牌桶的优点是可以用令牌的数量来类比实际流量的大小:
一个请求可能需要大量的令牌, 而令牌不足时, 则该请求会直接无法发出, 而那些只需要少量令牌的请求则能够被放行.

令牌桶是漏桶meter变体的反向实现, 想象水龙头在往空水桶里灌水(令牌), 然后再把水(令牌)从桶中舀出来.

在漏桶中, 将请求看作是水流.
漏桶是一个有进水口和出水口的桶, 桶的容量是恒定的.
出水口的流速是恒定的(意为T秒内最多消耗N个单位的水), 进水口流速由生产者决定.

当进水口的速率大于出水口时, 桶最终会溢出, 此时会拒绝生产者的请求.
当出水口的速率大于进水口时, 桶最终会变空, 此时会拒绝消费者的请求.

漏桶的仪表形式是一种计数器, 计数器会由于流量增加而上升, 并定期减少.
这其实是令牌桶的一种实现, 只不过在描述上方向相反.

漏桶的队列形式是一种FIFO队列, 与一般认为的消息队列具有相似的工作模式:
定期从队列中取出一定数量的流量, 然后转发.

  • 由于令牌桶的特性, 令牌桶的容量往往需要设定为一个较高的值,
    否则由于令牌的补充速率较低, 可能会导致流量无法被充分利用.
    因此, 令牌桶的容量无法用于最大负载值的参考, 对于后端来说, 系统的最大负载难以预测.
  • 由于漏桶的特性, 漏桶出水口的最大速率是恒定不变的.
    因此对被限流的后端来说, 系统的最大负载是一个确定的值.

缓存具有容量限制, 当缓存已满, 首先丢弃使用频率最低的项目.

最简单的实现方式是为每个项目分配一个计数器, 每次使用项目时, 增加其值.
当缓存已满, 丢弃计数值最小的项目.

  • 使用次数最多的项目, 即使长时间不使用, 也不会被删除.
  • 刚刚进入缓存的项目, 很容易成为使用计数值最小的项目.

缓存具有容量限制, 当缓存已满, 首先丢弃最近最少使用的项目.

实现方式为设置一个自增计数器, 为每个项目分配一个序号值.
每次访问缓存时, 将对应项目的序号设置为计数器的值, 然后将计数器自增1.
当缓存已满, 丢弃序号最小的项目.

对于有序结构而言, 有一种很简单的实现方法:
每次访问时, 从序列里删除最早的项目, 然后将其插入到序列末尾.

带有容量限制和过期删除机制的缓存.

结合了LFU和LRU.

当缓存满时, 随机选择一个项目替换掉.

汉明距离仅可用于计算等长字符串之间的编辑距离, 因此对于模糊匹配来说用处不大.

https://en.wikipedia.org/wiki/Comparison_gallery_of_image_scaling_algorithms

缩放的图像不会变得模糊, 而是以锯齿呈现, 主要用于将像素图放大.

require! 'prelude-ls': {round, map, zip-with}
nearest-neighbor-interpolation = (zoom, src-image) ->
color = (image, x, y) ->
i = (y * image.width + x) * 4
map (|| 0), image.data[i to i + 3]
canvas = document.create-element \canvas
canvas.width = src-image.width * zoom
canvas.height = src-image.height * zoom
ctx = canvas.get-context \2d
dst-image= ctx.create-image-data canvas.width, canvas.height
for dst-x from 0 til canvas.width
for dst-y from 0 til canvas.height
src-color = color src-image, (round dst-x / zoom), (round dst-y / zoom)
dst-i = (dst-y * canvas.width + dst-x) * 4
dst-color = map (/ 2), zip-with (+), src-color, color dst-image, dst-x, dst-y
for i from 0 to 3
dst-image.data[dst-i + i] = dst-color[i]
ctx.put-image-data dst-image, 0, 0
canvas
require! 'prelude-ls': {map, round, floor, ceiling, sqrt, abs, sum}
bilinear-interpolation-put = (zoom, src-image) ->
color = (image, offset, point) -->
if point.x >= image.width or point.y >= image.height
if offset is 3
255
else
0
else
image.data[(image.width * point.y + point.x) * 4 + offset]
[R, G, B, A] = map (color src-image), [0 to 3]
canvas = document.create-element \canvas
canvas.width = src-image.width * zoom
canvas.height = src-image.height * zoom
ctx = canvas.get-context \2d
dst-image = ctx.create-image-data canvas.width, canvas.height
for dst-x from 0 til canvas.width
for dst-y from 0 til canvas.height
src = x: dst-x / zoom, y: dst-y / zoom
lt = x: floor(src.x), y: floor src.y
rt = x: ceiling(src.x), y: floor src.y
lb = x: floor(src.x), y: ceiling src.y
rb = x: ceiling(src.x), y: ceiling src.y
weight-mean = (src, points) ->
weights = []
sf = []
for p, i in points when p.x < src-image.width and p.y < src-image.height
w = sqrt(abs(p.x - src.x) * abs(p.y - src.y))
w = 1 / w if w isnt 0
weights.push w
sf.push ((w, p)->
(f) ->
w * f p
)(w, p)
(f) ->
s = sum map ((s) -> s(f)), sf
if sum(weights) is 0 then 0 else s / sum weights
get-weight-mean = weight-mean src, [lt, rt, lb, rb]
dst-i = (dst-y * canvas.width + dst-x) * 4
dst-image.data[dst-i + 0] = round get-weight-mean R
dst-image.data[dst-i + 1] = round get-weight-mean G
dst-image.data[dst-i + 2] = round get-weight-mean B
dst-image.data[dst-i + 3] = round get-weight-mean A
ctx.put-image-data dst-image, 0, 0
canvas
require! 'prelude-ls': {map, floor}
bicubic-interpolation-put = (zoom, src-image)->
color = (image, x, y) ->
i = (y * image.width + x) * 4
map (|| 0), image.data[i to i + 3]
triangle-interpolation = f ->
f = f / 2
if f < 0
f + 1
else
1 - f
clamp = value ->
return 255 if value > 255
return 0 if value < 0
value
canvas = document.create-element \canvas
canvas.width = src-image.width * zoom
canvas.height = src-image.height * zoom
ctx = canvas.get-context \2d
dst-image = ctx.create-image-data canvas.width, canvas.height
for dst-y from 0 til dst-image.height
src-y = dst-y * zoom
j = floor src-y
t = src-y - j
for dst-x from 0 til dst-image.width
src-x = dst-x * zoom
k = floor src-x
u = src-x - k
rgba = [0, 0, 0, 0]
s = 0
for m from -1 til 3
for n from -1 til 3
rgb = color src-image, j + m, k + n
f1 = triangle-interpolation m - t
f2 = triangle-interpolation -(n - u)
s += f2 * f1
rgba[0] += rgb[0] * f2 * f1
rgba[1] += rgb[1] * f2 * f1
rgba[2] += rgb[2] * f2 * f1
rgba[3] += rgb[3] * f2 * f1
dst-i = (dst-y * canvas.width + dst-x) * 4
dst-image.data[dst-i + 0] = clamp parseInt rgba[0] / s
dst-image.data[dst-i + 1] = clamp parseInt rgba[1] / s
dst-image.data[dst-i + 2] = clamp parseInt rgba[2] / s
dst-image.data[dst-i + 3] = clamp parseInt rgba[3] / s
ctx.put-image-data dst-image, 0, 0
canvas

Array 的特定规则子集.

DAG 的特定规则子集.

Tree 的特定规则子集.

有序的二叉树.

一种DFA, 用于实现字符串匹配, 通过空间换时间获得高性能.
被实际运用在搜索关键字的自动完成, 敏感词匹配等功能上.

对标准字典树的一种压缩尝试, 它的末端节点从字符变成了字符串.

增减字典项目时, 需要重新构建同级的节点.

后缀树为字典的每一个后缀建立节点, 例如单词banana会建立以下字符串的字典(\0用于标记字符串结尾):
banana\0
anana\0
nana\0
ana\0
na\0
a\0
\0

需要较大的内存空间, 常用于模式匹配.

堆是一种完全二叉树数据结构, 除最底层之外, 其他层的节点都被元素填满, 且最底层尽可能从左到右插入.

其特点在于堆的所有节点要么总是小于它的后代, 要么总是大于它的后代.
根据这种特点, 可将堆分为两种类型:

  • 最大堆(根节点最大)
  • 最小堆(根节点最小)

Python内建的heapq模块提供了一种基于list的堆实现, 它用list表示二叉树, 将list转化为堆的操作被称为heapify.

具有优先级的队列, 可插入带优先级的元素, 取出优先级最高的元素, 查看可优先级最高的元素.
优先队列有多种不同的实现, 有的实现会维护一个有序数组, 有的则使用堆队列.

一种只支持"入队/入列(enqueue)"和"出队/出列(dequeue)"的数据结构.

特性:

  • 先进先出(First In First Out, FIFO)

链表诞生的原因是数组在内存中大小固定, 在数组中间插入/删除元素效率很低(需要移动之后的所有元素),
对数组进行扩容很麻烦(复制所有的数组元素到新的位置), 未使用的数组部分还会浪费内存空间.

链表用一个结构体解决了数组的痛点, 代价是比单个数组成员多消耗一点内存空间(用于存储前后元素的指针),
以及无法根据索引找到元素(只能通过遍历).

Hash + Array [+ Linked List ]

由于HashTable使用的哈希函数的映射结果数量很可能有限,
HashTable在存储时可能会将多个元素存储在一个位置, 这时有两种处理冲突情况的方法.

为散列表的每一个冲突位置创建一个链表, 将冲突的元素用链表连接起来.

在搜索存在冲突的位置时, 逐个遍历链表上的元素, 返回匹配的元素.

线性探查法将冲突的元素保存在对应索引位置(已经被使用)的下一个索引上(若下一个索引也被使用, 以此类推).

删除元素时需要将之后的冲突元素全部前移一位/将最后一位交换到被删除元素的位置/惰性删除
(仅添加标记实现的软删除).

缺陷:

  • 一些编程语言的数组是固定大小的, 使用线性探查法很可能耗尽数组.

一种由"节点(Node)"和"边(Edge)"组成的数据结构.

类型:

  • 有向图(directed graph): 节点之间的连接包含方向
  • 无向图(undirected graph): 节点之间的连接不包含方向
  • 有向无环图(DAG): 在有向图的基础上不包含环状结构(多个节点之间在方向上构成循环)

表示方法:

  • 邻接矩阵
  • 邻接表
    使用散列表表示节点之间的关系
graph = {}
graph['you'] = ['alice', 'bob', 'claire']
graph['bob'] = ['anuj', 'peggy']
graph['alice'] = ['peggy']
graph['claire'] = ['thom', 'jonny']
graph['anuj'] = []
graph['peggy'] = []
graph['thom'] = []
graph['jonny'] = []
  • 关联矩阵

Graph 的特定规则子集.

布隆过滤器是一种概率数据结构, 用于替代HashMap实现超大集合(元素规模上亿)的元素是否存在的判定.
用布隆过滤器能够得到"该元素一定不存在"或"可能存在"两种结果, 后一种结果不是确定的, 而是概率性的.
Redis有布隆过滤器的模块RedisBloom.

布隆过滤器的原理很简单, 想象有一个超大的数组(数组长度计为m), 所有数组下标的值都为0.
我们用k种不同的hash算法对需要存入布隆过滤器的元素分别求hash值,
然后将数组对应hash值的下标设置为1.
在布隆过滤器的公式里, n为插入的元素个数.
当我们需要查询一个元素是否存在时, 采取相同的k种hash操作, 然后查看对应的数组下标,
如果有一个数组下标为0, 则说明这个值肯定不存在于布隆过滤器, 反之则可能存在.

将每个元素都这样存入布隆过滤器时, 有概率出现某个下标值已经被设置为1的现象,
这是布隆过滤器无法准确判定"元素存在"的主要原因.

布隆过滤器不支持删除.

下推自动机与状态机的区别在于它有栈, 因此它不仅可以到达下一个状态, 还可以退回上一个状态.

有限状态机是一种数学计算模型, 是一个在任何给定时间只能处于有限数量状态中的一种状态的抽象机器.
状态机具有一个状态转换函数(transation), 它会响应输入的"事件"改变自身的状态.

一些状态机是无尽的, 具有循环结构, 一些状态机则有一个最终状态.

状态爆炸是指状态机需要表示的状态数量因为组合激增而变成笛卡尔积.

举例来说, 一个游戏角色有"站立"和"跳起"两种状态, 又有"持枪"和"不持枪"两种状态.
如果要在一个状态机里表示该游戏角色的全部状态,
就会出现"持枪站立", "不持枪站立", "持枪跳起", "不持枪跳起"这四种状态.

通常使用状态图的复合状态特性解决状态爆炸问题.

状态机没有得到广泛应用的一个重要原因是使用状态机会引入大量额外代码.
即使是使用专门的状态机库, 描述状态机的代码也会使代码量显著增加,
而且这些代码对状态机的描述远远不如一张图片来得直观.

由于大多数场景可以被简单的if条件和基于布尔值的状态开关应付, 因此引入状态机很像是一种过度设计.

隐式状态机指的是具有状态机的行为, 但并不单独抽象成状态机的系统.
传统编程中的各种基于if条件的状态判断和基于布尔值的状态开关就是隐式状态机.

隐式状态机本质上是意大利面条代码, 并不具有状态机的优点, 会随着状态数量增加而陷入维护困境.

隐式状态机:

  1. 1.
    程序世界发生了一些事情.
  2. 2.
    事件处理器得到事件, 检查布尔值变量.
  3. 3.
    基于布尔值变量, 事件处理器直接调用相关的组件行为.

显式状态机:

  1. 1.
    程序世界发生了一些事情.
  2. 2.
    事件处理器得到事件, 将事件转发给状态机.
  3. 3.
    状态机可能出现两种结果:
    1. 1.
      新事件导致状态变更, 此时状态机会调用相关的组件行为.
      根据情况, 状态机与组件的关系可以分为两种类型:
      • 耦合(组件需要了解当前状态):
        被调用的行为位于组件侧, 组件侧查询当前状态, 然后选择对应的条件分支.
        这种情况下, 当修改状态机时, 组件侧也需要一起修改.
      • 解耦(组件不需要了解当前状态):
        被调用的行为位于状态机, 组件侧对状态一无所知, 但提供相应的接口允许状态机操纵它.
        这种情况下, 当修改状态机时, 组件侧不需要做修改.
    2. 3.
      新事件未导致状态变更.

状态机的增强版, 通过让状态机可以嵌套, 克服了状态机的局限性.

参考: https://statecharts.dev/

与复合状态相对的概念, 即没有子状态的状态.

具有一个或多个子状态的状态被称为复合状态, 子状态的变更通过复合状态的子状态机来描述.

复合状态的一种.
并行状态是一个状态里的多个互不相关的子状态机.
当状态机进入并行状态时, 每个子状态机从头启动
(子状态机一旦退出, 其状态就会销毁, 每次进入都是重新开始),
当状态机退出并行状态时, 每个子状态机都退出.

并行状态常用于组合一个实体的多个离散行为, 以解决状态爆炸.

复合状态的一种.
分层状态是嵌套了子状态机的状态, 当状态机进入分层状态时, 就会从头启动它的子状态机.

一种特殊的状态, 允许在退出此状态时回到进来时的那个状态.

有浅历史状态和深历史状态两种:

  • 浅历史状态指的是一个复合状态能够记住它是从哪个状态转换而来的,
  • 深历史状态指的是一个复合状态能够记住它是从哪个状态转换而来的, 以及该状态所有后代状态机的状态.

Guard是"事件"所具有的条件检查断言.
只有在断言通过时, 才会将事件输入给状态转换函数.

状态机里的一个状态可以响应事件名相同, 但Guard不同的多个事件.
只有第一个断言通过的事件会真的发生.

条件检查为状态转换引入了复杂性, 使得推理状态转换变得困难.

一种与特定状态的"进入状态"绑定的行为, 进入该状态后会立即触发又一次转换.
通常与Guard配合使用, 仅在满足条件时才发生让自动转换成功.

使用场景:

  • 根据条件决定状态机的初始化状态.

状态图的强大扩展性使得用一张大状态图描述整个程序成为可能, 但这么做往往适得其反.

状态图本身和状态机一样, 只有描述状态变化的能力.
可执行状态图在状态图的基础上加上行为(副作用),
使得状态图本身变成一种根据状态变更执行特定行为的机器.