Comment obtenir la différence entre deux tableaux en Javascript?
Est-il un moyen de retourner la différence entre deux tableaux en JavaScript?
Par exemple:
var a1 = ['a', 'b'];
var a2 = ['a', 'b', 'c', 'd'];
//need ["c", "d"]
Des conseils très apprécié.
- Symétrique ou non symétrique?
- Avec de nouveaux ES6 fonction de ce qui peut être fait comme un simple liner (il faudra beaucoup de temps pour être en mesure d'utiliser dans tous les principaux navigateurs). Dans tous les cas vérifier mon répondre
- un aspect important de la solution est la performance. le temps asymptotique de la complexité de ce type d'opération dans d'autres langues, est
O(a1.length x log(a2.length))
- est-ce possible de performances en JavaScript?
Vous devez vous connecter pour publier un commentaire.
Je suppose que vous comparez un tableau normal. Si non, vous avez besoin de changer la pour boucle à un pour .. dans boucle.
JS:
Une meilleure solution, si vous n'avez pas de soins sur la rétro-compatibilité, est à l'aide de filtre. Mais encore, cette solution fonctionne.
var a1 = ['a', 'b'];
etvar a2 = ['a', 'b', 'c', 'd', 'b'];
, il sera de retour en cas de réponse incorrecte, c'est à dire['c', 'd', 'b']
au lieu de['c', 'd']
.function diff2(a, b) { var i, la = a.length, lb = b.length, res = []; if (!la) return b; else if (!lb) return a; for (i = 0; i < la; i++) { if (b.indexOf(a[i]) === -1) res.push(a[i]); } for (i = 0; i < lb; i++) { if (a.indexOf(b[i]) === -1) res.push(b[i]); } return res; }
JS:
Note indexOf et le filtre ne sont pas disponibles dans ie avant d'ie9.
[1,2,3].diff([3,4,5])
il sera de retour[1,2]
au lieu de[1,2,4,5]
afin de ne pas résoudre le problème dans la question d'origine, quelque chose d'être conscient de.[1,2,3,4,5,6].diff( [3,4,5,10] );
, votre résultat sera[1, 2, 6]
, plutôt que de l'attendre[1, 2, 6, 10]
.Il ya une meilleure façon à l'aide de ES7:
Intersection
Pour
[1,2,3] [2,3]
il donnera[2,3]
. D'autre part, pour[1,2,3] [2,3,5]
sera de retour la même chose.Différence
Pour
[1,2,3] [2,3]
il donnera[1]
. D'autre part, pour[1,2,3] [2,3,5]
sera de retour la même chose.Pour un symétrique différence, vous pouvez le faire:
De cette façon, vous obtiendrez un tableau contenant tous les éléments de arr1 qui ne sont pas dans arr2 et vice-versa
Comme @Joshaven Potter remarquer lors de sa réponse, vous pouvez les ajouter à la Matrice.prototype de sorte qu'il peut être utilisé comme ceci:
< 0
au lieu de== -1
Array
différence est ce qu'on appelleset operation
, parce que la recherche de propriété est le propre du travail deSet
, qui sont des ordres de grandeur plus rapide queindexOf
/includes
. Tout simplement, votre solution est très inefficace et plutôt lent.Set
, les valeurs doivent être uniques, non?[1,2,3] [2,3,5]
étant donné que les chiffres sont uniques, mais si vous aviez dire[1,1,2,3] [1,2,3,5]
et devrait[1]
vous ne pouviez pas utiliserSet
. Votre solution ne fonctionne pas, soit si :-/ j'ai fini la création de cette fonction parce que je ne pouvais pas trouver un moyen efficace de le faire de façon plus succincte. Si vous avez des idées sur la façon de le faire, j'aimerais savoir!Array.includes()
ES7 plutôt la fonction de l'ES6? (1) (2) et pour continuer, avec ES6 vous pouvez utiliserArray.some()
par exemplelet intersection = aArray.filter(a => bArray.some(b => a === b))
, non?Array.prototype.diff = arr1.filter(x => arr2.includes(x)); ^ ReferenceError: arr1 is not defined
C'est de loin le moyen le plus facile d'obtenir exactement le résultat que vous recherchez, à l'aide de jQuery:
diff
contient maintenant ce qui était dansold_array
qui n'est pas dansnew_array
{a: 1} != {a: 1}
) (preuve).not
avec un tableau, jQuery utilise l'utilitaire intégré.grep()
qui est spécifiquement pour le filtrage des tableaux. Je ne peux pas voir ce changement.old_array
est celui qui a le plus de valeurs quenew_array
, sinon, il ne renvoie pas la diff... qui suce.O(m x n)
, oùm
est la longueur deold_array
adn
la longueur denew_array
?Ext.Array.difference(array1, array2)
.La méthode de différence dans le trait de Soulignement (ou sa baisse-dans le remplacement, Lo Tableau De Bord) peut le faire aussi:
Comme avec n'importe quel trait de Soulignement de la fonction, vous pouvez également l'utiliser dans une plus orienté objet style:
Plaine JavaScript
Il y a deux intepretations pour la "différence". Je vous laisse choisir celle que vous voulez. Disons que vous avez:
Si vous souhaitez obtenir
['a']
, l'utilisation de cette fonction:Si vous souhaitez obtenir
['a', 'c']
(tous les éléments contenus dans soita1
oua2
, mais pas les deux, ce que l'on appelle symétrique différence), l'utilisation de cette fonction:Lodash /Trait De Soulignement
Si vous utilisez lodash, vous pouvez utiliser
_.différence(a1, a2)
(cas 1 ci-dessus) ou_.xor(a1, a2)
(cas 2).Si vous utilisez Underscore.js, vous pouvez utiliser le
_.différence(a1, a2)
fonction pour le cas 1.ES6 Ensemble, pour de très grands tableaux
Le code ci-dessus fonctionne sur tous les navigateurs. Toutefois, pour les grands ensembles de plus de 10 000 éléments, il devient assez lent, car il a de O(n2) de la complexité. Sur de nombreux navigateurs modernes, nous pouvons profiter de l'ES6
Set
objet pour accélérer les choses. Lodash utilise automatiquementSet
quand il est disponible. Si vous n'êtes pas à l'aide de lodash, utilisez la mise en œuvre, inspirée par Axel Rauschmayer du blog:Notes
Le comportement de tous les exemples peut être surprenant ou non évident si vous vous souciez de -0, +0, NaN ou de matrices creuses. (Pour la plupart des utilisations, ce n'est pas grave.)
Vous pouvez utiliser un Ensemble dans ce cas. Il est optimisé pour ce genre d'opération (union, intersection, différence).
Assurez-vous qu'il s'applique à votre cas, une fois qu'il ne permet pas de doublons.
Set
fonction sans avoir à obtenir tout le reste...Pour obtenir le symétrique différence vous suffit de comparer les tableaux dans les deux sens (ou de toutes les façons dans le cas de plusieurs tableaux)
ES7 (ECMAScript 2016)
ES6 (ECMAScript 2015)
ES5 (ECMAScript 5.1)
Exemple:
Différence entre les Tableaux d'Objets
Exemple:
(x) => !unique.some((y) => x[key] === y[key])
serait un peu mieux que lesfilter(...).length === 0
Fusionner les deux tableaux, les valeurs uniques apparaîtra qu'une seule fois afin indexOf() sera le même que lastIndexOf().
à soustraire un tableau à partir d'un autre, il suffit d'utiliser l'extrait de code ci-dessous:
Il retourne ['1,'2','6'] qui sont les éléments du premier tableau qui n'existe pas dans le second.
Par conséquent, en fonction de votre problème de l'échantillon, d'après le code est la solution exacte:
Une solution à l'aide de
indexOf()
sera ok pour les petits tableaux, mais à mesure qu'ils grandissent dans la longueur de la performance de l'algorithme approchesO(n^2)
. Voici une solution qui fonctionnera mieux pour de très grands tableaux à l'aide d'objets comme des tableaux associatifs pour stocker le tableau des entrées de touches; il élimine aussi les entrées en double automatiquement mais ne fonctionne qu'avec les valeurs de chaîne (ou des valeurs qui peuvent être stockés en toute sécurité comme des chaînes de caractères):Avec l'arrivée de l'ES6 et de décors et de splat opérateur (au moment de la ne fonctionne que sous Firefox, vérifier tableau de compatibilité), vous pouvez écrire la suite d'un liner:
qui entraînera
[ "c", "d" ]
.b.filter(x => !a.indexOf(x)))
O(n + m)
votre solution estO(n * m)
où n et m sont des longueurs de tableaux. Prendre de longues listes et ma solution sera exécuté en quelques secondes, tandis que le vôtre va prendre des heures.a.filter(x => !b1.has(x))
est plus simple. Et de noter les spec ne requiert que la complexité, den * f(m) + m
avecf(m)
sublinéaire en moyenne. C'est mieux quen * m
, mais pas nécessairementn + m
.var difference = a.filter(x => !b1.has(x));
Approche fonctionnelle avec ES2015
Le calcul de la
difference
entre les deux tableaux est l'un desSet
opérations. Le terme l'indique déjà que le natifSet
type doit être utilisé, dans le but d'augmenter la recherche de vitesse. De toute façon, il y a trois permutations lorsque vous calculez la différence entre les deux ensembles:Ici est une solution fonctionnelle qui tient compte de ces permutations.
Gauche
difference
:JS:
Droit
difference
:differencer
est trivial. C'est justedifferencel
retourné avec des arguments. Vous pouvez écrire une fonction pour des raisons de commodité:const differencer = flip(differencel)
. C'est tout!Symétrique
difference
:Maintenant que nous avons la gauche et la droite, la mise en œuvre de l'symétrique
difference
devient trivial ainsi:JS:
Je pense que cet exemple est un bon point de départ pour obtenir une impression de ce que la programmation fonctionnelle signifie:
De la programmation avec les blocs de construction qui peuvent être branchés ensemble dans de nombreuses façons différentes.
La réponse ci-dessus par Joshaven Potter est grande. Mais il renvoie les éléments de la matrice B qui ne sont pas dans la gamme de C, mais pas dans l'autre sens. Par exemple, si
var a=[1,2,3,4,5,6].diff( [3,4,5,7]);
, alors il sera de sortie: ==>[1,2,6]
, mais pas[1,2,6,7]
, qui est la différence réelle entre les deux. Vous pouvez toujours utiliser Potter code ci-dessus, mais simplement refaire la comparaison une fois vers l'arrière trop:Cela devrait sortie:
[ 1, 2, 6, 7 ]
Une autre façon de résoudre le problème
difference
comme fonction dans une version future, et cette fonction a une fonction différente de la signature puis la vôtre, il va casser votre code ou de bibliothèques étrangères qui utilisent cette fonction.Comment à ce sujet:
Ainsi, de cette façon vous pouvez faire
array1.diff(array2)
pour obtenir leur différence (Horrible moment de la complexité de l'algorithme si - O(matrice1.longueur x matrice2.la longueur), je crois)filter
méthode est un ajout récent à JavaScript et n'est pas supportée par tous les navigateurs.Solution très Simple avec la fonction de filtre de JavaScript:
JS:
À l'aide de http://phrogz.net/JS/ArraySetMath.js vous pouvez:
filter
)fn
rappel paramètre vous permet de spécifier la manière de comparer les éléments de tableau deJS:
length
valeurs. C'est déjà la plaine de la propriété. jsperf.com/array-length-cachingCe travail est: fondamentalement fusionner les deux groupes, rechercher les doublons et pousser ce n'est pas dupliquée dans une nouvelle matrice qui est la différence.
JS:
ce qui fonctionne pour moi
Il suffit de penser... pour l'amour d'un défi 😉 serait-ce de travailler... (pour la base des tableaux de chaînes de caractères, nombres, etc.) pas de tableaux imbriqués
Note le tri sera probablement pas comme il est noté ci-dessus... mais si vous le souhaitez, appel .sort() sur le tableau à trier.
Je voulais une fonction similaire qui a pris dans un vieux tableau et un nouveau tableau et m'a donné un tableau des éléments ajoutés et un tableau des éléments supprimés, et je voulais qu'il soit efficace (donc pas .contient!).
Vous pouvez jouer avec ma solution proposée ici: http://jsbin.com/osewu3/12.
Quelqu'un peut voir les problèmes et/ou améliorations de l'algorithme? Merci!
De Code:
littlebit correctif pour la meilleure réponse
cela prendra du type de courant de l'élément en considération. b/c quand on à[a1[i]], il convertit une valeur de chaîne à partir de son oroginal valeur, de sorte que nous avons perdu de la valeur réelle.
Vous pouvez utiliser underscore.js : http://underscorejs.org/#intersection
Vous avez besoin de méthodes pour le tableau :
Cela a été inspirée par le a accepté de répondre par Penseur, mais Penseur de la réponse semble assumer les tableaux sont des ensembles. Il tombe à l'eau si les tableaux sont
[ "1", "2" ]
et[ "1", "1", "2", "2" ]
La différence entre ces tableaux est
[ "1", "2" ]
. La solution suivante est O(n*n), donc pas l'idéal, mais si vous avez de grandes baies, il a de la mémoire des avantages sur le Penseur de la solution.Si vous faites affaire avec, en premier lieu, le Penseur de la solution est certainement mieux. Si vous avez une version récente de Javascript avec l'accès aux filtres, vous devez utiliser ceux aussi bien. Ce n'est que pour ceux qui ne traitons pas avec des décors et utilisez une ancienne version de JavaScript (pour quelque raison que ce soit)...
//es6 approche
Si les tableaux ne sont pas de types simples, puis l'une des réponses ci-dessus peuvent être adaptées:
Cette méthode fonctionne sur les tableaux d'objets complexes.
Simple. Pourrait utiliser avec des objets aussi, vérifiant une propriété de l'objet.
Comme,
encore une autre réponse, mais il semble que personne n'a mentionné jsperf où ils comparer plusieurs algorithmes et de soutien à la technologie: https://jsperf.com/array-difference-javascript semble à l'aide de filtre obtient les meilleurs résultats. grâce
Je cherchais une réponse simple qui n'implique pas l'aide de différentes bibliothèques, et je suis venu avec moi, que je ne pense pas qu'a été mentionné ici.
Je ne sais pas comment elle est efficace ou quoi que ce soit, mais il fonctionne;
Pour mon code j'ai besoin de doublons ainsi, mais je suppose que ce n'est pas toujours préféré.
Je suppose que le principal inconvénient c'est que c'est potentiellement la comparaison de nombreuses options qui ont déjà été rejetées.
En réponse à la personne qui voulait soustraire un tableau à partir d'un autre...
Si pas plus que de dire les éléments de 1000 essayez ceci...
La configuration d'une nouvelle variable à double Array01 et de l'appeler Array03.
Maintenant, l'utilisation de l'algorithme de tri à bulles pour comparer les éléments de Array01 avec Array02 et à chaque fois que vous trouvez une correspondance
effectuez les opérations suivantes pour Array03...
NB: Nous sommes en train de modifier Array03 au lieu de Array01 afin de ne pas bousiller les boucles imbriquées du tri à bulles!
Enfin, copiez le contenu de Array03 à Array01 avec une affectation simple, et vous avez terminé.
Samuel: "Pour mon code j'ai besoin de doublons ainsi, mais je suppose que ce n'est pas toujours préférée.
Je suppose que le principal inconvénient c'est que c'est potentiellement la comparaison de nombreuses options qui ont déjà été rejetées."
Lorsque l'on compare les DEUX listes, les Tableaux, etc, et les éléments sont de moins de 1000, la norme de l'industrie dans le
L3G monde est d'utiliser le tri à bulles qui évite de dupes.
Le code devrait ressembler à quelque chose comme ça... (non testé mais cela devrait fonctionner)
Pour tester la sortie...
Si pas utiliser hasOwnProperty ensuite, nous avons des éléments incorrects. Par exemple:
Ma version:
Contribuer avec jQuery solution que j'utilise actuellement:
Solution rapide. Bien qu'il semble que d'autres ont déjà posté des différentes variantes de la même méthode. Je ne suis pas sûr que c'est le meilleur pour les gros tableaux, mais il travaille pour mes tableaux qui ne sera pas de plus de 10 ou 15.
Différence
b
-a
CoffeeScript version:
Compare simplement toutes les valeurs et retourne un tableau avec les valeurs qui ne se répète pas.
diff
comme fonction dans une version future, et cette fonction a une fonction différente de la signature puis la vôtre, il va casser votre code ou de bibliothèques étrangères qui utilisent cette fonction.Symétrique et linéaire de la complexité. Nécessite l'ES6.
Similaire à Ian Grainger la solution (mais en caractères d'imprimerie):
Il y a beaucoup de problèmes avec les réponses que je lis ici qui en font une valeur limitée dans la pratique de la programmation des applications.
D'abord et avant tout, vous allez vouloir avoir un moyen de contrôler ce que cela signifie pour deux éléments dans le tableau à "l'égalité". L' === comparaison ne va pas le couper, si vous êtes à essayer de comprendre si mettre à jour un tableau d'objets en fonction d'un ID ou quelque chose comme ça, qui, franchement, est probablement l'un des scénarios les plus probables dans lequel vous voulez un diff de la fonction. Il limite également vous aux tableaux de choses qui peut être comparé avec l' === opérateur, c'est à dire chaînes de caractères, entiers, etc, et c'est à peu près inacceptable pour les adultes.
Deuxièmement, il y a trois état des résultats d'une opération diff:
Je pense que cela signifie que vous besoin de pas moins de 2 boucles, mais je suis ouvert à de sales tours si quelqu'un connaît un moyen de la réduire à une seule.
Voici quelque chose que j'ai bricolé, et je tiens à souligner que je NE fais ABSOLUMENT PAS attention à ce qu'il ne fonctionne pas sur les anciennes versions de Microshaft navigateurs. Si vous travaillez à un niveau inférieur environnement de codage comme IE, c'est à vous de la modifier à travailler au sein de l'limitations frustrantes que vous êtes coincé avec.
Cette question est vieux mais c'est toujours la top hit pour tableau javascript soustraction je voulais donc ajouter la solution que j'utilise. Cela correspond pour le cas suivant:
La méthode suivante sera en mesure de produire le résultat désiré:
Il convient de noter que la fonction ne pas inclure les valeurs de la soustraction qui ne sont pas présents dans le minuend:
J'ai essayé toutes ces ci-dessus, mais aucune n'a fonctionné quand vous en avez besoin pour correspondre sans accepter les doublons.
Par exemple:
Serait de retour vide diff tableau car
2
serait trouvé une fois dans le deuxième tableau, même si nous en avons besoin pour correspondre à deux fois.Donc j'ai réussi à arranger quelque chose:
juste de règlage de la chaîne pour assurer.... espaces habitude de nuire à la diff
voici la fonction que j'utilise pour obtenir la différence entre les 2 tableaux, C'est une bonne numérique, chaîne, mixte num/tableaux de chaîne. pas littéral d'objet dans des tableaux /multidimentional tableaux
Si vous êtes le tableau contient des objets qu'il devient un peu plus difficile si vous voulez comparer un attribut.
Heureusement
lodash
c'est assez facile à l'aide de_contains
et_.pluck
:Voici ce que j'utilise:
ou cette un
À la dure (dans le cas où vous voudriez faire quelque chose de plus de fantaisie que .indexOf)
La voie de la facilité
De données:
à l'aide de filtre:
résultat de la différence de deux tableaux
difference
dans une future version et cette fonction a une fonction différente de la signature puis la vôtre, il va casser votre code ou de l'étranger bibliothèques que vous utilisez.Ici est de savoir comment j'obtiens deux tableaux différence. Pur et propre.
Il retourne un objet qui contient [ajouter] et [supprimer].
Vous pouvez utiliser un objet commun et de compter la fréquence de chaque valeur dans le premier tableau. Pour le deuxième tableau, décrémenter la valeur de l'objet courant. Puis itérer sur toutes les touches et ajouter toutes les clés dont la valeur est supérieure à 1.
JS:
La réponse choisie n'est que la moitié droite. Vous devez comparer les tableaux a deux façons d'obtenir une réponse complète.
**Cette fonction retourne un tableau de valeurs uniques, ou un tableau de doubles, ou un tableau de non-double (différence) pour tout 2 des tableaux basés sur le type d'argument. **
C'est plus simple de traiter ce que partielle fonctions de moi. Assez surpris de ne pas voir une fonctionnelle de la solution de programmation, voici la mienne en ES6:
Je tombe dans cette question, qui était d'obtenir la différence de deux tableaux simples
et je ne vois pas pourquoi ne pas aller à la base pour les boucles :
qui permettrait le retour de la nécessaire
["c", "d"]
[modifier] droit proposé ci-dessus, vu à la fin.
De toute façon, une bonne raison pour éviter cela, la solution la plus simple ?
Fonte à chaîne type d'objet: