不相交集合元素的数据结构——并查集

不相交集合有两种基本操作:合并(union)和查询(find)。

并查集保持了一组不相交的动态集合,每个集合通过一个代表来识别,代表即集合中的某个成员。

数组实现Quick Find

我们可以直接用数组来存储集合的标识,这样查找操作直接返回对应数组的值即可,复杂度为O(1);而合并操作每次都需要遍历整个数组,复杂度为O(n)

     0   1   2   3   4   5   6   7   8   9
     -------------------------------------
 id  0   1   2   3   4   5   6   7   8   9

union(1, 4)
union(1, 5)

     0   1   2   3   4   5   6   7   8   9
     -------------------------------------
 id  0   1   2   3   1   1   6   7   8   9

有根树表示 Quick Union

为了降低合并操作的复杂度,我们可以用多个有根树表示集合,每个结点存储指向其父亲结点的指针,根节点指向自己。判断是否属于同一个集合时,我们只需要判断元素所属的树根是否相同。

批注 2019-10-08 010040.jpg

这种方式实际上并没有本质提高,而且如果一些极端情况下会退化成一个链表,查找操作的复杂度反而上升了,上面的例子中就是这样。

查找和合并的时间复杂度都为O(h),h表示树高。

所以我们需要对合并操作进行优化,优化方式一般为以下两种。

按秩合并(union by rank)

秩(Rank)就是一颗树的结点数,即使包含较少结点的树根指向包含较多结点的树根。
所以上面的例子中union(1, 2)操作会让 2 节点会指向 1 。
批注 2019-10-08 010145.jpg

这样查找操作最坏情况的时间复杂度为O(logN)

路径压缩

在查找所在位置是我们会进行递归,那么我们可以利用递归回溯的过程进行路径压缩。所谓压缩表示的就是将从x结点搜索到祖先结点所经过的结点都指向该树的根节点结点。
DSU_path_compression.png

在压缩之后树的高度低了,所以查找复杂度也降低了。

同时使用按秩合并和路径压缩

复杂度为反阿克曼函数,具体的证明比较复杂,可以参科下面这篇讲义。
这里简单介绍下阿克曼函数,他表示f(n) = 2 ^2^2^…^2,可见其增长速度极快,其反函数用lg*n表示,其值可以认为小于5。

https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/UnionFind.pdf

批注 2019-10-08 010145.jpg
参考文章:
https://cp-algorithms.com/data_structures/disjoint_set_union.html
https://algs4.cs.princeton.edu/15uf/

子元素 diff 算法的优化

5a58d2b2bbd4b-min.jpg

React 的 Diff

React先遍历新数组来找到插入和需要移动的节点,为了避免不必要的移动,react使用了一个哨兵值lastIndex,记录访问过的源数组下标最大值,如果当前元素的下标小于lastIndex,表示原相对位置无法满足需要了需要移动,否则更新lastIndex,这样来最大限度地利用原相对位置。
最后遍历一遍旧数组找到需要删除的元素。

但这种方式并不是总能得到最优结果。

例如:'1234' ➔ '4123'
React 并没有将4移到最前面,而是将234都移动一次。因为对新数组的遍历是从左向右的依次进行,所以这种位置相对关系总是局部的。

Diff 的改进

缩小问题规模

首先考虑一种情况,我们只对字符串进行了一次插入或删除操作,其实是没有必要进行diff,我们通过匹配两个字符串的通用前缀/后缀,可以直接找出差异,即便字符串进行了多次插入删除,查找公共前后缀也能在一定程度上减小diff的计算量,因为使用二分搜索的时间复杂度是O(nlogn)。

例如下面的两个字符串的公共前缀为abc,后缀为g,可以直接去掉。

A: -> [a b c d e f g] <-
B: -> [a b c h f e g] <-

寻找最小的移动次数

diff 算法首先需要一个旧数组的索引{1:0,2:1,3:2,4:3},通过该索引计算出新数组的对应位置。然后计算数组索引的最长上升子序列,通常使用动态规划实现,具体不做展开。

A: [a b c d]
B: [d a b c]
P: [3 0 1 2]
LIS: [0 1 2]

然后我们自右向左遍历新数组和 LIS 序列,查看元素的位置是否能与 LIS 序列的任何一个值匹配,若匹配则位置无需移动,然后取前一个LIS值继续,否则将其移动到当前遍历新数组元素的前面。
如上面的例子中,中有遍历到第一位时才不匹配,所以将B[1]=d移动到A[1]=a的前面即可。

为什么LIS能够做到这一点,因为它在整体上保留了数组升序排列的相对位置。

参考文章:
https://www.zhihu.com/question/65824137
https://github.com/NervJS/nerv/issues/3

比较排序与计数排序时间复杂度的证明

比较排序

对于任意的比较排序算法,我们都能将其操作抽象成一颗决策树,这是一颗完全二叉树,它表示了某一排序算法对所有元素的比较操作。下图是插入排序的例子:
批注 2019-09-04 010631.jpg

每一条路径都是一种可能性,所以算法的最坏情况下的排序次数就是决策树的高度。

n个元素,可能的排序结果有A(n,n-1)=n!种,假设此时的树高为h,则叶子节点最多为2^(h+1)

2^(h+1) ≥ n!  
h + 1 ≥ log2(n!)

log(n!) = O(nlogn)

证明:

不等式缩放

log(n!) = log1 + ... + logn ≥ n/2 * log(n/2) = n/2 * logn - n/2 = c1 * logn
log(n!) = log1 + ... + logn ≤ nlogn = c2 * logn

Stirling 近似

76029ac06006a23f29011873c13a7a64541c6acd.svg

a35e8e0205988cf8552eec558d121f764d7e4021.svg

计数排序

计数排序的思想是:在待排序序列中,如果我们能统计出有多少元素小于或等于某一个元素,我们也就知道了该元素的正确位置。
例如:有五个元素小于x,那么就把x放到第六位(对于相同的元素我们认为最早遇到小于后面遇到的)。

实现该算法我们需要三个数组,初始input,结果output和表示元素统计数的count数组。
下面为算法的伪代码:

count = array of k+1 zeros
for x in input:
   count[key(x)] += 1

total = 0
for i in 0, 1, ... k:
   count[i], total = total, count[i] + total

output = array of the same length as input
for x in input:
   output[count[key(x)]] = x
   count[key(x)] += 1

return output

算法可视化

时间复杂度分析:假设在[0,k]的n个元素,数组初始化O(k),构造统计数组C是O(n),统计数累加O(k),排序是O(n)
所以总共时间复杂度为O(k+n)

计数排序是一种典型空间换时间的算法。

性能比较

下面是JS中的性能对比:

Array with 10000000 elements:
n log(n) takes 15.611 seconds
Linear takes 3.896 seconds

参考文章:
https://medium.com/free-code-camp/my-favorite-linear-time-sorting-algorithm-f82f88b5daa1

矩阵相乘的Strassen's算法

矩阵乘法的数学表达式为equation.png

对于两个n*n整数矩阵,相乘需要进行n^3次整数乘法和n^3-n^2次整数加法,显然时间复杂度为O(n^3)

我们先将问题简化,任意的矩阵乘法我们都可以转换为两个2x2的矩阵相乘。而这个2x2的矩阵乘法可以拆解为如下形式。
捕获.PNG

Strassen有(7/8)n^3次整数乘法和(7/8)n^3+(3/4)n^2+8次加法,而整数乘法运算时间大于加法。最终的时间复杂度为O(n*log2(7))

算法的核心思想是用更小规模的乘法来得到中间矩阵,最后加法汇总成需要的矩阵。

Introduction and Strassen’s Algorithm.pdf

JS 实现LRU缓存

为什么不直接用对象这种k-v结构,因为内存空间很宝贵而且是有限的。
在浏览器我们无所谓,但服务端就不一样了,例如nuxt就是用了LRU算法缓存接口数据或者渲染后的dom对象。

LRU(Least Recently Used)把最近没用过的一个置换出去,意思就是如果最近用到了就放到前面,如果不够了最后一个就是最近没使用的,将其删除掉就好。使用双链表就能满足这种需求。

/*
 * Illustration of the design:
 *
 *       entry             entry             entry             entry
 *       ______            ______            ______            ______
 *      | tail |.newer => |      |.newer => |      |.newer => | head |
 *      |  A   |          |  B   |          |  C   |          |  D   |
 *      |______| <= older.|______| <= older.|______| <= older.|______|
 *
 */
class Node {
    prev = null;
    next = null;
    constructor(k, v) {
        if (valid(k)) this.key = k;
        if (valid(v)) this.value = v;
    }

    valid(e) {
        return typeof key != "undefined" && key !== null
    }
}

class LRU {
    size = 0;
    head = null;
    tail = null;
    map = {};
    constructor(limit = 1000) {
        this.limit = limit
    }

    setHead(node) {
        node.next = this.head;
        node.prev = null;
        if (this.head !== null) this.head.prev = node;
        if (this.tail === null) this.tail = node;
        this.size++;
        this.map[node.key] = node;
    }

    set(k, v) {
        const node = new Node(k,v);
        if (this.map[key]) {
            this.map[key].value = node.value;
            this.remove(node.key);
        } else {
            if (this.size >= this.limit) {
                delete this.map[this.tail.key];
                this.size--;
                this.tail = this.tail.prev;
                this.tail.next = null;
            }
        }
        this.setHead(node);
    }

    get(k) {
        if (this.map[k]) {
            const value = this.map[k].value;
            const node = new Node(k, v);
            this.remove(k);
            this.setHead(node);
            return value;
        } else {
            console.log("Key " + k + " does not exist in the cache.")
        }
    }

    remove(key) {
        const node = this.map[key];
        if (node.prev !== null) {
            node.prev.next = node.next;
        } else {
            this.head = node.next;
        }
        if (node.next !== null) {
            node.next.prev = node.prev;
        } else {
            this.tail = node.prev;
        }
        delete this.map[key];
        this.size--;
    }
}

插入删除时间复杂度都是O(1)

现在为止我们实现了最为核心部分,但是缓存也不能无限的停留在内存中,像接口这些数据有时会发生改变,所以还需要为缓存加上有效期,在get时判断是否过期。

LRU能带给我们一定的收益,但是他也让我们的程序拥有了状态,也就不能做分布式来多实例负载均衡。