js-priority-queue queue/dequeue

JavaScript performance comparison

Test case created by Adam Hooper

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

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

Test runner

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

Java applet disabled.

Testing in CCBot 2.0.0 / Other 0.0.0
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.

0 Comments