別の配列の内容に基づいて配列をフィルタリングする最も効率的な方法は何ですか？

Question

itemsとremoveItemsの2つの配列があり、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

実際にはO(M * N)です。

おそらくanimals配列を最初にソートしてから、バイナリ検索を実行する方が良いでしょう。 O(N * log N)に減らすことができます-とにかくlog N < Mの場合です。

とにかく、JSで作業していてクライアント側で実行している場合は、データの量を最小限に抑えるようにしてください。そうしないと、ブラウザがリクエストごとに怒鳴ります。

Answer 2

基本的にあなたがしたいことは、セット差S \ Tを効率的に計算することです。私が知っている（漸近的に）最速の方法は、Tをハッシュマップに入れて（| T |ステップ）、Sの各s（ | S |ステップ）Tのsをチェックします（これはO（1）です）。したがって、O（| T | + | S |）ステップになります。

Answer 3

jQueryを使用すると、非常に簡単です。

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

mammals = $.grep(animals, is_mammal);

$.grep および $.inArray 。