rapid-queue-2

JavaScript array.shift() is slow. This is an implementation using circular buffer and two stack. Circular queue use circular buffer and Double Stack Queue use two stack to implement the queue.

This implementation of shift is up to 10,000 times faster than JavaScript's array.shift().

Installation

npm install rapid-queue-2

Usage

Before using it, require the module

const RapidQueue = require('rapid-queue-2')

or

import RapidQueue from 'rapid-queueu-2'

Creating queue

const queue = RapidQueue.createQueue(200)

Queue operation

Inserting element to the end of queue

queue.push(5)`

Push will insert 5 to the back of the queue, it will automatically grow the array if the capacity is not enough.

Get front element

const front = queue.front()

It will return the front element without removing it from the queue. It will return null if queue is empty.

Remove front element

const front = queue.shift()

It will return and remove front element from the queue. It will return null if queue is empty.

Get queue length

const length = queue.length()

It will return the number of element inside queue;

Check if queue is empty

const isEmpty = queue.isEmpty()

Performance

Shift 1,000,000 items by rapid-queue-2: 0.00865 Seconds Shift 1,000,000 items by regular array: 88.97404 Seconds

The code used for benchmark:

const RapidQueue = require('rapid-queue-2')
const queue = RapidQueue.createQueue()

// function to measure code execution time
function parseHrtimeToSeconds(hrtime) {
  var seconds = (hrtime[0] + hrtime[1] / 1e9).toFixed(5)
  return seconds
}

for (let i = 0; i < 1000000; i++) {
  queue.push(i)
}

// start measuring time1
startTime1 = process.hrtime()

for (let i = 0; i < 1000000; i++) {
  queue.shift()
}

// stop time1
const elapsedSeconds1 = parseHrtimeToSeconds(process.hrtime(startTime1))
console.log('rapid-queue-2: ' + elapsedSeconds1 + 'seconds')

// ------ regular array implementation
const arr = []

for (let i = 0; i < 1000000; i++) {
  arr.push(i)
}

// start measuring time2
startTime2 = process.hrtime()
for (let i = 0; i < 1000000; i++) {
  arr.shift()
}

// stop time2
const elapsedSeconds2 = parseHrtimeToSeconds(process.hrtime(startTime2))
console.log('Array: ' + elapsedSeconds2 + 'seconds')

License

MIT

The original code is on kevyuu/rapid-queue and is not maintained.