前端

这篇笔记记录了如何通过利用JavaScript编码原则和算法优化来改进JavaScript代码。

一、本堂课重点内容

  • 判断一段JavaScript代码是否是好代码不能仅从代码本身的书写风格来看
  • 利用JavaScript的编码原则（各司其责、组件封装、过程抽象）
  • 在算法层面优化代码

二、详细知识点介绍

1、代码“不可貌相”

  • 有这样一段代码：
function isUnitMatrix2d(m){
    return m[0] === 1 && m[1] === 0 && m[2] === 0 && m[3] === 1 && m[4] === 0 && m[5] === 0;
}

这段代码的作用是判断一个mat2d矩阵是否是单位矩阵。单从代码风格上来看，大部分人会认为这并不是一段好代码，因为它看起来很冗长，或是复用性差等等。但是这实际上是一段真实的代码，出自spritejs/layer.js。使用这一段代码的原因是为了追求高性能，而避免了使用for循环增加时间复杂度。因此，评判一段代码是否优秀，要综合考虑使用场景、效率等多方面因素。

2、LeftPad事件

  • Leftpad模块被作者从npm上撤下导致了所有直接或间接依赖它的模块都受到了影响。Leftpad关键部分源码如下：
function leftpad(str, len, ch) {
    str = String(str);
    var i = -1;
    if (!ch && ch !== 0) ch = ' ';
    len = len - str.length;
    while (++i < len) {
        str = ch + str;
    }
    return str;
}
  • 有人指出，这一段代码不够完美，因为其时间复杂度为O(n)
  • 有人提出了一种时间复杂度更小、代码更简洁的方案
function leftpad(str, len, ch) {
    str = "" + str;
    const padLen = len - str.length;
    if(padLen <= 0){
        return str;
    } else{
        return ("" + ch).repeat(padLen) + str;
    }
}
  • 上面这段代码的关键在于使用了repeat()方法，这个方法利用快速幂的思想，使得其时间复杂度为O(logn)。关键部分代码如下：
for(;;){
    if((count & 1) == 1) {
        rpt += str;
    }
    count >>>= 1;
    if (count == 0) {
        break;
    }
    str += str;
}
  • 快速幂算法：
    • 将幂指数写成二进制的形式，例如$2^{6}$，可以写成$2^{(110)_2} = 2^{(100)_2}·2^{(10)_2}$。对于任意整数都可以拆成诸如$2^{(100...)_2}$的形式相乘，而乘数只需要不断把底数平方就可以得出。

3、判断是否为4的幂

  • Leetcode上有一种很巧妙的解法：
function isPowerOfFour(num){
    num = parseInt(num);
    return num > 0 &&
        (num & (num - 1)) === 0 &&
        (num & 0xAAAAAAAA) === 0;
}
  • 这个题解的思路如下：
    • 首先这个数肯定大于0
    • 其次，一个数是4的幂则一定是2的幂。对于一个n位二进制数m，如果其第k位为1，且第k+1~n位均为0，则m&(m-1)得到的结果的前k-1位不变，k~n位全为0。一个数num如果是2的幂，则其二进制的第一位为0，后面的位均为0，因此(num&(num-1)) === 0可以判断这个数是不是2的幂
    • (num & 0xAAAAAAAA)的作用是取出二进制数的偶数位。对于一个为4的幂的数来说，其最高位的1处在奇数位（例如$4=(100)_2$，$16=(10000)_2$），而仅为2的幂不为4的幂的数的最高位的1处在偶数位上，因此(num & 0xAAAAAAAA) === 0可以在上一步的基础上判断是否为4的幂

4、洗牌算法

  • 使用sort()方法洗牌导致的后果是排在前面的元素打乱后出现在前面的概率依然很高
  • 标准的一种洗牌方法，其思路是每次从未打乱的部分等可能地选一个元素，把它与未打乱部分的最后一个元素交换，保证洗牌后每张牌出现在每一个位置的概率相同
const cards = [0, 1, 2, 3, 4];
function shuffle(cards) {
    const c = [...cards];
    for (let i = c.length; i > 0; i--) {
        const pIdx = Math.floor(Math.random() * i);
        [c[pIdx], c[i - 1]] = [c[i - 1], c[pIdx]];
    }
    return c;
}
  • 证明该算法的正确性：
    • 假如有一个长度为n的数组$[a_1, a_2, ..., a_n]$。现在任选一个元素放在位置n上，每一个元素有$\frac 1 n$的概率被选中
    • 位置n固定后，再从前n-1个元素中任选一个放在位置n-1上；此时，每一个元素上一轮没有被选中的概率为$\frac {n-1} n$，这一轮被选中的概率为$\frac 1 {n-1}$，相乘得$\frac {n-1} n * \frac 1 {n-1} = \frac 1 n$
    • 以此类推，每个元素出现在每一个位置上的概率均为$\frac 1 n$

5、分红包

  • 切割法
function generate(amount, count){
    let ret = [amount];
    while(count > 1){
        // 挑选最大的一块进行切分
        let cake = Math.max(...ret),
            idx = ret.indexOf(cake),
            part = 1 + Math.floor((cake / 2) * Math.random()),
            rest = cake - part;
        ret.splice(idx, 1, part, rest);
        count--;
    }
    return ret;
}
  • 栅栏法（随机生成一些数值，插入到对应的位置，每次计算插值之间差作为红包的大小，保证红包数值分布不均匀）
function * draw(cards){
  const c = [...cards];

  for(let i = c.length; i > 0; i--) {
    const pIdx = Math.floor(Math.random() * i);
    [c[pIdx], c[i - 1]] = [c[i - 1], c[pIdx]];
    yield c[i - 1];
  }
}

function generate(amount, count){
  if(count <= 1) return [amount];
  const cards = Array(amount - 1).fill(0).map((_, i) => i + 1);
  const pick = draw(cards);
  const result = [];
  for(let i = 0; i < count; i++) {
    result.push(pick.next().value);
  }
  result.sort((a, b) => a - b);
  for(let i = count - 1; i > 0; i--) {
    result[i] = result[i] - result[i - 1];
  }
  return result;
}

三、实践练习例子：

  • 均已在上一节中列出

四、课后个人总结：

  • 书写代码时，要尽可能地考虑到时间、空间复杂度和代码规范程度，利用高性能算法，才能写出执行效率高、可读性强的代码

五、引用参考：