Qual è il modo più efficiente di filtrare un array in base al contenuto di un altro array?
-
03-07-2019 - |
Domanda
Supponiamo che io abbia due matrici, elementi e removeItems e che volessi che qualsiasi valore trovato in removeItems fosse rimosso dagli elementi.
Il meccanismo della forza bruta sarebbe probabilmente:
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]);
}
}
Questo è cosa? O (N ^ 2)? C'è un modo più efficiente?
Soluzione
Questo è in realtà O (M * N)
.
Probabilmente potresti fare meglio a ordinare prima l'array animals
, quindi fare una ricerca binaria. Sarai in grado di ridurre a O (N * log N)
- bene, questo è se log N < M
comunque.
Ad ogni modo, se stai lavorando con JS e questo funziona sul lato client, prova semplicemente a mantenere una quantità minima di dati, altrimenti i loro browser ti grideranno con ogni richiesta.
Altri suggerimenti
Fondamentalmente quello che vuoi fare è calcolare in modo efficiente la differenza impostata S \ T. Il modo (asintoticamente) più veloce che conosco è mettere T in una hashmap (che fa passi | T |) e ripassare ogni s in S ( che fa | S | passi) controllando se in T (che è O (1)). Quindi si arriva ai passaggi O (| T | + | S |).
Con jQuery è abbastanza facile:
function is_mammal(animal)
{
return $.inArray(animal, nonMammals) == -1;
}
mammals = $.grep(animals, is_mammal);
Consulta i documenti per $ .grep
e $ .inArray
.