矩阵相乘的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能带给我们一定的收益,但是他也让我们的程序拥有了状态,也就不能做分布式来多实例负载均衡。

基于布隆过滤器的依赖注入

如果你读过Shadowsocks或者Angular的代码,你会发现他里面都自己实现了一个布隆过滤器。
SS用他来匹配GFW名单,Angular中用来依赖注入服务名单。NodeInjector是Ivy渲染器引入的Angular注入器,它大量使用bloom过滤器来检索令牌。

Bloom过滤器的基本数据结构是位向量。

Bloom Filter原理:当一个元素被加入集合时,通过K个Hash函数将这个元素映射成一个位阵列(Bit array)中的K个点,把它们置为1。检索时,我们只要看看这些点是不是都是1就(大约)知道集合中有没有它了:如果这些点有任何一个0,则被检索元素一定不在;如果都是1,则被检索元素很可能在。

Angular中的bloom比特位为256,因此我们有一个256位的向量,它被分成8个部分。

Angular 通过递增整数值生成(如果尚未定义)令牌的唯一ID,并将其置于静态__NG_ELEMENT_ID__属性。
它通过按位AND(&)运算符获取该数字并使其适合bloom大小,以便结果始终在0-255之间。

// 用原始 bloomBit 值决定检查那个 bloom 过滤器桶
// e.g: bf0 = [0 - 31], bf1 = [32 - 63], bf2 = [64 - 95], bf3 = [96 - 127], etc
const b7 = bloomBit & 0x80;
const b6 = bloomBit & 0x40;
const b5 = bloomBit & 0x20;
const tData = tView.data as number[];

if (b7) {
  b6 ? (b5 ? (tData[injectorIndex + 7] |= mask) : (tData[injectorIndex + 6] |= mask)) :
       (b5 ? (tData[injectorIndex + 5] |= mask) : (tData[injectorIndex + 4] |= mask));
} else {
  b6 ? (b5 ? (tData[injectorIndex + 3] |= mask) : (tData[injectorIndex + 2] |= mask)) :
       (b5 ? (tData[injectorIndex + 1] |= mask) : (tData[injectorIndex] |= mask));
}

代码都是位运算,看起来挺复杂,其实就是将2^bloomBit位置为1。下面是一个简单例子:

const bloomBit = 3 % 255 // 3
const mask = 1 << bloomBit;
             1 << 3 // 8
8..toString(2) // 1000
                           
1 bucket          00000000000000000000000000001000
....
8 bucket          00000000000000000000000000000000    

next_permutation 算法原理和JS实现

C++ STL中的 next_permutation 函数和 prev_permutation 两个函数提供了对于一个特定排列P,求出其后一个排列P+1和前一个排列P-1的功能。

我们假设一个序列Pn=<3 6 4 2>,我们可以从右起第一位看成各位,第二位为十位以此类推,那么很容易得出递减序列表示的数最大,这个例子中<6 4 2>为递减,已经无法通过交换数字位置得到更大的数,所以我们找到第一个非递减元素3,然后从前面递减序列中找到第一个大于它的元素4,交换着两个元素得到<4 6 3 2>,但是这里<6 3 2>仍是递减,而我们需要以4开头的最小序列,所以我们还要将递减序列颠倒成递增序列,最终得到Pn+1=<4 2 3 6>。

算法步骤如下:

  • 从尾端向前,找到两个相邻元素 i < (i+1)
  • 再从尾端向前,找到第一个元素满足 j > i
  • swap(i, j), 然后把 i+1 之后的所有元素 reverse 倒排
#include<cstdio>
#include<cstring>

void inline swap(char *s1,char *s2){
    char t=*s1;*s1=*s2;*s2=t;
}

//反转字符串函数,s,e分别执行字符串的开始和结尾
void reverse(char *s,char *e){
    for(e--;s<e;s++,e--)swap(s,e);
}

bool next_permutation(char *start,char *end){
    char *cur = end-1, *pre=cur-1;
    while(cur>start && *pre>=*cur)cur--,pre--;
    if(cur<=start)return false;
    
    for(cur=end-1;*cur<=*pre;cur--);//找到逆序中大于*pre的元素的最小元素 
    swap(cur,pre);
    reverse(pre+1,end);//将尾部的逆序变成正序 
    return true;
}

JS实现:

function next_permutation( arr ) {
    const length = arr.length;
    if( length <=1 ) return false;
    
    let i = length;
    while(true){
        var t = i;
        i--;
        if( arr[ i ] < arr[ t ] ) {
            var j = length;
            while( !( arr[ i ] < arr[ --j ] ) );

            const temp = arr[ i ];
            arr[ i ] = arr[ j ];
            arr[ j ] = temp;
            
            // splice()函数做了两件事,首先将arr的t以后的元素移除,并且将移除的部分颠倒后保存在rev中
            var rev = arr.splice( t, length ).reverse();

            // 将后面颠倒后的部分连接至arr,这里不能用concat()来连接,否则改变的就不是原来的arr了
            Array.prototype.push.apply( arr, rev );
            return true;
        }
        if(!i){
            arr.reverse();
            return false;
        }
    }
}

红黑树

红黑树在C++的STL中很广泛,例如map和set都是用红黑树实现的,此外还大量应用在Linux系统中。所以有必要深入了解下。

定义

红黑树是每个节点都带有颜色属性的二叉查找树,颜色为红色或黑色。在二叉查找树的基础上增加了以下要求:

  • 节点是红色或黑色。
  • 根是黑色。
  • 所有叶子都是黑色(叶子是NIL节点)。
  • 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
  • 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

插入

先把结点标记为红色,再按二叉查找树的方法插入,最后再根据红黑树的要求进行调整。
所以我们根据插入后被破坏的红黑树性质进行分情况讨论。

  1. 被插入节点是根结点直接涂黑
  2. 被插入节点的父根结点为黑色,那么插入后的新树仍然是一棵红黑树
  3. 被插入的节点的父节点是红色,那么我们调整的最终目标是将这两个红色层层上移动,最终通过旋转将其中一个红色移动到最顶端,然后将其涂黑(注意不节点移动,只是颜色自下而上传递)

Case 1 当前节点的父节点是红色,且当前节点的祖父节点的另一个子节点(叔叔节点)也是红色。
(01) 将“父节点”设为黑色。
(02) 将“叔叔节点”设为黑色。
(03) 将“祖父节点”设为“红色”。
(04) 将“祖父节点”设为“当前节点”(红色节点);即,之后继续对“当前节点”进行操作。

Case 2 当前节点的父节点是红色,叔叔节点是黑色,且当前节点是其父节点的右孩子
(01) 将“父节点”作为“新的当前节点”。
(02) 以“新的当前节点”为支点进行左旋。

Case 3 当前节点的父节点是红色,叔叔节点是黑色,且当前节点是其父节点的左孩子
(01) 将“父节点”设为“黑色”。
(02) 将“祖父节点”设为“红色”。
(03) 以“祖父节点”为支点进行右旋。

为何将插入节点置为红色?
选黑色不是不可以,调整嘛,最终总是能符合定义。首先我们插入操作对之前的红黑树造成的破坏只可能有2.4.5,当我们选择红色的时候永远不会违反性质5,所以置为红色比黑色要简单。

与AVL树比较

  1. 如果插入引起了树的不平衡,AVL和红黑树都是最多只需要2次旋转操作,即两者都是O(1);但是在删除引起树的不平衡时,最坏情况下,AVL需要维护从被删节点到根这条路径上所有节点的平衡性,因此需要旋转的量级O(logN),而红黑最多只需3次旋转,只需要O(1)的复杂度。
  2. AVL的结构相较RB-Tree来说更为平衡,所以在插入和删除node更容易造成不平衡,因此在大量数据需要插入或者删除时红黑树效率更高。