关于javascript:为什么-shift-比-pop-慢JS-中队列的实现

咱们晓得在 JS 中，删除数组元素有两个办法：pop 与 shift，别离能够删除开端与结尾的元素。

然而同样是删除元素，它们的执行工夫的确不同的。

当数组我的项目较多时，shift 的执行工夫显著长于 pop。

const test = (arrLength) => {let arr1 = []
  console.time(`${arrLength}-arr1`)
  for (let i = 0; i < arrLength; i++) {arr1.push(i)
  }
  for (let i = 0; i < arrLength; i++) {arr1.pop()
  }
  console.timeEnd(`${arrLength}-arr1`)

  let arr2 = []
  console.time(`${arrLength}-arr2`)
  for (let i = 0; i < arrLength; i++) {arr2.push(i)
  }
  for (let i = 0; i < arrLength; i++) {arr2.shift()
  }
  console.timeEnd(`${arrLength}-arr2`)
}

test(10 ** 5)
test(10 ** 6)

后果如下：

这是因为 pop 删除元素后不须要扭转其余元素的索引，工夫复杂度为 O(1)；而调用 shift 办法删除结尾元素后，须要保护数组的索引，相当于对数组中的所有元素都进行了一次赋值操作，其工夫复杂度为 O(n)

栈与队列是咱们罕用的两种数据结构。

栈的元素先进后出，比方函数栈，函数递归调用时，后调用的函数先执行完。

队列的元素先进先出，比方工作队列，工作依照派发的程序顺次执行。

在 JS 中，栈能够看成只调用 push 与 pop 办法的数组，队列能够看成是只调用 shift 与 push 办法的数组。

然而在之前的例子中也看到了，当解决大量数据时，把数组间接当成队列使用性能十分差。

所以，咱们要设法实现队列这一数据结构。

开始之前咱们要明确实现的指标，咱们实现的队列要提供以下几个性能：

存储数据：队列要可能按序存储数据
push：增加元素的惟一办法，将元素增加进队列尾部的办法，并返回队列长度
shift：删除元素的惟一办法，将队首元素删除的办法，并返回删除的元素
length：能够通过 length 属性拜访队列的长度
拜访元素：个别队列会容许访问队头与队尾的元素

这里介绍通过 假删除数组元素 的形式实现队列。

咱们晓得数组的不能当作队列应用的起因是间接应用 shift 删除元素后会挪动其余元素的索引。

咱们能够本人保护数组的索引，防止删除后频繁挪动。

具体实现是定义一个 offset 变量，记录索引的偏移。

在拜访元素时，通过偏移量的计算，获取正确的后果。

在删除元素时，只用把数组首元素置空，而后偏移加 1。

这期间不进行实在的删除操作，这就是所谓的 假删除。

但为了防止数组大小有限增大，咱们设置当偏移量 (空元素) 大于数组的长度的一半时，就将空元素删除，保障占用空间不超过应用队列大小的两倍。

具体实现代码及正文如下

// 创立一个队列
function createQueue() {const arr = [] // 外部的数组
  let offset = 0 // 偏移

  // 增加元素，返回队列的长度
  const push = (...arg) => {return arr.push(...arg) - offset
  }
  // 删除元素，返回被删除的元素
  const shift = () => {const res = arr[offset] // 要返回的删除元素
    // 假删除
    arr[offset] = undefined
    offset++

    // 防止数组有限扩充，定期一次性删除后面的空元素
    if (offset > arr.length / 2) {arr.splice(0, offset)
      offset = 0
    }

    return res
  }

  // 通过 Proxy 拦挡队列的操作
  const p = new Proxy({},
    {get(target, prop) {switch (prop) {
          case 'push': {return push}
          case 'shift': {return shift}
          case 'length': {
            // 队列长度 = 数组理论长度 - 偏移
            return arr.length - offset
          }
          default: {
            // 元素实在索引 = 要拜访的索引 + 偏移
            return arr[Number(prop) + offset]
          }
        }
      },
    }
  )

  return p
}

const queue = createQueue()

console.log(queue.push(0, 1, 2, 3, 4)) // 5
console.log(queue[0]) // 0
console.log(queue.length) // 5

console.log(queue.shift()) // 0
console.log(queue[0]) // 1
console.log(queue.length) // 4

console.log(queue.shift()) // 1
console.log(queue.push(5)) // 4
console.log(queue[0]) // 2
console.log(queue[queue.length - 1]) // 5

进行 10/100/1000 万次增删操作，测试队列的性能

const test = (arrLength) => {let arr1 = []
  console.time(`${arrLength}-arr1`)
  for (let i = 0; i < arrLength; i++) {arr1.push(i)
  }
  for (let i = 0; i < arrLength; i++) {arr1.pop()
  }
  console.timeEnd(`${arrLength}-arr1`)

  let arr2 = createQueue()
  console.time(`${arrLength}-arr2`)
  for (let i = 0; i < arrLength; i++) {arr2.push(i)
  }
  for (let i = 0; i < arrLength; i++) {arr2.shift()
  }
  console.timeEnd(`${arrLength}-arr2`)
}

test(10 ** 5)
test(10 ** 6)
test(10 ** 7)

function createQueue() {……}

测量后果如下：

能够看出，不论数据多大，性能也只差 4 倍。

因为要进行操作的拦挡与索引偏移的计算，分外的性能开销不可避免，常数倍的性能差距曾经能够满足要求。

如果文中有不了解或不谨严的中央，欢送评论发问。

如果喜爱或有所启发，心愿能点赞关注，激励一下作者。

关于javascript:为什么-shift-比-pop-慢JS-中队列的实现

栈与队列

如何实现？

测试性能

结语