javascript - add、removeFirst、removeFirstN 数组操作的性能优化

Question

对于我的用例，我发现随着数组大小的增长，移位/切片方法对我的 CPU 造成了太多压力。理论上，该数组可能有 86400 个项目那么大，尽管通常它会小得多——大约 10000 个数组元素。

我试图用一个简单的例子来说明它。想象一下这是一个非常大的规模。它会正常运行直到某个点，但通常像这样删除第一个(或前 n 个)项目似乎非常无效。

希望对“为什么会这样”有更多了解的人可以填写以下代码段中的 3 个函数中的一个或多个:

• 添加()
• removeFirst()
• 移除第N个(n)

不变性在这里行不通 - 或者更确切地说，由于我们追求最佳性能，因此复制不断增长且相当大的数据结构(在本例中为数组)绝对行不通。

有什么好的建议吗？ :-)

let objArray = []
let maxCount = 10;
let i = 0;

function add(){
  objArray.push({x: + new Date(), y: Math.floor(Math.random() * 10000) + 1});
  console.log("add")
}

function removeFirst(){
  objArray.shift();
  console.log("removeFirst")
}

function removeFirstN(n){
  objArray.splice(0,n)
  console.log(`removeFirstN(${n})`)
}

// Every second and obj is added to the array
setInterval(function(){
  if(objArray.length === maxCount){
    removeFirst();
  } else if(objArray.length > maxCount) { // this is possible since we're allowed to change maxCount
    const diff = objArray.length+1 - maxCount;
    removeFirstN(diff);
  }
  // Always add
  add();
  
  i++;
  
  if(i === 15) {
    maxCount--;
    i = 0;
  }
  
  console.log(`length: ${[...objArray].length}`)
  console.log([...objArray])
}, 1000)

Answer 1

根据列出的操作判断，您正在寻找具有 constant-time 的队列入队和出队。当您通过在一侧移动所有元素进行操作来将数组用作队列时，该操作所花费的时间与数组中的元素数量成正比。当元素数量变大时，基于循环缓冲区或链表(均满足恒定时间要求)的实现将更快。

链接列表非常简单，可以在帖子中进行演示:

class LinkedQueue {
    constructor() {
        this.head = null;
        this.tail = null;
    }

    enqueue(value) {
        const node = {value, next: null};

        if (this.tail === null) {
            // Empty queue; make this the only node
            this.tail = this.head = node;
        } else {
            // Make this the successor of the current last node,
            // then make it the new last node
            this.tail = this.tail.next = node;
        }
    }

    dequeue() {
        const result = this.head.value;

        if (this.head === this.tail) {
            // Last element remaining
            this.head = this.tail = null;
        } else {
            // Remove the first element
            this.head = this.head.next;
        }

        return result;
    }
}

但为了在实践中获得最佳性能，您需要使用基于循环缓冲区的队列。 double-ended-queue就是这样一个 npm 包。