JavaScript binary search vs. array.filter

Abstract

In this post, we want to find out if Array.filter is as fast as binary search. We will produce a large number of random key value-pairs, perform a lookup to find a key with
  1. Loop all entires (only as a benchmark)
  2. Quick-sort and binary find
  3. Array.find
and compare the performance. The key-value-pair array is used in json format. By the way we want to find out if Array.sort is as fast as a javascript implementation of the quick sort algorithm.

Rationale

In cases where client calculation time is crucial, the fastest way to retrieve an item of an unsorted array is useful.

Produce key value pairs

At first we will produce an array with 1.000.000 random key value pairs, e.g. [{key:234, value:"v218921"}]. For the random numbers we choose a range from 1 to 1.000.000.000.

1.

Sorting the array

Now we are going to sort the created array in two ways:
Note: The initial array is cloned via Array.slice() and the time needed to create the clone is does not count.

At first using the Array.sort method:
Note: This will take a few seconds as the function is run several times
2.

then using a quick sort algorithm:
Note: This will take a few seconds as the function is run several times
3.

Result

In some cases, the procedure that ran as second item was faster than the first one. In the longer run, the native Array.sort method seems to be slightly faster than a quick sort implementation. With regard to the effort (additional code for qs) one should use the native sort function.

Finding a key

In the next step we want to retrieve a key-value-pair from the array.

At first we start to find a value in the unsorted array with a normal loop O(n).
4.

Now we want to compare this to the time needed to find an item via Array.filter
5.

And finally we want to know whether a binary search in the sorted array is faster than the Array.filter method.
We have add the time needed to sort the array + the time needed to binary find the item!
6.

Result

Yes, Array.filter is faster as binary search. BUT: A simple loop is even faster than both. Array.filter has to loop all the data, because it can retrieve multiple values as a result. As binary search includes the sorting first, wich takes most of the time, this combination is too slow.

Conclusion

Use Array.sort instead on an implementation of quick sort and simply use a loop with max. O(n) to find a value within a JSON array.

Sources

[1] https://en.wikipedia.org/wiki/D3.j
[2] https://gist.github.com/pedrombafonso/5668956
[3] https://www.nczonline.net/blog/2009/09/01/computer-science-in-javascript-binary-search/

Source code

<script>

 

    var items = [];

    var items_ordered = [];

    var lookup_key = 0;

    var items_cnt = 1e6;

    var random_max = 1e9;

    var n = 10;

 

    function createRandomKVPs() {

        items = [];

        var start = new Date().getTime();

        for (i = 1; i < items_cnt; i++) {

            var k = getRandomInt(1, random_max);

            var v = ("v" + getRandomInt(1, random_max));

            items.push({ 'key': k, 'value': v });

        }

        lookup_key = items[getRandomInt(1, items_cnt)];

        var end = new Date().getTime();

        var d = (end - start);

        $('#status-create-rkvp').html('Status: OK, this took ' + d + ' milliseconds.');

    }

 

    function find_loop() {

        var start = new Date().getTime();

        for (var f = 0; f < items_cnt; f++) {

            if (items[f].key == lookup_key.key) break;

        }

        var end = new Date().getTime();

        var d = (end - start);

        $('#status-find-loop').html('Status: OK, this took ' + d + ' milliseconds (' + f + ' loops).');

        console.log(items[f].value + " / loops: " + f);

    }

 

    function find_filter() {

        var start = new Date().getTime();

        var result = items.filter(function (obj) {

            return obj.key == lookup_key.key;

        });

        var end = new Date().getTime();

        var d = (end - start);

        $('#status-find-filter').html('Status: OK, this took ' + d + ' milliseconds.');

        console.log(result[0].value);

    }

 

    function find_bin() {

        var start = new Date().getTime();

        sort();

        var found_item = binarySearch(items, lookup_key);

        var end = new Date().getTime();

        var d = (end - start);

        $('#status-find-bin').html('Status: OK, this took ' + d + ' milliseconds.');

        console.log(found_item.value);

    }

 

    function getRandomInt(min, max) {

        return Math.floor(Math.random() * (max - min + 1)) + min;

    }

 

    function sort() {

        items.sort(function (a, b) {

            return a.key == b.key ? 0 :

                a.key > b.key ? 1 : -1;

        });

        return true;

    }

 

    function sort1(debug) {

        var items_ordered1 = items.slice();

        var start = new Date().getTime();

        items_ordered1.sort(function (a, b) {

            return a.key == b.key ? 0 :

                a.key > b.key ? 1 : -1;

        });

        var end = new Date().getTime();

        var d = (end - start);

        $('#status-sort1').html('Status: OK, this took ' + d + ' milliseconds');

        //console.log(items);

        //console.log(items_ordered1);

        //if (debug) for (i = 0; i < 10; i++) { console.log(items_ordered1[i].key) };

        return d;

    }

 

    function sort2(debug) {

        var items_ordered2 = items.slice();

        var start = new Date().getTime();

 

        //quickSort(items_ordered2, 0, items_ordered2.length - 1)

        quick_sort(items_ordered2, "key");

 

        var end = new Date().getTime();

        var d = (end - start);

        $('#status-sort2').html('Status: OK, this took ' + d + ' milliseconds');

        //console.log(items);

        //console.log(items_ordered2);

        //if (debug) for (i = 0; i < 10; i++) { console.log(items_ordered2[i].key) };

        return d;

    }

 

    function sort1_perf() {

        $('#status-sort1').html($('#status-sort1').html() + ' / average of ' + n + ' runs (' + averagePerformance(sort1, n) + ')');

    }

    function sort2_perf() {

        $('#status-sort2').html($('#status-sort2').html() + ' / average of ' + n + ' runs (' + averagePerformance(sort2, n) + ')');

    }

 

    //https://gist.github.com/pedrombafonso/5668956

    function partition(list, prop, begin, end, pivot) {

        var piv = list[pivot];

        swap(list, pivot, end - 1);

        var store = begin;

        var ix;

        for (ix = begin; ix < end - 1; ++ix) {

            if (list[ix][prop] <= piv[prop]) {

                swap(list, store, ix);

                ++store;

            }

        }

        swap(list, end - 1, store);

        return store;

    }

 

 

    function swap(obj, a, b) {

        var tmp = obj[a];

        obj[a] = obj[b];

        obj[b] = tmp;

    }

 

    function qsort(list, prop, begin, end) {

        if (end - 1 > begin) {

            var pivot = begin + Math.floor(Math.random() * (end - begin));

 

            pivot = partition(list, prop, begin, end, pivot);

 

            qsort(list, prop, begin, pivot);

            qsort(list, prop, pivot + 1, end);

        }

    }

 

    function quick_sort(list, prop) {

        qsort(list, prop, 0, list.length);

    }

 

    function averagePerformance(proc, times) {

        var start = new Date().getTime();

        var d = 0;

        for (var i = 0; i < times; i++) {

            proc();

            //console.log(proc());

        }

        var end = new Date().getTime();

        var d = (end - start) / times;

        return d;

    }

 

    //Copyright 2009 Nicholas C. Zakas. All rights reserved.

    //MIT-Licensed, see source file

    // DN: modified to handle JSON arrray

    function binarySearch(items, value) {

 

        var startIndex = 0,

            stopIndex = items.length - 1,

            middle = Math.floor((stopIndex + startIndex) / 2);

        while (items[middle].key != value.key && startIndex < stopIndex) {

 

            //adjust search area

            if (value.key < items[middle].key) {

                stopIndex = middle - 1;

            } else if (value.key > items[middle].key) {

                startIndex = middle + 1;

            }

 

            //recalculate middle

            middle = Math.floor((stopIndex + startIndex) / 2);

        }

 

        //make sure it's the right value

        return (items[middle].key != value.key) ? -1 : items[middle];

    }

 

</script>


Dieter Neumann