最近在看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()介绍.