Какой наиболее эффективный способ фильтрации массива на основе содержимого другого массива?

Question

Допустим, у меня есть два массива: items и RemoveItems, и я хочу, чтобы все значения, найденные в RemoveItems, были удалены из элементов.

Механизм грубой силы, вероятно, будет следующим:

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

Это то, что?О(N^2)?Есть ли более эффективный способ?

Answer 1

Это на самом деле O(M * N).

Возможно, вы могли бы лучше сортировать animals сначала массив, а затем выполняем двоичный поиск.Вы сможете сократить до O(N * log N) - ну это если log N < M в любом случае.

В любом случае, если вы работаете с JS и он работает на стороне клиента, просто постарайтесь свести объем данных к минимуму, иначе их браузеры будут кричать на вас при каждом запросе.

Answer 2

По сути, вам нужно эффективно вычислить разность наборов S \ T.Самый (асимптотически) самый быстрый способ, который я знаю, — это поместить T в хэш-карту (которая делает шаги |T|) и просматривать каждый s в S (что делает шаги |S|), проверяя, есть ли s в T (что равно O(1) ).Таким образом, вы доберетесь до O(|T| + |S|) шагов.

Answer 3

С jQuery это довольно просто:

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

mammals = $.grep(animals, is_mammal);

См. документы для $.grep и $.inArray.