Qual é a maneira mais eficiente de filtragem uma matriz com base no conteúdo de uma outra matriz?

Question

Say Eu tenho duas matrizes, itens e removeItems e eu queria quaisquer valores encontrados em removeItems a ser removidos de itens.

O mecanismo de força bruta provavelmente seria:

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

Este é o quê? O (N ^ 2)? Existe uma maneira mais eficiente?

Answer 1

Isso é realmente O(M * N).

Provavelmente você poderia fazer melhor classificação da matriz animals primeiro, depois fazer uma busca binária. Você vai ser capaz de reduzir a O(N * log N) - Bem, isso é, se log N < M qualquer maneira

.

De qualquer forma, se você estiver trabalhando com JS e que corre do lado do cliente, então é só tentar manter quantidade de dados no mínimo, ou seus navegadores vai gritar com você com cada pedido.

Answer 2

Basicamente o que você quer fazer é eficientemente calcular a diferença do conjunto S \ T. A maneira (assintoticamente) mais rápido que eu sei é colocar T em um hashmap (que faz | T | etapas) e passar por cima de cada s em S ( isso faz com que | s | passos) verificação meteorológicas s em T (que é O (1)). Então você começa a O (| T | + | S |). Etapas

Answer 3

Com jQuery é muito fácil:

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

mammals = $.grep(animals, is_mammal);

Veja docs para $.grep e $.inArray .