What's the most efficient way of filtering an array based on the contents of another array?
-
03-07-2019 - |
Question
Say I have two arrays, items and removeItems and I wanted any values found in removeItems to be removed from items.
The brute force mechanism would probably be:
var animals = ["cow","dog","frog","cat","whale","salmon","zebra","tuna"];
var nonMammals = ["salmon","frog","tuna","spider"];
var mammals = [];
var isMammal;
for(var i=0;i<animals.length;i++){
isMammal = true;
for(var j=0;j<nonMammals;j++){
if(nonMammals[j] === animals[i]){
isMammal = false;
break;
}
}
if(isMammal){
mammals.push(animals[i]);
}
}
This is what? O(N^2)? Is there a more efficient way?
Solution
That's actually O(M * N)
.
Probably you could do better sorting the animals
array first, then doing a binary search. You'll be able to reduce to O(N * log N)
- well, that's if log N < M
anyway.
Anyway, if you're working with JS and that runs client-side, then just try to keep amount of data at minimum, or their browsers will yell at you with every request.
OTHER TIPS
Basically what you want to do is efficiently compute the set difference S \ T. The (asymptotically) fastest way I know is to put T into a hashmap (that makes |T| steps) and go over each s in S (that makes |S| steps) checking wether s in T (which is O(1)). So you get to O(|T| + |S|) steps.