Quelle est la façon de calculer une différence de jeu la plus rapide ou la plus élégante en utilisant des tableaux Javascript?

Question

Laissez A et B deux ensembles. Je cherche vraiment moyens rapides ou élégants pour calculer la différence de consigne (ou A - B A \B, selon votre préférence) entre eux. Les deux ensembles sont stockés et manipulés sous forme de tableaux Javascript, comme le dit le titre.

Notes:

• astuces spécifiques Gecko sont ok
• Je préfère coller à des fonctions natives (mais je suis ouvert à une bibliothèque légère si elle est beaucoup plus rapide)
• Je l'ai vu, mais pas testé, JS.Set (voir point précédent)

Modifier J'ai remarqué un commentaire sur les jeux contenant des éléments en double. Quand je dis « set » Je fais référence à la définition mathématique, ce qui signifie (entre autres) qu'ils ne contiennent pas d'éléments en double.

Answer 1

ne sais pas si cela est plus efficace, mais peut-être le plus court

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

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

console.log(diff);

Mise à jour à ES6:

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

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

console.log(diff);

Answer 2

Eh bien, 7 ans plus tard, Set de ES6 objet, il est assez facile (mais toujours pas aussi compact que pythons A - B), et aurait été plus rapide que indexOf pour les grands tableaux:

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

Vous pouvez utiliser un objet comme une carte pour éviter le balayage linéaire B pour chaque élément de A comme dans réponse 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() de href="https://developer.mozilla.org/en/Core_JavaScript_1.5_Reference/Objects/Object/toSource" est utilisé pour obtenir les noms de propriétés uniques; si tous les éléments ont déjà des représentations de chaîne unique (comme est le cas avec des chiffres), vous pouvez accélérer le code en laissant tomber les invocations de toSource().

Answer 4

Le plus court, en utilisant jQuery, est:

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

Je hachage du tableau B, puis garder les valeurs du tableau A ne présente en 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

L'intégration de l'idée de Christoph et en supposant deux méthodes d'itération non standard sur les tableaux et les objets / hashes (each et amis), nous pouvons en établir la différence, union et intersection dans le temps linéaire dans environ 20 lignes au total:

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

Cela suppose que each et filter sont définis pour les tableaux, et que nous avons deux méthodes utilitaires:

• myUtils.keys(hash): retourne un tableau avec les clés du hachage

• myUtils.select(hash, fnSelector, fnEvaluator): retourne un tableau avec les résultats de l'appel fnEvaluator sur les paires clé / valeur pour laquelle fnSelector renvoie true.

Le select() est inspiré de manière lâche par Common Lisp, et est simplement filter() et map() en un. (Il serait préférable de les avoir définis sur Object.prototype, mais faire des ravages avec épaves si jQuery, donc je réglé pour les méthodes utilitaires statiques).

Performance: Test avec

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

donne deux ensembles avec 50.000 et 66,666 éléments. Avec ces valeurs A-B prend environ 75 ms, alors que l'union et l'intersection sont environ 150ms chacun. (Mac Safari 4.0, en utilisant Javascript date pour le moment.)

Je pense que ce gain décent pour 20 lignes de code.

Answer 7

Utilisation Underscore.js (bibliothèque pour JS fonctionnelle)

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

Answer 8

Certaines fonctions simples, emprunt de @ réponse de milan:

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

Utilisation:

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

En ce qui concerne la façon dont jeûnaient, ce n'est pas si élégant mais j'ai quelques tests pour être sûr. Chargement d'un tableau comme un objet est beaucoup plus rapide à traiter en grandes quantités:

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

Résultats:

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

Cependant, cela fonctionne avec chaînes uniquement . Si vous envisagez de comparer des ensembles numérotés vous voulez mapper les résultats avec parseFloat .

Answer 10

Cela fonctionne, mais je pense que un autre est beaucoup plus courte et élégante aussi

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;