How to search for an object in a Javascript array, and fast!

Say you have an array of Javascript objects. You might want to pull out an item based on the value of one of it’s properties.

A simple function to retrieve an item from the array might look like this.

This code will work fine. But if, for some crazy reason, you want to retrieve the broccoli object, it will iterate through the entire array, checking each value. This is perfectly acceptable for a small array like this one. But what if you have thousands of large objects? When using Javascript as a client-side scripting language, the performance of iterating through an array is determined by the end-users browser and computer. So when running on a mobile device or an old machine, this sort of operation can be painfully slow when working with lots of data. Here are some ideas for speeding things up.

Data Structuring

One of many reasons that databases like SQL are generally efficient at retrieving data is indexing. This is a very broad topic, that is outside the scope of this post. However the basic principle is that the database ‘knows’ where certain values in the database are, so it doesn’t have to search for them. A good example of database indexing is a phone book. The records in the book are ordered by surname. If you want to find someone with the surname ‘Jones’, you can quickly skip all of the irrelevant records and just scan through J. In a SQL database this is called a clustered index, and determines the actual order of data storage, so only one column name can be used for a clustered index.

This principle can be applied to our data. If you have control of the format of your Javascript data, the above array can be slightly optimised. Each object has a ‘type’ to indicate whether it’s fruit, or veg. So instead of an array of objects, the data could be presented as an object, with the ‘type’ property used to ‘cluster’ the records.

And the function to retrieve an item

Now if you’re searching for broccoli, and you know it’s a vegetable, then your function only needs to iterate through half as much data to find your object. So, what if you don’t know the type? Your new indexed object can still be iterated through in the long-hand fashion. A slight modification to the function can check to see if ‘context’ is defined, and if not, just use an extra loop.

The looseness of Javascript’s syntax as a scripting language means that we can call the above function with or without specifying the second argument.

Advanced Indexing

If you need to deal with a large number of very large objects, it can be worth setting up an extra array, just for indexing. This is equivalent to a non-clustered index in SQL. It is very much like the index at the back of a book, which you can use to find the page number of a particular record. So when building your large array, also create an object that just holds information about the larger one.

This might seem pointless at first glance, but it provides a lightweight object that can be queried to find the location of an object based on your chosen property name. So, this time, if you want to retrieve the broccoli object, all you need to do is this.

This saves iterating through what could be thousands of large objects, inspecting their values. This indexing method will only work with a property that you know holds unique values. Even if you’re retrieving your large array from somewhere else, i.e. some JSON from another server, you could perform an initial loop through it to index your values, giving you fast access for later on.

Loop performance

There are a number of different ways to loop through an array. Here is an excellent post outlining the performance of the most common methods. http://benhollis.net/blog/2009/12/13/investigating-javascript-array-iteration-performance. It is conclusive from these tests that the ‘for’ loop is the most efficient method, with one thing to note. The second parameter, the boolean test to determine the length of the loop, is performed on every iteration. If you look at the loops above, they all assign the length of the array to a variable in the first parameter of the loop. The next parameter checks the variable, not the length property. This can speed up a loop significantly.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

Create a website or blog at WordPress.com

Up ↑

%d bloggers like this: