¿Cuál es la forma más eficiente de filtrar una matriz basada en el contenido de otra matriz?
-
03-07-2019 - |
Pregunta
Digamos que tengo dos matrices, elementos y removeItems y quería que los valores encontrados en removeItems se eliminen de los elementos.
El mecanismo de fuerza bruta probablemente sería:
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]);
}
}
¿Esto es qué? O (N ^ 2)? ¿Hay alguna forma más eficiente?
Solución
Eso es en realidad O(M * N)
.
Probablemente podría ser mejor ordenar primero la matriz animals
, luego hacer una búsqueda binaria. Podrá reducir a O(N * log N)
- bueno, eso es si log N < M
de todos modos.
De todos modos, si está trabajando con JS y eso se ejecuta en el lado del cliente, intente mantener la cantidad de datos al mínimo, o sus navegadores le gritarán con cada solicitud.
Otros consejos
Básicamente, lo que quiere hacer es calcular eficientemente la diferencia de conjunto S \ T. La forma (asintóticamente) más rápida que conozco es colocar T en un mapa hash (que hace | T | pasos) y revisar cada s en S ( eso hace que | S | pasos) compruebe si s en T (que es O (1)). Entonces llegas a O (| T | + | S |) pasos.