为什么pop比shift快
Why is pop faster than shift?
Douglas Crockford在JavaScript:The Good Parts中指出,"shift通常比pop慢得多"。jsPerf证实了这一点。有人知道为什么会这样吗?从一个简单的角度来看,他们似乎在做几乎相同的事情。
要删除返回的项而不重新寻址数组并使对它的所有引用无效,shift()
需要移动整个数组;CCD_ 2可以简单地从其长度中减去1。
shift()
必须重新索引整个数组,而pop()
则不需要。
pop()
只是简单地移除数组中的最后一个元素。因此,元素不会移动;只是CCD_ 6必须被更新。
CCD_ 7移除阵列中的第一个元素。这需要重新索引数组中的所有元素,使[1]
变为[0]
,依此类推
我用node(使用chrome v8)对此进行了一些测试,并注意到对于多达120k个元素的数组,shift的性能非常接近pop。一旦你的体重超过120K,它似乎会急剧下降。
var sum;
var tests = [125000,130000];
console.log(JSON.stringify(process.versions));
tests.forEach(function(count) {
console.log('Testing arrays of size ' + count);
var s1 = Date.now();
var sArray = new Array(count);
var pArray = new Array(count);
for (var i = 0; i < count ; i++) {
var num = Math.floor(Math.random() * 6) + 1
sArray[i] = num;
pArray[i] = num;
}
console.log(' -> ' + (Date.now() - s1) + 'ms: built arrays with ' + count + ' random elements');
s1 = Date.now();
sum = 0;
while (pArray.length) {
sum += pArray.pop();
}
console.log(' -> ' + (Date.now() - s1) + 'ms: sum with pop() ' + count + ' elements, sum = ' + sum);
s1 = Date.now();
sum = 0;
while (sArray.length) {
sum += sArray.shift();
}
console.log(' -> ' + (Date.now() - s1) + 'ms: sum with shift() ' + count + ' elements, sum = ' + sum);
});
输出:
{"http_parser":"1.0","node":"0.10.22","v8":"3.14.5.9","ares":"1.9.0-DEV","uv":"0.10.19","zlib":"1.2.3","modules":"11","openssl":"1.0.1e"}
Testing arrays of size 125000
-> 14ms: built arrays with 125000 random elements
-> 2ms: sum with pop() 125000 elements, sum = 436673
-> 6ms: sum with shift() 125000 elements, sum = 436673
Testing arrays of size 130000
-> 50ms: built arrays with 130000 random elements
-> 1ms: sum with pop() 130000 elements, sum = 455971
-> 54372ms: sum with shift() 130000 elements, sum = 455971
因为shift()重新索引了数组,所以shift方法在大数组上非常慢。
var array = [];
for(var i = 0;i< 1000000;i++){
array.push(i)
}
var start = new Date().getTime()
for(var i = 0; i< 100000; i++){
array.shift();
}
var duration = new Date().getTime() - start;// duration is so large, greater than 3 minutes
但使用链接队列时,持续时间仅为8ms
var LQueue = require('linked-queue')
var queue = new LQueue()
for(var i = 0;i< 1000000;i++){
queue.enqueue(i);
}
console.log("Queue length:"+ queue.length);
var start = new Date().getTime()
queue.dequeueAll(function(data){
})
var end = new Date().getTime();
console.log("Time:" + (end - start));// 8 ms
console.log("Queue length:"+ queue.length);
差异可以忽略不计—未优化的执行器运行shift
的速度可能比pop
慢得多,但优化的执行程序不会。
你可以这样优化:
let WrapArray = _=>{
//Ensure no other ref to `_`.
let numlike = _=>isNaN(_)?false:true
let num = _=>Number(_)
{
let shift_q = 0
return new Proxy(_, {
get(first_t, k){
switch(k){
case 'shift': return (z={})=>(z.r=first_t[0 + shift_q], delete first_t[0 + shift_q++], z.r)
break; case 'length': return first_t.length - shift_q
break; default: return first_t[numlike(k)?num(k) +/*todo overflowguard*/shift_q:k]
}
},
set(first_t, k, v){
switch(k){
case 'length': first_t.length = v + shift_q
break; default: first_t[numlike(k)?num(k) +/*todo overflowguard*/shift_q:k] = v
}
},
has(first_t, k){
return (numlike(k)?num(k) +/*todo overflowguard*/shift_q:k) in first_t
},
deleteProperty(first_t, k){
delete first_t[numlike(k)?num(k) +/*todo overflowguard*/shift_q:k];return 543
},
apply(first_t, t, s){
first_t.call(t, s)
},
construct(first_t, s, t){
new first_t(...s)
},
})
}
}
(_=WrapArray(['a','b','c'])).shift()
console.log(_.length/*2*/, _[0]/*b*/, _[1]/*c*/, _[2]/*undefined*/)
如果进行移位,则必须向后复制数组中的所有元素。要弹出,您只需要减少数组的长度。从技术上讲,一个实现可以绕过这一点,但您需要存储一个额外的"shift"变量,该变量"告诉"您数组的真正起始点在哪里。然而,这种类型的操作在实践中并没有被证明是非常有用的,因此大多数实现只存储数组指针的起始点和长度值来节省空间。
相关文章:
- 我想使用模态通过php文件发送邮件,并且我希望在提交关闭后关闭pop
- 防止Alt+Shift默认操作或检测多种操作系统语言的Javascript
- 如何通过documents.ready函数中的javascript自动按键(ctrl+shift+i)
- array.shift()只删除一半数组
- 如何通过按Enter提交输入表格,但在按shift和Enter时不提交
- 如何模拟shift/ctrl/alt键状态
- .pop() 可以用于 JavaScript 中的对象数组吗?
- Shift+选项+命令+左键单击的事件
- 如何检测 shift 键是否在操作时关闭
- 未捕获的类型错误:无法调用方法'shift'Chrome中的Facebook JS库为null
- shift鼠标点击触发器
- 使用forEach和.shift()时结果不一致
- 如何在jquery中获取shift+mousescroll事件
- 如何禁用angularjs中的shift+任意键组合
- text使用shift键和箭头键时的区域插入符号位置
- Javascript-仅使用pop()方法删除数组中的负值
- Javascript shift()总是返回0
- Javascript display(); no showing pop, push, unshift, shift?
- Javascript SHIFT和POP上的关联数组
- 为什么pop比shift快