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

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

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

Answer 1

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

Answer 2

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

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

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

Answer 3

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

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

mammals = $.grep(animals, is_mammal);

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