Performance optimizations for add, removeFirst, removeFirstN array operations

Question

For my use case I've found that the shift/slice methods are stressing my CPU way too much, as the array grows in size. In theory the array could be as big as 86400 items, although usually it would much lower - around 10000 array elements.

I've tried to illustrate it with a simple example. Imagine this at a very large scale. It'll run decently up until a point, but generally it seems highly ineffective to remove the first (or first n) item(s) like this.

Hopefully somebody with more knowledge in "why that is", can fill out one or more of the 3 functions in the snippet below:

add()
removeFirst()
removeFirstN(n)

Immutability won't work here - or rather, since we're after the optimal performance, copying a growing and quite large datastructure (array in this case) definitely won't work.

Any good suggestions? :-)

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)

This question might be a good candidate for Code Review Stack Exchange. — Jordan Running
– Jordan Running, Commented Feb 20, 2018 at 16:11
Didn't know that site. But I sure will be using that alot from now on :-) — Dac0d3r
– Dac0d3r, Commented Feb 20, 2018 at 17:48
Sounds like you need a queue! Here’s a fast deque implementation: npmjs.com/package/double-ended-queue — Ry-
– Ry- ♦, Commented Feb 20, 2018 at 17:50
Sure looks like it Ryan. However how would I be able to remove the first n items of the array? Is it so fast that you just do it with n shifts? :D — Dac0d3r
– Dac0d3r, Commented Feb 20, 2018 at 17:58

2 revs · Accepted Answer · 2018-02-20 18:09:15Z

1

Judging by the listed operations, you’re looking for a queue with constant-time enqueue and dequeue. When you use an array as a queue by moving all the elements for operations on one side, that operation instead takes time proportional to the number of elements in the array. An implementation based on a circular buffer or linked list (both satisfy the constant-time requirement) will be faster as the number of elements becomes larger.

Linked lists are simple enough to demonstrate in a post:

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

but for the best performance in practice, you’ll want to use a queue based on a circular buffer. double-ended-queue is one such npm package.

edited Feb 20, 2018 at 18:09

community wiki

2 revs
Ryan

Sign up to request clarification or add additional context in comments.

7 Comments

Dac0d3r Over a year ago

Fantastic answer. Thanks a lot!!

Ry- Over a year ago

@Dac0d3r: happy to help!

Dac0d3r Over a year ago

Coming back to this, I had a few problems implementing this. In my code I'm using this array for datapoints in a chart. This chart is a react component, which is uses a MobX observable array. Using this deque you can only get the first/last item, unless you want to use toArray and pay the performance penalty of copying all the items (in a for loop) into a new array. I really need an array - for other use cases this library is absolutely awesome :/

user3297291 Over a year ago

If you're curious about the circular buffer @Ryan mentioned, you might want to read this answer on a similar question.

Ry- Over a year ago

@Dac0d3r: Oh, so is this like live a time series?

|

Collectives™ on Stack Overflow

Performance optimizations for add, removeFirst, removeFirstN array operations

1 Answer 1

7 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related