Почему поп быстрее сдвига?

Question

Дуглас Крокфорд, в JavaScript: The Good Parts , утверждает, что «сдвиг обычно намного медленнее, чем поп». jsPerf подтверждает это . Кто-нибудь знает, почему это так? С неискушенной точки зрения они, кажется, делают почти одно и то же.

Answer 1

Чтобы удалить возвращенный элемент без повторной адресации массива и аннулирования всех ссылок на него, shift() требует перемещения всего массива; pop() может просто вычесть 1 из его длины.

Answer 2

shift() должен переиндексировать весь массив, а pop() - нет.

pop() просто удаляет последний элемент в массиве. Поэтому элементы не двигаются; просто .length должен быть обновлен.

shift() удаляет первый элемент в массиве. Это требует переиндексации всех элементов в массиве, так что [1] становится [0] и т. Д.

Answer 3

Я проводил некоторые тесты на этом узле (который использует Chrome v8) и заметил, что для массивов размером до 120 тыс. Элементов производительность shift довольно близка к популярности.Как только вы наберете больше 120 КБ, оно, похоже, резко замедлится.

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

Answer 4

Потому что 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

Но при использовании связанной очереди длительность составляет всего 8 мс

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);

Answer 5

Разница может быть незначительной - неоптимизированные исполнители могут работать 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*/)

Answer 6

Если вы сдвигаете, вы должны копировать все элементы в массиве в обратном направлении. Чтобы выскочить, вам нужно только уменьшить длину массива. Технически реализация могла бы обойти это, но вам нужно было бы хранить дополнительную переменную `shift ', которая сообщает вам, где находится реальное начало массива. Тем не менее, этот тип операции не оказался очень полезным на практике, и поэтому большинство реализаций экономят пространство, сохраняя только указатель начала массива и значение длины.