js-priority-queue queue/dequeue

JavaScript performance comparison

Test case created by Adam Hooper

Info

Let's make priority queues of different sizes using different strategies. We'll see which is fastest for queueing and dequeueing.

Preparation code

<script src="https://rawgithub.com/adamhooper/js-priority-queue/0.0.2/priority-queue.no-require.js"></script>
<script>
var random200000 = [];
for (var i = 0; i < 200000; i++) {
  random200000.push(i / 200000);
}

function shuffleArray(array) {
    for (var i = array.length - 1; i > 0; i--) {
        var j = Math.floor(Math.random() * (i + 1));
        var temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    return array;
}

shuffleArray(random200000);

window.random200000 = random200000;
</script>
 
<script>
Benchmark.prototype.setup = function() {
    var array10, array100, array1000, array10000, heap10, heap100, heap1000, heap10000, bheap10, bheap100, bheap1000, bheap10000;
   
    function cmp(a, b) { return a - b; }
   
    array10 = new PriorityQueue({ comparator: cmp, strategy: PriorityQueue.ArrayStrategy });
    array100 = new PriorityQueue({ comparator: cmp, strategy: PriorityQueue.ArrayStrategy });
    array1000 = new PriorityQueue({ comparator: cmp, strategy: PriorityQueue.ArrayStrategy });
    array10000 = new PriorityQueue({ comparator: cmp, strategy: PriorityQueue.ArrayStrategy });
   
    heap10 = new PriorityQueue({ comparator: cmp, strategy: PriorityQueue.BinaryHeapStrategy });
    heap100 = new PriorityQueue({ comparator: cmp, strategy: PriorityQueue.BinaryHeapStrategy });
    heap1000 = new PriorityQueue({ comparator: cmp, strategy: PriorityQueue.BinaryHeapStrategy });
    heap10000 = new PriorityQueue({ comparator: cmp, strategy: PriorityQueue.BinaryHeapStrategy });
   
    bheap10 = new PriorityQueue({ comparator: cmp, strategy: PriorityQueue.BHeapStrategy });
    bheap100 = new PriorityQueue({ comparator: cmp, strategy: PriorityQueue.BHeapStrategy });
    bheap1000 = new PriorityQueue({ comparator: cmp, strategy: PriorityQueue.BHeapStrategy });
    bheap10000 = new PriorityQueue({ comparator: cmp, strategy: PriorityQueue.BHeapStrategy });
   
    var random200000 = window.random200000;
   
    for (var i = 0; i < 10; i++) {
      array10.queue(random200000[i]);
      heap10.queue(random200000[i]);
      bheap10.queue(random200000[i]);
    }
   
    for (var i = 0; i < 100; i++) {
      array100.queue(random200000[i]);
      heap100.queue(random200000[i]);
      bheap100.queue(random200000[i]);
    }
   
    for (var i = 0; i < 1000; i++) {
      array1000.queue(random200000[i]);
      heap1000.queue(random200000[i]);
      bheap1000.queue(random200000[i]);
    }
   
    for (var i = 0; i < 10000; i++) {
      array10000.queue(random200000[i]);
      heap10000.queue(random200000[i]);
      bheap10000.queue(random200000[i]);
    }
   
    function queueAndDequeueNItems(n, queue) {
      for (var i = 0; i < n; i++) {
        queue.queue(random200000[100000 + i]);
      }
      for (var i = 0; i < n; i++) {
        queue.dequeue();
      }
    }
};
</script>

Preparation code output

Test runner

Warning! For accurate results, please disable Firebug before running the tests. (Why?)

Java applet disabled.

Testing in unknown unknown
Test Ops/sec
array-10
queueAndDequeueNItems(5, array10);
pending…
heap-10
queueAndDequeueNItems(5, heap10);
pending…
bheap-10
queueAndDequeueNItems(5, bheap10);
pending…
array-100
queueAndDequeueNItems(5, array100);
pending…
heap-100
queueAndDequeueNItems(5, heap100);
pending…
bheap-100
queueAndDequeueNItems(5, bheap100);
pending…
array-1000
queueAndDequeueNItems(5, array1000);
pending…
heap-1000
queueAndDequeueNItems(5, heap1000);
pending…
bheap-1000
queueAndDequeueNItems(5, bheap1000);
pending…
array-10000
queueAndDequeueNItems(5, array10000);
pending…
heap-10000
queueAndDequeueNItems(5, heap10000);
pending…
bheap-10000
queueAndDequeueNItems(5, bheap10000);
pending…

Compare results of other browsers

Revisions

You can edit these tests or add even more tests to this page by appending /edit to the URL. Here’s a list of current revisions for this page:

0 comments

Add a comment