Was ist der effizienteste Weg, eine Anordnung auf dem Inhalt eines anderen Array anhand von Filtern?

Question

Sagen, ich habe zwei Arrays, Gegenstände und removeItems und ich wollte in removeItems gefunden alle Werte aus den Gegenständen entfernt werden.

Der Brute-Force-Mechanismus wäre wahrscheinlich:

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

Dies ist, was? O (N ^ 2)? Gibt es eine effizientere Art und Weise?

Answer 1

Das ist eigentlich O(M * N).

Wahrscheinlich könnte man besser machen die animals Array Sortierung zuerst, dann eine binäre Suche zu tun. Sie werden in der Lage zu O(N * log N) zu reduzieren -. Gut, das ist, wenn log N < M sowieso

Wie auch immer, wenn Sie mit JS arbeiten und das läuft clientseitige, dann versucht nur zu minimaler Menge von Daten zu halten oder ihr Browser mit jeder Anfrage an Sie schreit.

Answer 2

Im Grunde, was Sie tun möchten, ist effizient die eingestellte Differenz S \ T. Die Berechnung (asymptotisch) schnellste Weg, ich weiß, ist T in eine hashmap zu setzen (das macht | T | Stufen) und gehen jeweils in S s ( das macht | S | Stufen) Überprüfung, ob s in T (die O (1)). So erhalten Sie auf O (| T | + | S |). Schritte

Answer 3

Mit jQuery ist es ziemlich einfach:

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

mammals = $.grep(animals, is_mammal);

Siehe Dokumentation für $.grep und $.inArray .