Каков самый быстрый или самый изящный способ вычислить разность множеств с помощью массивов JavaScript?

Это работает, но я думаю, что другой намного короче и изящнее

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;

Я бы хэшировал массив B, а затем сохранял значения из массива A, отсутствующего в 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;
}

Вы можете использовать объект в качестве карты, чтобы избежать линейного сканирования 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 () .

Включая идею Кристофа и допуская пару нестандартных методов итерации для массивов и объектов / хэшей ( каждый и другие), мы можем получить разность множеств, объединение и пересечение за линейное время примерно в 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);
  }
};

Это предполагает, что каждый и фильтр определены для массивов, и что у нас есть два вспомогательных метода:

• myUtils. keys (hash) : возвращает массив с ключами хэша

• myUtils.select (hash, fnSelector, fnEvaluator) : возвращает массив с результаты вызова fnEvaluator на парах ключ / значение, для которых fnSelector возвращает true.

select () в некоторой степени вдохновлен Common Lisp и представляет собой просто filter () и map () в одном лице. (Было бы лучше, если бы они были определены в Object.prototype , но это нанесет ущерб jQuery, поэтому я остановился на статических служебных методах.)

Производительность: Тестирование с

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

дает два набора с 50 000 и 66 666 элементами. При этих значениях AB занимает около 75 мс, а объединение и пересечение - около 150 мс каждое. (Mac Safari 4.0, с использованием Javascript Date для измерения времени.)

Я думаю, что это достойная плата за 20 строк кода.