ما هي الطريقة الأسرع أو الأكثر أناقة لحساب اختلاف محدد باستخدام صفيفات JavaScript؟

Question

يترك A و B يكون مجموعتين. أبحث عن حقا طرق سريعة أو أنيقة لحساب فرق المجموعة (A - B أو A \B, ، اعتمادا على تفضيلاتك) بينهما. يتم تخزين المجموعتين ومعالجتها كصفائف JavaScript، كما يقول العنوان.

ملاحظات:

• الحيل الخاصة بأشغازو بخير
• أفضل الالتصاق بالوظائف الأصلية (لكنني منفتح على مكتبة خفيفة الوزن إذا كانت أسرع)
• لقد رأيت، ولكن لم يتم اختبارها، js.Set.Set. (انظر النقطة السابقة)

يحرر: لاحظت تعليق حول مجموعات تحتوي على عناصر مكررة. عندما أقول "تعيين" أشير إلى التعريف الرياضي، مما يعني (من بين أمور أخرى) أنهم لا يحتويون على عناصر مكررة.

Answer 1

إذا كنت لا تعرف ما إذا كان هذا أكثر فعالية، ولكن ربما أقصر

A = [1, 2, 3, 4];
B = [1, 3, 4, 7];

diff = A.filter(function(x) { return B.indexOf(x) < 0 })

console.log(diff);

تم التحديث إلى ES6:

A = [1, 2, 3, 4];
B = [1, 3, 4, 7];

diff = A.filter(x => !B.includes(x) );

console.log(diff);

Answer 2

حسنا، بعد 7 سنوات، مع مجموعة ES6 الكائن من السهل جدا (ولكن لا يزال غير مضغوط كأوروبا أ - ب)، وبحسب ما ورد أسرع من indexOf للحصول على صفائف كبيرة:

console.clear();
let a = new Set([1, 2, 3, 4]);
let b = new Set([5, 4, 3, 2]);


let a_minus_b = new Set([...a].filter(x => !b.has(x)));
let b_minus_a = new Set([...b].filter(x => !a.has(x)));
let a_intersect_b = new Set([...a].filter(x => b.has(x))); 

console.log([...a_minus_b]) // {1}
console.log([...b_minus_a]) // {5}
console.log([...a_intersect_b]) // {2,3,4}

Answer 3

يمكنك استخدام كائن كخريطة لتجنب المسح الخطي B لكل عنصر من عناصر A كما في إجابة User187291:

function setMinus(A, B) {
    var map = {}, C = [];

    for(var i = B.length; i--; )
        map[B[i].toSource()] = null; // any other value would do

    for(var i = A.length; i--; ) {
        if(!map.hasOwnProperty(A[i].toSource()))
            C.push(A[i]);
    }

    return C;
}

غير قياسي toSource() طريقة يستخدم للحصول على أسماء الملكية الفريدة؛ إذا كانت جميع العناصر لديها بالفعل تمثيلات سلسلة فريدة (كما هو الحال مع الأرقام)، يمكنك تسريع الرمز عن طريق إسقاط toSource() الدعوات.

Answer 4

أقصر، باستخدام jQuery، هو:

var A = [1, 2, 3, 4];
var B = [1, 3, 4, 7];

var diff = $(A).not(B);

console.log(diff.toArray());

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>

Answer 5

أود الحصول على الصفيف B، ثم احتفظ بالقيم من مجموعة غير موجودة في B:

function getHash(array){
  // Hash an array into a set of properties
  //
  // params:
  //   array - (array) (!nil) the array to hash
  //
  // return: (object)
  //   hash object with one property set to true for each value in the array

  var hash = {};
  for (var i=0; i<array.length; i++){
    hash[ array[i] ] = true;
  }
  return hash;
}

function getDifference(a, b){
  // compute the difference a\b
  //
  // params:
  //   a - (array) (!nil) first array as a set of values (no duplicates)
  //   b - (array) (!nil) second array as a set of values (no duplicates)
  //
  // return: (array)
  //   the set of values (no duplicates) in array a and not in b, 
  //   listed in the same order as in array a.

  var hash = getHash(b);
  var diff = [];
  for (var i=0; i<a.length; i++){
    var value = a[i];
    if ( !hash[value]){
      diff.push(value);
    }
  }
  return diff;
}

Answer 6

دمج فكرة كريستوف وتفيد بضعة أساليب التكرار غير القياسية على المصفوفات والأشياء / التجزئة (each والأصدقاء)، يمكننا الحصول على فرق فرق، الاتحاد والتقاطع في الوقت الخطي في حوالي 20 خطوط المجموع:

var setOPs = {
  minusAB : function (a, b) {
    var h = {};
    b.each(function (v) { h[v] = true; });
    return a.filter(function (v) { return !h.hasOwnProperty(v); });
  },
  unionAB : function (a, b) {
    var h = {}, f = function (v) { h[v] = true; };
    a.each(f);
    b.each(f);
    return myUtils.keys(h);
  },
  intersectAB : function (a, b) {
    var h = {};
    a.each(function (v) { h[v] = 1; });
    b.each(function (v) { h[v] = (h[v] || 0) + 1; });
    var fnSel = function (v, count) { return count > 1; };
    var fnVal = function (v, c) { return v; };
    return myUtils.select(h, fnSel, fnVal);
  }
};

هذا يفترض ذلك each و filter يتم تعريفها للمصفوفات، وأن لدينا طريقتان فائدة:

• myUtils.keys(hash): إرجاع مجموعة مع مفاتيح التجزئة

• myUtils.select(hash, fnSelector, fnEvaluator): إرجاع صفيف مع نتائج الدعوة fnEvaluatorعلى أزواج المفتاح / القيمة التيfnSelector إرجاع صحيح.

ال select() مستوحاة فضفاضة من LISP المشتركة، وهي مجرد filter() و map() دخلت واحدة. (سيكون من الأفضل أن يكون لهم محددة Object.prototype, ، ولكن القيام بذلك تحطيم الخراب مع مسج، لذلك استقرت لأساليب المرافق الثابتة.)

الأداء: اختبار مع

var a = [], b = [];
for (var i = 100000; i--; ) {
  if (i % 2 !== 0) a.push(i);
  if (i % 3 !== 0) b.push(i);
}

يعطي مجموعتين مع عناصر 50،000 و 6666 666. مع هذه القيم، يستغرق AB حوالي 75 مللي ثانية، في حين أن الاتحاد والتقاطع حوالي 150 سم. (Mac Safari 4.0، باستخدام تاريخ JavaScript للتوقيت.)

أعتقد أن هذا مهدئ لائق لمدة 20 خطا من التعليمات البرمجية.

Answer 7

استخدام underscore.js. (مكتبة JS الوظيفية)

>>> var foo = [1,2,3]
>>> var bar = [1,2,4]
>>> _.difference(foo, bar);
[4]

Answer 8

بعض الوظائف البسيطة، الاقتراض من إجابة @ ميلان:

const setDifference = (a, b) => new Set([...a].filter(x => !b.has(x)));
const setIntersection = (a, b) => new Set([...a].filter(x => b.has(x)));
const setUnion = (a, b) => new Set([...a, ...b]);

الاستعمال:

const a = new Set([1, 2]);
const b = new Set([2, 3]);

setDifference(a, b); // Set { 1 }
setIntersection(a, b); // Set { 2 }
setUnion(a, b); // Set { 1, 2, 3 }

Answer 9

بالنسبة للطريقة الصامتة، هذا ليس أنيقا للغاية لكنني قمت بتشغيل بعض الاختبارات للتأكد. تحميل مجموعة واحدة ككائن أسرع بكثير معالجتها بكميات كبيرة:

var t, a, b, c, objA;

    // Fill some arrays to compare
a = Array(30000).fill(0).map(function(v,i) {
    return i.toFixed();
});
b = Array(20000).fill(0).map(function(v,i) {
    return (i*2).toFixed();
});

    // Simple indexOf inside filter
t = Date.now();
c = b.filter(function(v) { return a.indexOf(v) < 0; });
console.log('completed indexOf in %j ms with result %j length', Date.now() - t, c.length);

    // Load `a` as Object `A` first to avoid indexOf in filter
t = Date.now();
objA = {};
a.forEach(function(v) { objA[v] = true; });
c = b.filter(function(v) { return !objA[v]; });
console.log('completed Object in %j ms with result %j length', Date.now() - t, c.length);

نتائج:

completed indexOf in 1219 ms with result 5000 length
completed Object in 8 ms with result 5000 length

ومع ذلك، هذا يعمل مع سلاسل فقط. وبعد إذا كنت تخطط لمقارنة مجموعات مرقمة، فستحتاج إلى تعيين النتائج parfefloat..

Answer 10

هذا يعمل، لكنني أعتقد أن واحد آخر هو أقصر وأقل بكثير

A = [1, 'a', 'b', 12];
B = ['a', 3, 4, 'b'];

diff_set = {
    ar : {},
    diff : Array(),
    remove_set : function(a) { ar = a; return this; },
    remove: function (el) {
        if(ar.indexOf(el)<0) this.diff.push(el);
    }
}

A.forEach(diff_set.remove_set(B).remove,diff_set);
C = diff_set.diff;