Дуглас Крокфорд, в JavaScript: The Good Parts, утверждает, что "сдвиг обычно намного медленнее, чем поп". jsPerf подтверждает это. Кто-нибудь знает, почему это так? С несложной точки зрения, похоже, они делают почти то же самое.
Почему поп быстрее, чем сдвиг?
Ответ 1
Чтобы удалить возвращенный элемент без повторной адресации массива и аннулирования всех ссылок на него, shift()
требует перемещения всего массива; pop()
может просто вычесть 1 из его длины.
Ответ 2
shift()
должен повторно индексировать весь массив, а pop()
- нет.
pop()
просто удаляет последний элемент в массиве. Поэтому элементы не перемещаются; просто нужно обновить .length
.
shift()
удаляет первый элемент в массиве. Это требует повторной индексации всех элементов в массиве, так что [1]
становится [0]
и т.д.
Ответ 3
Я делал некоторые тесты на этом с помощью node (который использует chrome v8) и заметил, что для массивов размером до 120 тыс. элементов производительность сдвига довольно близка к поп-музыке. Как только вы получите больше 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
Ответ 4
Потому что shift() reindex массив, поэтому метод сдвига очень большой на большом массиве.
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
Ответ 5
Если вы сдвигаетесь, вы копируете все элементы массива назад. Для поп вам нужно только уменьшить длину массива. Технически реализация может обойти это, но вам нужно будет сохранить дополнительную переменную `shift ', которая сообщит вам, где находится реальный старт массива. Однако этот тип операции не очень полезен на практике, поэтому большинство реализаций экономят пространство, сохраняя только начало указателя массива и значение длины.
Ответ 6
Разница может быть пренебрежимо малой: неоптимизированные исполнители могут работать 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*/)