Optimizing search functionality with large javascript arrays

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.

Okay, how I use it in javascript?

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.

Download the source code

Performance

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!

About Dynatrace

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.



12 comments

Nice article, I didn’t know about the binary algorithm, I will put this script in my toolbox!

by Mark on August 10, 2010 at 6:37 pm. Reply #

nice.
can you have a good tutorial about simple and light-weight auto-complete?

by من و متعه ام on August 10, 2010 at 10:07 pm. Reply #

Yes I have one very lightweight autocomplete (it is also feature light ;) , but I would be kind of embarrassed to compare it to jquery ui autocomplete.

by Cedric Dugas on August 10, 2010 at 10:36 pm. Reply #

When I saw the title of this article my mouth dropped open… this is EXACTLY what I needed! I was searching an array of over 80,000 items, and believe me, it was slow as heck! I’m going to try this out right away! Thank you so much!

by Natalie on August 11, 2010 at 12:43 am. Reply #

[...] Posi­tion Absolute, web apps and front-end stuff — Opti­miz­ing search func­tion­al­ity with… [...]

by Optimizing search functionality with large javascript arrays | RefreshTheNet on August 11, 2010 at 1:32 am. Reply #

For extremely heavy autocompletes (like the one in JavaScriptMVC.com), I’ll go through and hash the first 2 characters into something like:

{ ‘a’ : { ‘d’ : ['add','advent', ... ],
….. }.
}

This way, if your words were uniformly distributed, you would have 1/(26^2=676) of the array to binary search through. If memory is an issue, you can convert the strings to sting objects: new String(‘add’) and have references to strings in the array instead of string literals. If you do 3 levels each array would be 1/17567th of the size.

For non CS nerds out there, using a Hash (in JS an Object) is O(1) lookup. If you can, using Objects is always better than Arrays.

by Justin Meyer on August 11, 2010 at 11:34 pm. Reply #

[...] Position Absolute, web apps and front-end stuff – Optimizing … [...]

by American Garage Supply’s Garage Cabinets Put Everything in Their Place « Furniture From Tibet on August 12, 2010 at 1:55 am. Reply #

The correct name is “binary search algorithm” NOT just “binary algorithm”, which is meaningless.

by Marcus Tucker on August 16, 2010 at 10:22 am. Reply #

Very informative and helpful. Thaks very much.

by Reza on September 14, 2010 at 4:33 pm. Reply #

Yesss..
Very informative and helpful. Thaks very much.

by Wiyono on March 28, 2011 at 10:19 am. Reply #

This “free sharing” of infrotmaoin seems too good to be true. Like communism.

by Kassie on October 17, 2011 at 5:09 pm. Reply #

Why not just use one of the higher level functions found in ECMAScript 5? There are lots to choose fromL .forEach(), .every(), .some() and more

If you need to support IE8 and below then use the underscore.js library: http://documentcloud.github.com/underscore/

by Andy Walpole on February 22, 2012 at 1:59 am. Reply #

Leave your comment

Required.

Required. Not published.

If you have one.