Comme tout le monde sait qu'il n'y a pas de fonction intégrée pour supprimer les duplicats d'un tableau en JavaScript. J'ai remarqué que cela manque également de jQuery (qui a une fonction unique uniquement pour les sélections DOM) et que l'extrait le plus commun que j'ai trouvé vérifie l'ensemble de la matrice et un sous-ensemble pour chaque élément (pas très efficace, je pense), comme : donc j'ai fait le mien: Je me demande s'il y a un autre algorithme accepté comme le meilleur de ce cas (ou si Vous voyez une faille évidente qui pourrait être corrigée), ou, que faites-vous quand vous en avez besoin dans JavaScript (je suis conscient que JQuery n'est pas le seul cadre et certains autres peuvent l'avoir déjà couverts). < / p>
5 Réponses :
Je pense que votre version ne fonctionnera pas lorsque vous aurez des objets ou une fonction dans la matrice qui donne une représentation de chaîne comme prototype JS a un " Méthode UNIQ ", vous pouvez obtenir inspiration de celui-ci. [objet d'objet] . Parce que vous ne pouvez avoir que des chaînes comme des clés dans des objets (dans l'objet "hachage" ici). Vous aurez besoin de boucler dans la matrice de résultat pour trouver si la nouvelle entrée existe déjà. Il sera toujours plus rapide que la première méthode.
Bon point, je n'ai pas tenu compte du problème Tostring .
La première méthode ne fonctionne pas avec des objets non plus, si je vous comprends correctement. Iow === ne fonctionne pas sur des objets. Alors supposer que la matrice ne contiendra que des "scalaires" qui peuvent être comparés directement avec == ou === (par exemple, des INT, des flotteurs, des bools, des chaînes) pensez-vous toujours que la seconde ne fonctionnera pas?
er, attends. Je suppose == fonctionne bien sur les références d'objet. nm alors!
Tous les objets comparés seront considérés comme égaux, ce qui est faux avec la première méthode. Mais la deuxième méthode fonctionnera et sera vraiment plus rapide si la matrice ne contient que des valeurs scalaires.
Fabien: Le premier est le premier, c'est mieux dans le cas général, tandis que le second est meilleur dans le cas "scalaire".
J'ai examiné le code de prototype et il est de la même manière que celle des traitements de soulignement, ce qui donne O (n) pour les tableaux triés et O (n ^ 2) pour non traduit.
L'utilisation de l'objet littéral est exactement ce que je ferais. beaucoup de personnes manquent cette technique beaucoup du temps, optant à la place des promenades typiques de tableau comme le code d'origine que vous avez montré. La seule optimisation serait d'éviter la recherche à chaque fois. Autre que cela, o (n) est à peu près aussi bon que vous obtenez pour l'unicité et est bien meilleur que l'exemple d'origine O (N ^ 2). Complexités de temps pour résumer Comme avec la plupart des algorithmes, il y a des échanges. Si vous ne triez que des valeurs scalaires, vos modifications apportées à l'algorithme d'origine donnent la solution la plus optimale. Toutefois, si vous devez trier les valeurs non scalaires, utilisez ou imitant la méthode UNIQ de l'une des bibliothèques décrites serait votre meilleur choix.
Il est préférable d'utiliser hachage.hasownProperty (arr [i]) . L'opérateur dans est vrai pour les propriétés héritées telles que Tostring . ("Tostring" dans {}) => vrai
Bonne prise @chetan. J'ai mis à jour la réponse.
Le unique ne serait-il pas une complexité O (n) pour les listes triés?
Désolé, oui. Copy + Coller a eu le meilleur de moi.
Selon le Cette réponse à Autry Question Utilisation de Résultat [Résultat.Length] = arr [i]; pourrait être meilleur que push ()
C'est parfaitement valide, mais c'est une micro optimisation. Les optimisations que nous examinons ici sont en termes d'ordres de complexité.
Je ne suis pas un expert d'algorithme de quelque manière que ce soit, mais je garde un œil sur le sous-traitant.js. Ils ont ceci comme fonction appelée Uniq:
http://documentcloud.github.com/underscore / # UNIQ P>
J'ai regardé le code dans leur bibliothèque et la copie ici pour référence (pas mon code, ce code appartient à Underscore.js): P>
// Produce a duplicate-free version of the array. If the array has already
// been sorted, you have the option of using a faster algorithm.
_.uniq = function(array, isSorted) {
return _.reduce(array, [], function(memo, el, i) {
if (0 == i || (isSorted === true ? _.last(memo) != el : !_.include(memo, el))) memo.push(el);
return memo;
});
};
Je suis sûr que! _. Inclure également le tableau de zéro.
Je n'avais pas entendu parler de cette bibliothèque auparavant, alors j'ai pris une promenade dans le code à la recherche de manière spécifique à _. Inclure et _. Dernier . On dirait que les matrices triées prendront O (n) et non acheminées seront O (n ^ 2), donc ce n'est pas une amélioration constante.
Justin: bon sommeil. L'échantillon de code OPS (premier) semble supposer que la matrice est triée. Il commence la boucle interne de l'indice actuel + 1.
S'avère, cela est implémenté de la même manière Prototype implémente UNIQ
Malheureusement, les objets JS n'ont aucune identité accessible à partir de la langue - comme les autres affiches mentionnées, à l'aide d'objets comme touches dans un dictionnaire échouera lorsque différents objets ont des objets de chaîne égaux et il n'y a pas de Il y a un moyen d'éviter la vérification O (n ^ 2) All-paires pour Malheureusement, ce qui précède ne fonctionnera que pour des objets modifiables. Il échoue à des valeurs de tableau qui n'autorisent pas le réglage de la propriété (par exemple les entiers, ID () fonctionner dans la langue.
=== Identité si vous pouvez modifier les objets. Choisissez une chaîne aléatoire, parcourez la matrice une fois pour vérifier qu'aucun objet n'a de propriété par ce nom, alors juste faire arr [i] [i] [Randathapertyname] = 1 pour chaque i . Si l'objet suivant de la matrice a déjà cette propriété, il s'agit d'un duplicata.
42 ["aléatoire"] = 1 ne fonctionne pas :()
amusant avec fonctionnel)
Est-ce que ces matrices ne contiennent que des valeurs scalaires ou y a-t-il une chance de contenir des objets et des tableaux?
Et y a-t-il l'hypothèse de tri ou non?