Quel est le moyen le plus efficace de filtrer un tableau en fonction du contenu d'un autre tableau?

Question

Disons que j'ai deux tableaux, éléments et removeItems et que je souhaitais que toutes les valeurs trouvées dans removeItems soient supprimées des éléments.

Le mécanisme de force brute serait probablement:

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]);
   }
}

C'est quoi? O (N ^ 2)? Y a-t-il un moyen plus efficace?

Answer 1

C'est en fait O(M * N).

Vous pourriez probablement faire mieux de trier le tableau animals d'abord, puis d'effectuer une recherche binaire. Vous pourrez réduire à O(N * log N) - eh bien, c'est si log N < M de toute façon.

Quoi qu'il en soit, si vous travaillez avec JS et qu'il fonctionne côté client, essayez simplement de limiter la quantité de données au minimum, sinon leur navigateur vous hurle dessus à chaque demande.

Answer 2

En gros, vous voulez calculer efficacement la différence définie S \ T. Le moyen le plus rapide (asymptotiquement) que je connaisse est de mettre T dans une table de hachage (qui fait | T | étapes) et de passer en revue chaque s dans S ( cela fait | S | étapes) en vérifiant si s dans T (qui est O (1)). Vous arrivez donc aux étapes O (| T | + | S |).

Answer 3

Avec jQuery, c'est assez facile:

function is_mammal(animal)
{
    return $.inArray(animal, nonMammals) == -1;
}

mammals = $.grep(animals, is_mammal);

Voir la documentation pour $.grep et $.inArray .