H5W3
当前位置:H5W3 > JavaScript > 正文

【JS】JavaScript的队列优化-shift和pop

JavaScript的队列优化-shift和pop

overfly发布于 今天 04:56

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

javascript
阅读 16发布于 今天 04:56
本作品系原创,采用《署名-非商业性使用-禁止演绎 4.0 国际》许可协议
avatar

overfly
1 声望
0 粉丝

0 条评论
得票时间

avatar

overfly
1 声望
0 粉丝

宣传栏

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

本文地址:H5W3 » 【JS】JavaScript的队列优化-shift和pop

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址