ما هي الطريقة الأكثر فعالية لتصفية مصفوفة بناءً على محتويات مصفوفة أخرى؟

Question

لنفترض أن لدي صفيفين وعناصر و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]);
   }
}

هذا هو ما؟يا (ن ^ 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.