Search item array vs literal

JavaScript performance comparison

Revision 3 of this test case created by Pencroff

Preparation code

 
<script>
Benchmark.prototype.setup = function() {
    var linearSearch = function (value, colection, lenght) {
                    var undef, i;
                    for (i = 0; i < lenght; i += 1) {
                        if (colection[i] === value) {
                            return i;
                        }
                    }
                    return -1;
                },
    binarySearch = function (value, colection, lenght) {
                    var first = 0,
                        last = lenght - 1,
                        mid = first + ((last - first) >> 1),
                        item;
                    if (lenght === 0 || colection[first] > value || colection[last] < value) {
                        return -1;
                    }
                    while (first - last) {
                        item = colection[mid];
                        if (value === item) {
                            return mid;
                        } else if (value < item) {
                            last = mid;
                        } else {
                            first = mid + 1;
                        }
                        mid = first + ((last - first) >> 1);
                    }
                    if (colection[last] !== value) {
                        return -1;
                    }
                    return last;
                },
    bigLen = 100000,
    smallLen = 50,
    bigArray,
    bigLiteral,
    smallArray,
    smallLiteral,
    bigItem,
    smallItem,
    getRandomNumber = function(range) {
      return Math.floor(Math.random() * range);
    },
    fillArray = function (size) {
      var i, arr = [];
      arr.length = size;
      for (i = 0; i < size; i += 1) {
        arr[i] = getRandomNumber(size*10);
      }
      return arr;
    },
    copyArrayToLiteral = function (array) {
      var i, lt = {},
          size = array.length;
      for (i = 0; i < size; i += 1) {
        lt[i] = array[i];
      }
        return lt;
    },
    index;
    bigArray = fillArray(bigLen);
    bigArray.sort(function (a, b) {
      return a - b;
    });
    bigLiteral = copyArrayToLiteral(bigArray);
    bigItem = bigArray[getRandomNumber(bigLen)];
    smallArray = fillArray(smallLen);
    smallArray.sort(function (a, b) {
      return a - b;
    });
    smallLiteral = copyArrayToLiteral(smallArray);
    smallItem = smallArray[getRandomNumber(smallLen)];
};
</script>

Test runner

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

Java applet disabled.

Testing in unknown unknown
Test Ops/sec
Native (50 items)
index = smallArray.indexOf(smallItem);
pending…
Linear array (50 items)
index = linearSearch(smallItem, smallArray, smallLen);
pending…
Linear literal (50 items)
index = linearSearch(smallItem, smallLiteral, smallLen);
pending…
Binary array (50 items)
index = binarySearch(smallItem, smallArray, smallLen);
pending…
Binary literal (50 items)
index = binarySearch(smallItem, smallLiteral, smallLen);
pending…
Native (100 000 items)
index = bigArray.indexOf(bigItem);
pending…
Linear array (100 000 items)
index = linearSearch(bigItem, bigArray, bigLen);
pending…
Linear literal (100 000 items)
index = linearSearch(bigItem, bigLiteral, bigLen);
pending…
Binary array (100 000 items)
index = binarySearch(bigItem, bigArray, bigLen);
pending…
Binary literal (100 000 items)
index = binarySearch(bigItem, bigLiteral, bigLen);
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