by Cedric Dugas on August 9, 2010
Processing arrays can take quite a few bit of time, this is something that can directly impacts the loading speed of your page and depend of the computer and the browser your users use. When you think that a typical users can load your website with a netbook , or an iphone for that matter, speeding up search in large arrays can be a good way to optimize your code.
If you never studied in computer science, well like me, the first way you might think about searching in your arrays is to do a loop using the array length and compare each item with your query until you find what you need.
This means that if you are looking for all the items starting by the letter W in a array listed alphabetically, of let’s say 100 000 items, you will iterate not far from 100 000 times to find them all! This is way too long, but there is some way to make it better, a freaking lot better.
Introducing the binary search algorithm
It sounds complicated, but in fact this is really simple. Imagine a phone book, imagine that you are looking for the name Smith. Using a traditional loop you would have to look at each page of the book until you get to S, that would be pretty painful..
Now instead of doing that, cut the phone book in half, look if Smith will be in the left or right part, discard the irrelevant part.Now take that your revelant part, cut it in half, and do the same operation until you find a Smith on your page. Just at the first operation, you discarded 50 000 results, with the traditional loop, you would be at 2 of 100 000.
Of course once you got a Smith, you need to look right before and after this item for others Smith, create a new list with all your Smith, and your done! As I said before this is based on the fact that you already got a list in a alphabetical order, this would not work with a disordered list.
You can find more information about this algorithm on this page.
You can find a couple of resources on the web to help you implement this functionality yourself, but I created a small helper that use the binary algorithm to search into arrays for one of my project.
With this little helper you just pass your array and what you are looking for and it will return you back a result array, a typical use would look like this:
var searchResult = searchBinary("m", array, true) // the parameters are : searchBinary(search string, array to search, case insensitive?)
This will return an array with all items starting by the letter m. A good use of this script would be with a auto-complete widget.
I did a small performance comparison with Dynatrace. With an array of 2500 items, the binary algorithm is approximately 15 times faster than a traditional loop in Internet Explorer 8 with a core duo 1.3. Of course the more your array is big, the more you save time. The download also include a traditional search helper, so you can do the test yourself if you want.
Hope you guys like it!
Dynatrace is a cool tool for testing front-end performance on Internet Explorer, you get execution times from everything, cpu usage, and much more. It is the most powerful tool I saw on any platform for front-end tracing. The best part? It’s completely free!
Special thanks to Sherif Zaroubi for his help with this.