关于javascript:JavaScript的队列优化shift和pop

最近在看 webpack 的源码, 发现 webpack 封装的 ArrayQueue 类中, 实现的出队列办法 dequeue 在数组长度大于 16 时, 采纳 reverse+pop 来代替 shift.

dequeue() {if (this._listReversed.length === 0) {if (this._list.length === 0) return undefined;
        if (this._list.length === 1) return this._list.pop();
        if (this._list.length < 16) return this._list.shift();
        const temp = this._listReversed;
        this._listReversed = this._list;
        this._listReversed.reverse();
        this._list = temp;
    }
    return this._listReversed.pop();}

benchmark 测试

采纳 benchmark 进行两种形式的性能测试.

const Benchmark = require("benchmark");
const suite = new Benchmark.Suite();
suite
  .add("shift", function () {let arr = [];
    for (let i = 0; i < 100000; i++) {arr[i] = i;
    }
    let length = arr.length;
    for (let i = 0; i < length; i++) {arr.shift();
    }
  })
  .add("reverse-pop", function () {let arr = [];
    for (let i = 0; i < 100000; i++) {arr[i] = i;
    }
    let length = arr.length;
    arr.reverse();
    for (let i = 0; i < length; i++) {arr.pop();
    }
  })
  .on("cycle", function (event) {console.log(String(event.target));
  })
  .on("complete", function () {console.log("Fastest is" + this.filter("fastest").map("name"));
  })
  .run({async: true});

当数组长度是 10 时, 测试后果:

shift x 12,899,872 ops/sec ±1.55% (88 runs sampled)
reverse-pop x 14,808,207 ops/sec ±1.31% (92 runs sampled)
Fastest is reverse-pop

当数组长度是 1000 时, 测试后果:

shift x 13,518 ops/sec ±1.42% (88 runs sampled)
reverse-pop x 117,351 ops/sec ±1.03% (85 runs sampled)
Fastest is reverse-pop

当数组长度是 100000 时, 测试后果:

shift x 1.02 ops/sec ±5.80% (7 runs sampled)
reverse-pop x 523 ops/sec ±3.62% (84 runs sampled)
Fastest is reverse-pop

当数组长度越大, 两种形式的性能差距越大.

起因查找

shift 办法每次调用时, 都须要遍历一次数组, 将数组进行一次平移, 工夫复杂度是 O(n). 而 pop 办法每次调用时, 只需进行最初一个元素的解决, 工夫复杂度是 O(1).

具体可参考 ECMAScript language specification 中对于 Array.prototype.shift() 和 Array.prototype.pop() 介绍.