what is the best way to find some items in an array based on the item property value?

Question

I have an array like this:

var anArray = [
    { name: "scala",  type: "a" },
    { name: "abc",    type: "b" },
    { name: "test",   type: "a" },
    { name: "ruby",   type: "c" },
    { name: "erlang", type: "a" },
];

I want to find items based on the item property. I currently do it using jQuery. something like this;

Array.prototype.find_by_key = function(key, value) {
    return $.grep(this, function(item){
        return (item[key] == value);
    });
}

var whatIHaveFound = anArray.find_by_key("type", "a"); // find items which the item property: "type" equals "a"

is there some better way to do this in javascript? or is there some algorithm to do this better and quickly? when the array has many items. this may be very slow. any ideas? thanks.

Answer 1

Wiser minds may correct me, but I would think you're going to have to iterate through every time (at more or less similar speeds), unless:

You know that you're going to repeat searches and that some keys are more likely to be searched than others. You might bias the collection then so that it's not flat, but is presorted according to your terms. Thus your collection would become:

var groupedByType = 
{"a":[{name:"scala"},{name:"test"}, {name:"erlang"}],  
{"b":[{name:"abc"}],  
{"c":[{name:"ruby"}]};

Alternatively you might try memoizing your collection access, such that after you've done a search you record the search terms and results, in this case storing it in the memo cache as

["type","a"]:[
{ name: "scala",  type: "a" },  
{ name: "test",   type: "a" },  
{ name: "erlang", type: "a" }]

Pros and cons of this: It's very fast to access previously executed searches, if the underlying data has not changed in a way that deprecates your cache. On the other hand, it means that you have to control data access (I like to store my data inside a closure in these cases, so that I only have to expose mutators - sort of a lightweight OO but with more protection), and you may find it more performant to discard your cached data when it's modified than to try to work out deltas, depending on how your data is structured.

What I would emphasize above everything else though, is to make absolutely sure that you need any optimization at all. Is this subsection fast enough? Can you bring your app up to speed another way? If you're writing a clientside search engine or something, you're probably going to want to go a little bit further into it than just working out which of the jQuery iterators is fastest.