Javascript 为什么 pop 比 shift 快？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/6501160/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Why is pop faster than shift?
提问by zjmiller
Douglas Crockford, in JavaScript: The Good Parts, states that "shift is usually much slower than pop". jsPerf confirms this. Does anyone know why this is the case? From an unsophisticated point of view, they seem to be doing pretty much the same thing.
Douglas Crockford 在JavaScript: The Good Parts中指出“shift 通常比 pop 慢得多”。jsPerf证实了这一点。有谁知道为什么会这样？从简单的角度来看，他们似乎在做几乎相同的事情。
回答by geekosaur
To remove the returned item without re-addressing the array and invalidating all references to it, shift()requires moving the entire array around; pop()can simply subtract 1 from its length.
要删除返回的项目而不重新寻址数组并使对其的所有引用无效，shift()需要移动整个数组；pop()可以简单地从其长度中减去 1。
回答by Andrew Moore
shift()has to re-index the whole array while pop()doesn't.
shift()必须重新索引整个数组，而pop()不必重新索引。
pop()simply removes the last element in the array. Therefore, the elements do not move; simply the .lengthhas to be updated.
pop()简单地删除数组中的最后一个元素。因此，元素不会移动；只是.length必须更新。
shift()removes the first element in the array. This requires a re-indexing of all elements in the array, so that [1]becomes [0]and so on.
shift()删除数组中的第一个元素。这需要在阵列中的所有元件的重新索引，以便[1]变成[0]等。
回答by bhirt
I was doing some tests on this with node (which uses chrome v8) and noticed that for arrays up to around 120k elements the performance of shift is pretty close to pop. Once you get bigger than 120K it seems to slow down dramatically.
我正在使用 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);
});
Output:
输出：
{"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
回答by hungnt
Because shift() reindex array so the shift method is very slow on large array.
因为 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 minutesBut the duration is just 8ms when using linked-queue
但是使用链接队列时的持续时间仅为 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);回答by Pacerier
The difference can be negligible—Unoptimized executors may run shiftmuch slower than pop, but optimized ones won't.
差异可以忽略不计——未优化的执行程序运行shift速度可能比 慢得多pop，但优化的执行程序不会。
You can optimize like this:
你可以这样优化：
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*/)
回答by Mikola
If you shift, you have copy all the elements in the array backwards. To pop, you only need to decrement the length of the array. Technically, an implementation could get around this, but you would need to store an extra `shift' variable that tells you where the real start of the array is. However, this type of operation has not proven to be very useful in practice and so most implementations save space by only storing a start of array pointer and a length value.
如果您移动，您将向后复制数组中的所有元素。要弹出，您只需要减少数组的长度。从技术上讲，一个实现可以解决这个问题，但是你需要存储一个额外的“shift”变量，它告诉你数组的真正开始在哪里。然而，这种类型的操作在实践中并没有被证明非常有用，因此大多数实现通过只存储数组指针和长度值来节省空间。
