js-sorted-set insert/remove

JavaScript performance comparison

Test case created by Adam Hooper

Info

Let's create sorted sets of three sizes:

And we'll use these algorithms:

And let's insert and remove() some random items from them and see what's fastest.

Preparation code

<script src="https://rawgithub.com/adamhooper/js-sorted-set/0.0.2/sorted-set.no-require.js" type="text/javascript"></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, tree10, tree100, tree1000, tree10000, rbtree10, rbtree100, rbtree1000, rbtree10000;
   
    function cmp(a, b) { return a - b; }
   
    array10 = new SortedSet({ comparator: cmp, strategy: SortedSet.ArrayStrategy });
    array100 = new SortedSet({ comparator: cmp, strategy: SortedSet.ArrayStrategy });
    array1000 = new SortedSet({ comparator: cmp, strategy: SortedSet.ArrayStrategy });
    array10000 = new SortedSet({ comparator: cmp, strategy: SortedSet.ArrayStrategy });
   
    tree10 = new SortedSet({ comparator: cmp, strategy: SortedSet.BinaryTreeStrategy });
    tree100 = new SortedSet({ comparator: cmp, strategy: SortedSet.BinaryTreeStrategy });
    tree1000 = new SortedSet({ comparator: cmp, strategy: SortedSet.BinaryTreeStrategy });
    tree10000 = new SortedSet({ comparator: cmp, strategy: SortedSet.BinaryTreeStrategy });
   
    rbtree10 = new SortedSet({ comparator: cmp, strategy: SortedSet.RedBlackTreeStrategy });
    rbtree100 = new SortedSet({ comparator: cmp, strategy: SortedSet.RedBlackTreeStrategy });
    rbtree1000 = new SortedSet({ comparator: cmp, strategy: SortedSet.RedBlackTreeStrategy });
    rbtree10000 = new SortedSet({ comparator: cmp, strategy: SortedSet.RedBlackTreeStrategy });
   
    var random200000 = window.random200000;
   
    for (var i = 0; i < 10; i++) {
      array10.insert(random200000[i]);
      tree10.insert(random200000[i]);
      rbtree10.insert(random200000[i]);
    }
   
    for (var i = 0; i < 100; i++) {
      array100.insert(random200000[i]);
      tree100.insert(random200000[i]);
      rbtree100.insert(random200000[i]);
    }
   
    for (var i = 0; i < 1000; i++) {
      array1000.insert(random200000[i]);
      tree1000.insert(random200000[i]);
      rbtree1000.insert(random200000[i]);
    }
   
    for (var i = 0; i < 10000; i++) {
      array10000.insert(random200000[i]);
      tree10000.insert(random200000[i]);
      rbtree10000.insert(random200000[i]);
    }
   
    function insertAndRemoveNItemsInSet(n, set) {
      for (var i = 0; i < n; i++) {
        set.insert(random200000[100000 + i]);
      }
      for (var i = 0; i < n; i++) {
        set.remove(random200000[100000 + i]);
      }
    }
};
</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
Small array insert+remove
insertAndRemoveNItemsInSet(5, array10);
pending…
Medium array insert+remove
insertAndRemoveNItemsInSet(5, array100);
pending…
Large array insert+remove
insertAndRemoveNItemsInSet(5, array1000);
pending…
Small binary tree insert+remove
insertAndRemoveNItemsInSet(5, tree10);
pending…
Medium binary tree insert+remove
insertAndRemoveNItemsInSet(5, tree100);
pending…
Large binary tree insert+remove
insertAndRemoveNItemsInSet(5, tree1000);
pending…
Small red-black tree insert+remove
insertAndRemoveNItemsInSet(5, rbtree10);
pending…
Medium red-black tree insert+remove
insertAndRemoveNItemsInSet(5, rbtree100);
pending…
Large red-black tree insert+remove
insertAndRemoveNItemsInSet(5, rbtree1000);
pending…
Huge array insert+remove
insertAndRemoveNItemsInSet(5, array10000);
pending…
Huge binary tree insert+remove
insertAndRemoveNItemsInSet(5, tree10000);
pending…
Huge red-black tree insert+remove
insertAndRemoveNItemsInSet(5, rbtree10000);
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