Efficient way to iterate over elements of array for matching contents of another array

Question

Using jQuery I'm trying to find an efficient way to iterate through an array excludeMe and check if elements from another array needsExclusions are contained in the excludeMe array. Not sure if this is the most efficient, but it works. Fiddle here: http://jsfiddle.net/yef9q/3/

//Iterate through needsExclusions for an excludeMe string
//someFlag raised on matching strings
var excludeMe = ["in west", "philadelphia", "born and", "raised"];
var needsExclusions = ["philadelphia", "raised"];
var someFlag = true;
$.each(excludeMe, function(i,val) {
 //alert("value: " + val);
 if ($.inArray(val, needsExclusions) != -1) {
 alert("matching value: " + val);
 someFlag = false; 
 }
});

• megawac: Sounds like your looking for an intersection algorithm
• David Harkness: @megawac While the result can be determined from the intersection (it's not empty), the code above merely tests whether the two sets are disjoint which is faster to calculate when they have at least one element in common.
• megawac: @DavidHarkness it seems so, its hard to tell with that alert what the asker is looking for

Answer 1

Your particular example gets 10 times faster by just removing the jQuery and using a for loop and .indexOf() instead of the jQuery versions. It's also worth stopping the iteration when you find an excluded value since you don't need to look any more once the flag is already set:

var excludeMe = ["in west", "philadelphia", "born and", "raised"];
var needsExclusions = ["philadelphia", "raised"];
var someFlag = true;
for (var i = 0; i < excludeMe.length; i++) {
 if (needsExclusions.indexOf(excludeMe[i]) !== -1) {
 someFlag = false; 
 break;
 }
}

Here's a jsperf that illustrates the speed difference: http://jsperf.com/exclusion-test

If you had a much large data set, then it might pay off to put the needsExclusions values into an object to serve as a direct lookup index (faster than array.indexOf()), but that's probably only faster when the list gets a lot longer because there's setup overhead to build the initial index.

• megawac: added an ugly implementation to ur jsperf to just to be annoying (jsperf.com/exclusion-test/2) :)
• MannfromReno: very helpful, thank you! and I like that jsperf site, I had never seen that before.
• jfriend00: @MannfromReno - yeah, pretty much any performance related question can really only be answered with testing and jsperf is often very useful for performance comparisons.
• David Harkness: @megawac There's a bug in the while-loop version: it stops on the first non-match instead of the first match, but it's still faster once fixed.

Answer 2

Very similar to jfriend00's answer, just using a different setup for the loop:

var excludeMe = ["in west", "philadelphia", "born and", "raised"];
var needsExclusions = ["philadelphia", "raised"];
var someFlag = true;
for( var i = 0, l = excludeMe.length ; i < l && someFlag ; i++ ) {
 someFlag = needsExclusions.indexOf(excludeMe[i]) === -1;
}

If something from excludeMe is found in needsExclusion, someFlag gets set to false, and the loop exits, since it'll only loop while i < l && someFlag.

And yes, definitely skip jQuery. You're just working with simple arrays here, no need to bring in jQuery for that.

On another note: Your naming is very confusing. The two arrays are named so similarly that I had to do several double-takes before I knew what was what.

Given that it's an example, I don't know what the actual names should be, but I'd recommend something like someArray for the input, and blacklist for the items that must not be in someArray. Clearer that way.

• MannfromReno: thank you, yes I know I just threw together some random names, they're named completely different and more intuitive in my solution.