Is there a Better Way to Search a JavaScript Array than Using jQuery's each?

Question

I often have the need to search a javascript array that contains objects. I want to search for an object in the array that has a property match. For example, searching an array of Person objects for where the person's id/key === "ABC123"

It can be done pretty easily using jQuery using the $.each method, which is what I settled on. You can see the example here in jsFiddle. http://jsfiddle.net/johnpapa/EJAFG/

I'm wondering if anyone else has found a faster and/or better way to do this?

var Person = function(code, name) {
    this.code = code;
    this.name = name;
};
var people = [
    new Person("ABC123", "Tooth Fairy"),
    new Person("DEF456", "Santa Claus"),
    new Person("PIR000", "Jack Sparrow"),
    new Person("XYZ987", "Easter Bunny")
    ];

var utils = {};
// Could create a utility function to do this
utils.inArray = function(searchFor, property) {
    var retVal = -1;
    $.each(this, function(index, item) {
        if (item.hasOwnProperty(property)) {
            if (item[property].toLowerCase() === searchFor.toLowerCase()) {
                retVal = index;
                return false;
            }
        }
    });
    return retVal;
};

// or we could create a function on the Array prototype indirectly
Array.prototype.inArray = utils.inArray;

// let's use the prototype for now
var i = people.inArray("PIR000", "code");
$('#output').text(people[i].name);

There are lot's of questions similar to this one, but I have yet to see one with a solution other than iterating (like I did here).

So the question is ... is there a better way?

Answer 1

$.each would be about O(n) I would think. Any simple "for" loop that breaks when it finds an applicable item would be at most O(n) but would on average be less unless the latter items of the array were constantly found to be the matching elements. Array.filter is a method that works but is not native to some browsers. There are pure javascript implementations of the Array.filter method if you so wished to use it. For the browsers that host it natively, it would probably execute faster as their implementation is probably compiled and ran in native code. But the filter method would always yield O(n) as it "filters" the elements of the array into a new array.

I'd personally stick with the for(int i=0;...) approach. Less overhead of scope changing by calling other functions and you can easily "break" on a matched element.

I also wanted to add that you could use local database storage(which uses SqlLite) provided by HTML 5. This is obviously not widely supported but would be MUCH faster than any other javascript approach given a large enough set of data. Here is a link if you want to check it out:

http://blog.darkcrimson.com/2010/05/local-databases/

Here is a somewhat off the wall way of doing it: You could theoretically index your data and retrieve it using those indicies in a fast manner. Instead of storing your data in a javascript array, you store it in the DOM and "index" the elements using CSS classes like "data-id-5". This gives you the advantage of using the native selector API built-in to most major browsers. Here is an example:

DOM:

 <div id="datastuff" style="display:none">
     <span class="data-id-ABC123" data-person='{"code": "ABC123", "name": "Tooth Fairy"}'></span>
     <span class="data-id-DEF456" data-person='{"code": "DEF456", "name": "Santa Claus"}'></span>
     <span class="data-id-PIR000" data-person='{"code": "PIR000", "name": "Jack Sparrow"}'></span>
     <span class="data-id-XYZ987" data-person='{"code": "XYZ987", "name": "Easter Bunny"}'></span>
 </div>

Now we can use jQuery and query for it: We'll query for key of "ABC123":

var person = $(".data-id-ABC123").data("person");
console.log(person.name);//Tooth Fairy

Answer 2

In general you can't get elements from an array faster then O(n) unless you know something about what you want to index.

For example, if you are indexing somethnig that is comparable you can sort the array and do binary search.

If you are doing searches on a column and the values are ints or strings you can use plain Javascript objects as hash tables.

var people = [
    new Person("ABC123", "Tooth Fairy"),
    new Person("DEF456", "Santa Claus"),
    new Person("PIR000", "Jack Sparrow"),
    new Person("XYZ987", "Easter Bunny")
];

var people_table = {};
for(var i=0; i<people.length; i++){
    people_table[ people[i].id ] = people[i];
}

//fast search:
var someone = people_table['ABC123'];

After a certain point queries get too complex to easily do by hand in Javascript so it might be a good idea to send the processing server-side so you can use a more appropriate tool, like as a relational database.