CODEWITHSUNDEEP
javascriptarrays
Alex
Alex

Reputation: 71

Javascript return position index of "matched" array within array

Is there an alternative, faster method of returning the position/index of part of an array within another array (where multiple values match)? It's called a lot within my pathfinding algorithm so could do with being as fast as possible.

My current function is:

// Haystack can be e.g. [[0,1,278.9],[4,4,22.1212]]

function coordinate_location_in_array(needle,haystack){
    for(n in haystack){
        if(haystack[n][0]==needle[0] && haystack[n][1]==needle[1]) return n;
    }
    return false;
}

// Needle of [0,1]: returns 0
// Needle of [4,4]: returns 1
// Needle of [6,7]: returns false

Edit:

I've been messing around a bit and come up with a (rather ghastly) string manipulation-based method (thereby avoiding the costly for loop). I think it's still slightly slower. Could anybody benchmark these methods?

function coordinate_location_in_array(needle,haystack) {
    var str1 = ':' + haystack.join(':');
    var str2 = str1.replace(':'+needle[0]+','+needle[1],'*').split('*')[0]; 
    if(str2.length == str1.length) return false;
    var preceedingElements = str2.match(/:/g);
    return preceedingElements!=null?preceedingElements.length:0;
}

Perhaps with some improvements this second method might provide some performance gain?

Edit 2:

Bench marked all 3 described methods using jsperf.com (initial method is fastest): http://jsperf.com/finding-matched-array-within-array/3

Edit 3:

Just replaced the for(..in..) loop with a for(..;..;..) loop (since I know that the haystack array will never have "gaps") and performance seems to have significantly improved:

function coordinate_location_in_array(needle,haystack){
    for(var n=0;n<haystack.length;n++){
        if(haystack[n][0]==needle[0] && haystack[n][1]==needle[1]) return n;
    }
    return false;
}

I've updated the jsperf page to include this latest method.

Upvotes: 1

Views: 343

Answers (4)

Alan Curry
Alan Curry

Reputation: 14731

Seems to me this is just a substring search but with numbers instead of characters being the components of the string. As such, Boyer-Moore could be applicable, especially if your needles and haystacks get big.

Upvotes: 0

Alex
Alex

Reputation: 71

Using a for(..;..;..) loop rather than a for(..in..) loop made the biggest difference.

(See Edit 3 at the end of the question)

Upvotes: 0

laidback
laidback

Reputation: 555

i don't know if its faster, but you can do something like:

[1,2,3,4].slice(0,2).toString() == [1,2].toString()

in your case it would be:

function coordinate_location_in_array(needle,haystack){
for(n in haystack){
    if(haystack[n].slice(0,2).toString() == needle.toString()) return n
}
return false;

}

Also found this post, which covers comparison of JS arrays: compare-two-arrays-javascript-associative

Cheers Laidback

Upvotes: 0

Caleb
Caleb

Reputation: 1088

If the "haystack" isn't sorted then there isn't a way to make it faster. Not knowing how the elements in a collection are ordered makes finding something out of it linear by nature, because you just have to check each thing.

If you are using this function over the same "haystack" over and over, you could sort the collection, and use the sorting to make it quicker to find the "needle" (look up different sorting and search algorithms to find one that fits your need best, such as using binary search to find the "needle" after haystack is sorted.)

Upvotes: 2

Related Questions