¿Cuál es la forma más eficiente de filtrar una matriz basada en el contenido de otra matriz?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

Con jQuery es bastante fácil:

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

mammals = $.grep(animals, is_mammal);

Ver documentos para $.grep y $.inArray .