Writing a queue in Javascript
So you want to use a queue, a structure that has items added at one side and removed on another, in Javascript code. Items are added to the tail of the queue, while they are removed at the head. We, Romanians, are experts because in the Communist times resources were scarce and people often formed long queues to get to them, sometimes only on the basis of rumour. They would see a line of people and ask "Don't they have meat here?" and the answer would come "No, they don't have milk here. It's next building they don't have meat at". Anyway...
There is an option that can be used directly out of the box: the humble array. It has methods like .push (add an item), .pop (remove the latest added item - when you use it as a stack) and .shift (remove the oldest added item - when you use it as a queue). For small cases, that is all you need.
However, I needed it in a high performance algorithm and if you think about it, removing the first element of an array usually means shifting (hence the name of the function) all elements one slot and decreasing the length of the array. Consider a million items array. This is not an option.
One of the data structure concepts we are taught at school is the linked list. Remember that? Each item has a reference to the next (and maybe the previous) item in the list. You explore it by going from one item to the next, without indexing, and you can remove any part of the list or add to any part of the list just by changing the value of these references. This also means that for each value you want stored you have the value, the reference(s) and the overhead of handling a more complex data object. Again, consider a million numbers array. It's not the right fit for this problem.
Only one option remains: still using an array, but moving the start and the end of the array in an abstract manner only, so that all queue/dequeue operations take no effort. This means keeping a reference to the tail and the head of the queue in relation to the length of the queue and of the underlying array.
But first let's establish a baseline. Let's write a test and implement a queue using the default array pop/shift implementation:
// the test
const size = 100000;
const q=new Queue();
time(()=> { for (let i=0; i<size; i++) q.enqueue(i); },'Enqueue '+size+' items');
time(()=> { for (let i=0; i<size; i++) q.dequeue(i); },'Dequeue '+size+' items');
time(()=> { for (let i=0; i<size/10; i++) {
for (let j=0; j<10; j++) q.enqueue(i);
for (let j=0; j<9; j++) q.dequeue(i);
} },'Dequeue and enqueue '+size+' items');
// the Queue implementation
class Queue {
constructor() {
this._arr = [];
}
enqueue(item) {
this._arr.push(item);
}
dequeue() {
return this._arr.shift();
}
}
// the results
Enqueue 100000 items, 10ms
Dequeue 100000 items, 1170ms
Dequeue and enqueue 100000 items, 19msThe Enqueue operation is just adding to an array, enqueuing and dequeuing by leaving an item at ever series of dequeues is slightly slower, as the amount of array shifting is negligible. Dequeuing, though, is pretty heavy. Note that increasing just a little bit the amount of items leads to an exponential increase in time:
Enqueue 200000 items, 12ms
Dequeue 200000 items, 4549ms
Dequeue and enqueue 200000 items, 197msNow let's improve the implementation of the queue. We will keep enqueue using Array.push, but use a _head index to determine which items to dequeue. This means faster speed, but the queue will never shorten. It's the equivalent of Romanians getting their product, but remaining in the queue.
// the Queue implementation
class Queue {
constructor() {
this._arr = [];
this._head = 0;
}
enqueue(item) {
this._arr.push(item);
}
dequeue() {
if (this._head>=this._arr.length) return;
const result = this._arr[this._head];
this._head++;
return result;
}
}
// the results
Enqueue 200000 items, 11ms
Dequeue 200000 items, 4ms
Dequeue and enqueue 200000 items, 11msThe performance has reached the expected level. Dequeuing is now even faster than enqueuing because it doesn't need to expand the array as items are added. However, for all scenarios the queue is only growing, even when dequeuing all the items. What I can do is reuse the slots of the dequeued items for the items to be added. Now it gets interesting!
My point is that right now we can improve the functionality of our queue by replacing dequeued but still stored items with newly enqueued items. That is the equivalent of Romanians leaving the queue only after they get the meat and a new Romanian comes to take their place. If there are more people coming than getting served, then people that got their meat will all leave and we can just add people to the tail of the queue.
So let's recap the algorithm:
- we will use an array as a buffer
- the queue items start at the head and end at the tail, but wrap around the array buffer
- whenever we add an item, it will be added in the empty space inside the array and the tail will increment
- if there is no empty space (queue length is the same as the array length) then the array will be rearranged so that it has space for new itms
- when we dequeue, the item at the head will be returned and the head incremented
- whenever the head or tail reach the end of the array, they will wrap around
Some more improvements:
- if we enqueue a lot of items then dequeue them, the array will not decrease until we dequeue them all. An improvement is to rearrange the array whenever the queue length drops below half of that of the array. It will add computation, but reduce space.
- when we make space for new items (when the array size is the same as the one of the logical queue) we should add more space than just 1, so I will add the concept of a growth factor and the smallest size increase.
Here is the code:
/**
* A performant queue implementation in Javascript
*
* @class Queue
*/
class Queue {
/**
*Creates an instance of Queue.
* @memberof Queue
*/
constructor() {
this._array = [];
this._head = 0;
this._tail = 0;
this._size = 0;
this._growthFactor = 0.1;
this._smallestSizeIncrease = 64;
}
/**
* Adding an iterator so we can use the queue in a for...of loop or a destructuring statement [...queue]
*/
*[Symbol.iterator]() {
for (let i = 0; i < this._size; i++) {
yield this.getAt(i);
}
}
/**
* Returns the length of the queue
*
* @readonly
* @memberof Queue
*/
get length() {
return this._size;
}
/**
* Get item based on item in the queue
*
* @param {*} index
* @returns
* @memberof Queue
*/
getAt(index) {
if (index >= this._size) return;
return this._array[(this._head + index) % this._array.length];
}
/**
* Gets the item that would be dequeued, without actually dequeuing it
*
* @returns
* @memberof Queue
*/
peek() {
return this.getAt(0);
}
/**
* Clears the items and shrinks the underlying array
*/
clear() {
this._array.length = 0;
this._head = 0;
this._tail = 0;
this._size = 0;
}
/**
* Adds an item to the queue
*
* @param {*} obj
* @memberof Queue
*/
enqueue(obj) {
// special case when the size of the queue is the same as the underlying array
if (this._size === this._array.length) {
// this is the size increase for the underlying array
const sizeIncrease = Math.max(this._smallestSizeIncrease, ~~(this._size * this._growthFactor));
// if the tail is behind the head, it means we need to move the data from the head to
// the end of the array after we increase the array size
if (this._tail <= this._head) {
const toMove = this._array.length - this._head;
this._array.length += sizeIncrease;
for (let i = 0; i < toMove; i++) {
this._array[this._array.length - 1 - i] = this._array[this._array.length - 1 - i - sizeIncrease];
}
this._head = (this._head + sizeIncrease) % this._array.length;
}
else
// the array size can just increase (head is 0 and tail is the end of the array)
{
this._array.length += sizeIncrease;
}
}
this._array[this._tail] = obj;
this._tail = (this._tail + 1) % this._array.length;
this._size++;
}
/**
* Removed the oldest items from the queue and returns it
*
* @returns
* @memberof Queue
*/
dequeue() {
if (this._size === 0) {
return undefined;
}
const removed = this._array[this._head];
this._head = (this._head + 1) % this._array.length;
this._size--;
// special case when the size of the queue is too small compared to the size of the array
if (this._size > 1000 && this._size < this._array.length / 2 - this._smallestSizeIncrease) {
if (this._head<this._tail) {
this._array = this._array.slice(this._head,this._tail);
} else {
this._array=this._array.slice(this._head, this._array.length).concat(this._array.slice(0,this._tail));
}
this._head = 0;
this._tail = 0;
}
return removed;
}
}Final notes:
- there is no specification on how an array should be implemented in Javascript, therefore I've used the growth factor concept, just like in C#. However, according to James Lawson, the array implementation is pretty smart in modern Javascript engines, we might not even need it.
- the optimization in dequeue might help with space, but it could be ignored if what you want is speed and don't care about the space usage
- final benchmarking results are:
Enqueue 200000 items, 15ms, final array size 213106 Dequeue 200000 items, 19ms, final array size 1536 Dequeue and enqueue 200000 items, 13ms, final array size 20071
Comments
Be the first to post a comment