Algorithms: Javascript Array indexOf vs Binary Search vs Hash Access

I’ve been getting into algorithms lately, and I wanted to try out adding binary search to Simply Is, a simple type testing javascript utility I wrote a while back. But, surprisingly, it ended up being slower than the native Javascript array indexOf. Less surprisingly though, hash access was the fastest. Actually, creating a hash from the array then accessing it was actually still faster than the binary search (though slower than the native array indexOf).

My theory is that this result probably has to do with how Javascript works under the hood. Something worth looking into would be how Array indexOf is implemented in the Javascript source. It might be possible that since it’s built-in/operating at a lower level, there’s less overhead and thus performs better.


Binary search – 216,774 ops/sec

function binary_search(x,arr){
    if( typeof arr[0] === 'number' ){
        arr = arr.sort(function(x,y){ return Number(x) - Number(y) })
    }else{
        arr = arr.sort()
    }

    var min = 0,
        max = arr.length - 1,
        current_guess = Math.floor( (min + max)/2 )
        
    var found = false

    if( x === arr[current_guess] ){
        found = true
    }else if( x < arr[current_guess] ){ found = binary_search(x, arr.slice(min, current_guess) ) }else if( x > arr[current_guess] ){
        found = binary_search(x, arr.slice(current_guess + 1, max + 1))
    }

    return found
}

Array indexOf = 43,314,557 ops/second

var TEST_ARRAY = [2, 3, 17, 18, 22, 74, 25, 93, 43, 47, 48, 56, 59, 61, 64, 52, 71, 73, 75,37, 76, 77, 88, 21]
TEST_ARRAY.indexOf(73) > 0

Creating a hash from the array then accessing it = 809,269 ops/sec

   var TEST_HASH = {}
    TEST_ARRAY.forEach(function(value){
        TEST_HASH[value] = true
    })
    TEST_HASH[73]

(Existing) hash access = 90,671,807 ops/sec

TEST_HASH[73]

Either way, this result was somewhat surprising to me, since in terms of algorithms, binary search is supposed to be very fast. Then again, the comparison might not be completely fair, since the binary search is implemented at a higher level while the Array indexOf method is built-in. I wonder, though, how will it hold up if the array is very,very large? It’s possible that this result is only the case because the array that’s being searched is pretty small? Or, perhaps it has to do with the way I did the binary search (recursive calls on smaller array slices)? Maybe having to slice/create a new array is slowing it down?

Lots of possibilities for what may have led to this result. I’ll have to look into this a bit more one of these days.

2 Replies to “Algorithms: Javascript Array indexOf vs Binary Search vs Hash Access”

  1. Looking up the element with `indexOf` is n-time, since it has to look for every item in the array.

    Binary search is significantly faster, and has log(n) time. However, the slower result you got due to 2 main problem:
    1) Your binary search implementation includes sorting the array, which take n*log(n) time. So in the end, you end up taking n + n*log(n) to search the item, vs n-time by using `indexOf`. We typically don’t include sorting inside searching implementation, but using a data structure (ex: Binary Tree, or Priority Queue) that supports sorting elements when they are inserted in, then use Binary Search to look up elements.
    2) You are creating new array, by using `slice` for each step in your Binary Search. Using recursive call does not cause much overhead, comparing to creating new array at every step. You don’t need to create new array at every step, you only need to keep track of the low-bound and high-bound index.

    Another interesting thing, hash table does not always yield the fastest result. If you data is all integer, index accessing is still a lot (2-3x) faster than using hash, because you avoid the overhead of using the hash function. But of course, array will not work if you data is non-integer. And also you may waste a lot of space in array to store blank data, in order to have speed improvement over hash table.

    1. Hey Quang! I notice you found my blog…Pardon the cobwebs. 😉 Hope you’re doing well!

      Ah, now THAT makes sense…I was wondering why the result was so strange here. You’re right, I included the sort as part of the binary search function too, and come to think of it, I can see how slicing up the array/creating a new array each time can make it slow. Thanks for clearing that up for me. I’ll have to give this a re-work sometime and re-run the speed tests to see if that’ll make it better. Actually, after you pointed that out, I’m also thinking that maybe a better way of testing this would have been to remove all the setup parts from the code (e.g. the creation of the array, sorting, etc) and just test the object access part on its own to see if the results make a little more sense then….

Leave a Reply

Your email address will not be published. Required fields are marked *