Is There A Better Way To Search A Javascript Array Than Using Jquery's Each?

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

Solution 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

Solution 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.

Solution 3:

This doesn't answer your "search" question per se, but it may be a solution for you. You can create a specialized PersonArray class which indexes the people within it. The performance with this approach is O(1), but it uses more memory.

varPersonArray = function(persons) {
    this.elements = {};
    var i;
    for (i=0; i < persons.length; i++) {
        this.elements[persons[i].code] = persons[i];
    }
};

PersonArray.prototype.fromCode = function(s) {
    returnthis.elements[s];   
};

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

console.log(people.fromCode("ABC123"));  // Prints a personconsole.log(people.fromCode("DEF456"));  // Prints a personconsole.log(people.fromCode("NONE"));  // Undefined

You can extend this approach to index other fields, as well.

Also see: a demo and a benchmark (with 100,000 elements).

Solution 4:

If you intend to do this a lot, then you might want to create an index for specific properties so that items can be returned much faster. e.g. the following implements a storage object that add and gets objects that are added to it.

It keeps an index of object names (if they have one) so that getting them is efficient.

You'll only notice a performance bump for a large number of objects though (say more than 100 or so) and only for those with an index (though you can create an index for any number of properties and could have a more generic method to do that).

functionStorage() {
  this.store = [];
  this.nameIndex = {};
}

// Add item to the store, if has name property, add name to name indexStorage.prototype.addItem = function(item) {
  var idx = this.nameIndex;

  // If the item has a name propertyif (item.hasOwnProperty('name')) {

    // If already have an item with that name, add index of// this item to indexs of same named itemsif (idx.hasOwnProperty(item.name)) {
      idx[item.name].push(this.store.length);

    // Otherwise, add this item to the index
    } else {
      idx[item.name] = [this.store.length];


    }
  }  
  // Add the item to the storethis.store.push(item);
}

// Returns a possibly empty array of items with matching namesStorage.prototype.getItemsByName = function(name) {
  var result = [];
  var names;

  if (this.nameIndex.hasOwnProperty(name)) {
    list = this.nameIndex[name];

      for (var i=0, iLen=list.length; i<iLen; i++) {
        result.push(this.store[list[i]]);
      }
  }
  return result;
}

// Generic method for any property and valueStorage.prototype.getItemsByAttributeValue = function(propName, propValue) {
  // loop through items, return array of // those with matching property and value
}


var store = newStorage();

store.addItem({name:'fred',age:'9'});

var obj = store.getItemsByName('fred');

alert(obj[0].age); // 9

store.addItem({name:'sally',age:'12'});

obj = store.getItemsByName('sally');

alert(obj[0].age); //12

Solution 5:

Maybe you can loop it with a for..in. See: http://www.w3schools.com/js/js_loop_for_in.asp. Works in a similair fashion as php's foreach.