【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()介绍.

以上是 【JS】JavaScript的队列优化-shift和pop 的全部内容, 来源链接: www.h5w3.com/113576.html

回到顶部