对于我的用例,我发现随着数组大小的增长,移位/切片方法对我的 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)
最佳答案
根据列出的操作判断,您正在寻找具有 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 包。
关于javascript - add、removeFirst、removeFirstN 数组操作的性能优化,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48889456/