Question Supprimer les valeurs en double du tableau JS [en double]


Cette question a déjà une réponse ici:

J'ai un tableau JavaScript très simple qui peut contenir ou non des doublons.

var names = ["Mike","Matt","Nancy","Adam","Jenny","Nancy","Carl"];

J'ai besoin de supprimer les doublons et de mettre les valeurs uniques dans un nouveau tableau.

Je pourrais citer tous les codes que j'ai essayés mais je pense que c'est inutile parce qu'ils ne fonctionnent pas. J'accepte aussi les solutions jQuery.

Question similaire:


861
2018-02-10 14:53


origine


Réponses:


Rapide et sale en utilisant jQuery:

var names = ["Mike","Matt","Nancy","Adam","Jenny","Nancy","Carl"];
var uniqueNames = [];
$.each(names, function(i, el){
    if($.inArray(el, uniqueNames) === -1) uniqueNames.push(el);
});

362
2018-02-10 15:13



"Intelligent" mais naïf

uniqueArray = a.filter(function(item, pos) {
    return a.indexOf(item) == pos;
})

Fondamentalement, nous parcourons le tableau et, pour chaque élément, vérifions si la première position de cet élément dans le tableau est égale à la position actuelle. Évidemment, ces deux positions sont différentes pour les éléments en double.

En utilisant le paramètre 3rd ("this array") du rappel de filtre, nous pouvons éviter une fermeture de la variable de tableau:

uniqueArray = a.filter(function(item, pos, self) {
    return self.indexOf(item) == pos;
})

Bien que concis, cet algorithme n'est pas particulièrement efficace pour les grands tableaux (temps quadratique).

Hashtables à la rescousse

function uniq(a) {
    var seen = {};
    return a.filter(function(item) {
        return seen.hasOwnProperty(item) ? false : (seen[item] = true);
    });
}

C'est comme ça que ça se passe habituellement. L'idée est de placer chaque élément dans une table de hachage, puis de vérifier sa présence instantanément. Cela nous donne un temps linéaire, mais a au moins deux inconvénients:

  • Puisque les clés de hachage ne peuvent être que des chaînes en Javascript, ce code ne distingue pas les nombres et les "chaînes numériques". C'est, uniq([1,"1"]) reviendra juste [1]
  • Pour la même raison, tous les objets seront considérés égaux: uniq([{foo:1},{foo:2}]) reviendra juste [{foo:1}].

Cela dit, si vos tableaux contiennent uniquement des primitives et que vous ne vous souciez pas des types (par exemple, ce sont toujours des nombres), cette solution est optimale.

Le meilleur des deux mondes

Une solution universelle combine les deux approches: elle utilise des recherches de hachage pour les primitives et une recherche linéaire pour les objets.

function uniq(a) {
    var prims = {"boolean":{}, "number":{}, "string":{}}, objs = [];

    return a.filter(function(item) {
        var type = typeof item;
        if(type in prims)
            return prims[type].hasOwnProperty(item) ? false : (prims[type][item] = true);
        else
            return objs.indexOf(item) >= 0 ? false : objs.push(item);
    });
}

trier | uniq

Une autre option consiste à trier le tableau en premier, puis à supprimer chaque élément égal au précédent:

function uniq(a) {
    return a.sort().filter(function(item, pos, ary) {
        return !pos || item != ary[pos - 1];
    })
}

Encore une fois, cela ne fonctionne pas avec les objets (parce que tous les objets sont égaux pour sort). De plus, nous modifions silencieusement le tableau original en tant qu'effet secondaire - pas bon! Cependant, si votre entrée est déjà triée, c'est le chemin à parcourir (il suffit de retirer sort à partir de ce qui précède).

Unique par ...

Parfois, il est souhaitable d'unifier une liste basée sur certains critères autres que l'égalité, par exemple, pour filtrer les objets qui sont différents, mais partagent une propriété. Cela peut être fait élégamment en passant un rappel. Ce rappel "clé" est appliqué à chaque élément, et les éléments avec des "clés" égales sont supprimés. Depuis key est censé retourner une primitive, la table de hachage fonctionnera bien ici:

function uniqBy(a, key) {
    var seen = {};
    return a.filter(function(item) {
        var k = key(item);
        return seen.hasOwnProperty(k) ? false : (seen[k] = true);
    })
}

Un particulièrement utile key() est JSON.stringify ce qui supprimera les objets physiquement différents, mais "regarde" de la même façon:

a = [[1,2,3], [4,5,6], [1,2,3]]
b = uniqBy(a, JSON.stringify)
console.log(b) // [[1,2,3], [4,5,6]]

Si la key n'est pas primitif, vous devez recourir à la recherche linéaire:

function uniqBy(a, key) {
    var index = [];
    return a.filter(function (item) {
        var k = key(item);
        return index.indexOf(k) >= 0 ? false : index.push(k);
    });
}

ou utilisez le Set objet dans ES6:

function uniqBy(a, key) {
    var seen = new Set();
    return a.filter(item => {
        var k = key(item);
        return seen.has(k) ? false : seen.add(k);
    });
}

(Certaines personnes préfèrent !seen.has(k) && seen.add(k) au lieu de seen.has(k) ? false : seen.add(k)).

Bibliothèques

Tous les deux souligner et Lo-Dash fournir uniq méthodes Leurs algorithmes sont fondamentalement similaires au premier extrait ci-dessus et se résument à ceci:

var result = [];
a.forEach(function(item) {
     if(result.indexOf(item) < 0) {
         result.push(item);
     }
});

C'est quadratique, mais il y a de bonnes choses supplémentaires, comme l'emballage natif indexOf, capacité d'uniqifier par une clé (iteratee dans leur langue), et des optimisations pour les tableaux déjà triés.

Si vous utilisez jQuery et que vous ne supportez rien sans un dollar, cela se passe comme suit:

  $.uniqArray = function(a) {
        return $.grep(a, function(item, pos) {
            return $.inArray(item, a) === pos;
        });
  }

ce qui est, encore une fois, une variation du premier extrait.

Performance

Les appels de fonction sont chers en Javascript, donc les solutions ci-dessus, aussi concises soient-elles, ne sont pas particulièrement efficaces. Pour des performances maximales, remplacez filter avec une boucle et se débarrasser des autres appels de fonction:

function uniq_fast(a) {
    var seen = {};
    var out = [];
    var len = a.length;
    var j = 0;
    for(var i = 0; i < len; i++) {
         var item = a[i];
         if(seen[item] !== 1) {
               seen[item] = 1;
               out[j++] = item;
         }
    }
    return out;
}

Ce morceau de code moche fait la même chose que l'extrait # 3 ci-dessus, mais un ordre de grandeur plus rapide (à partir de 2017, il est seulement deux fois plus rapide - les gens de base de JS font du bon travail!)

function uniq(a) {
    var seen = {};
    return a.filter(function(item) {
        return seen.hasOwnProperty(item) ? false : (seen[item] = true);
    });
}

function uniq_fast(a) {
    var seen = {};
    var out = [];
    var len = a.length;
    var j = 0;
    for(var i = 0; i < len; i++) {
         var item = a[i];
         if(seen[item] !== 1) {
               seen[item] = 1;
               out[j++] = item;
         }
    }
    return out;
}

/////

var r = [0,1,2,3,4,5,6,7,8,9],
    a = [],
    LEN = 1000,
    LOOPS = 1000;

while(LEN--)
    a = a.concat(r);

var d = new Date();
for(var i = 0; i < LOOPS; i++)
    uniq(a);
document.write('<br>uniq, ms/loop: ' + (new Date() - d)/LOOPS)

var d = new Date();
for(var i = 0; i < LOOPS; i++)
    uniq_fast(a);
document.write('<br>uniq_fast, ms/loop: ' + (new Date() - d)/LOOPS)

ES6

ES6 fournit le Ensemble objet, ce qui rend les choses beaucoup plus facile:

function uniq(a) {
   return Array.from(new Set(a));
}

ou

let uniq = a => [...new Set(a)];

Notez que, contrairement à python, les ensembles ES6 sont itérés dans l'ordre d'insertion, donc ce code préserve l'ordre du tableau original.

Cependant, si vous avez besoin d'un tableau avec des éléments uniques, pourquoi ne pas utiliser les ensembles dès le début?

Générateurs

Une version "paresseuse", basée sur un générateur de uniq peut être construit sur la même base:

  • prendre la valeur suivante de l'argument
  • Si cela a déjà été vu, ignorez-le
  • sinon, cédez-le et ajoutez-le à l'ensemble des valeurs déjà vues

function* uniqIter(a) {
    let seen = new Set();

    for (let x of a) {
        if (!seen.has(x)) {
            seen.add(x);
            yield x;
        }
    }
}

// example:

function* randomsBelow(limit) {
    while (1)
        yield Math.floor(Math.random() * limit);
}

// note that randomsBelow is endless

count = 20;
limit = 30;

for (let r of uniqIter(randomsBelow(limit))) {
    console.log(r);
    if (--count === 0)
        break
}

// exercise for the reader: what happens if we set `limit` less than `count` and why


2209
2018-02-10 15:05



Je suis fatigué de voir tous les mauvais exemples avec des boucles ou jQuery. Javascript a les outils parfaits pour cela de nos jours: trier, cartographier et réduire.

Uniq réduit tout en conservant l'ordre existant

var names = ["Mike","Matt","Nancy","Adam","Jenny","Nancy","Carl"];

var uniq = names.reduce(function(a,b){
    if (a.indexOf(b) < 0 ) a.push(b);
    return a;
  },[]);

console.log(uniq, names) // [ 'Mike', 'Matt', 'Nancy', 'Adam', 'Jenny', 'Carl' ]

// one liner
return names.reduce(function(a,b){if(a.indexOf(b)<0)a.push(b);return a;},[]);

Uniq plus rapide avec tri

Il y a probablement des moyens plus rapides mais celui-ci est assez décent.

var uniq = names.slice() // slice makes copy of array before sorting it
  .sort(function(a,b){
    return a > b;
  })
  .reduce(function(a,b){
    if (a.slice(-1)[0] !== b) a.push(b); // slice(-1)[0] means last item in array without removing it (like .pop())
    return a;
  },[]); // this empty array becomes the starting value for a

// one liner
return names.slice().sort(function(a,b){return a > b}).reduce(function(a,b){if (a.slice(-1)[0] !== b) a.push(b);return a;},[]);

Mise à jour 2015: version ES6:

Dans ES6, vous avez Set et Spread, ce qui le rend très facile et performant pour supprimer tous les doublons:

var uniq = [ ...new Set(names) ]; // [ 'Mike', 'Matt', 'Nancy', 'Adam', 'Jenny', 'Carl' ]

Trier en fonction de l'occurrence:

Quelqu'un a demandé comment commander les résultats en fonction du nombre de noms uniques:

var names = ['Mike', 'Matt', 'Nancy', 'Adam', 'Jenny', 'Nancy', 'Carl']

var uniq = names
  .map((name) => {
    return {count: 1, name: name}
  })
  .reduce((a, b) => {
    a[b.name] = (a[b.name] || 0) + b.count
    return a
  }, {})

var sorted = Object.keys(uniq).sort((a, b) => uniq[a] < uniq[b])

console.log(sorted)

266
2018-04-07 22:42



Vanilla JS: supprimer les doublons en utilisant un objet comme un ensemble

Vous pouvez toujours essayer de le placer dans un objet, puis d'itérer à travers ses touches:

function remove_duplicates(arr) {
    var obj = {};
    var ret_arr = [];
    for (var i = 0; i < arr.length; i++) {
        obj[arr[i]] = true;
    }
    for (var key in obj) {
        ret_arr.push(key);
    }
    return ret_arr;
}

Vanilla JS: supprimer les doublons en suivant les valeurs déjà vues (sans risque)

Ou, pour une version sans danger pour la commande, utilisez un objet pour stocker toutes les valeurs précédemment vues, et vérifiez les valeurs par rapport avant de les ajouter à un tableau.

function remove_duplicates_safe(arr) {
    var seen = {};
    var ret_arr = [];
    for (var i = 0; i < arr.length; i++) {
        if (!(arr[i] in seen)) {
            ret_arr.push(arr[i]);
            seen[arr[i]] = true;
        }
    }
    return ret_arr;

}

ECMAScript 6: Utiliser la nouvelle structure de données Set (sans danger pour la commande)

ECMAScript 6 ajoute le nouveau Set Data-Structure, qui vous permet de stocker des valeurs de tout type. Set.values renvoie les éléments dans l'ordre d'insertion.

function remove_duplicates_es6(arr) {
    let s = new Set(arr);
    let it = s.values();
    return Array.from(it);
}

Exemple d'utilisation:

a = ["Mike","Matt","Nancy","Adam","Jenny","Nancy","Carl"];

b = remove_duplicates(a);
// b:
// ["Adam", "Carl", "Jenny", "Matt", "Mike", "Nancy"]

c = remove_duplicates_safe(a);
// c:
// ["Mike", "Matt", "Nancy", "Adam", "Jenny", "Carl"]

d = remove_duplicates_es6(a);
// d:
// ["Mike", "Matt", "Nancy", "Adam", "Jenny", "Carl"]

73
2018-02-10 15:03



Utilisation Underscore.js

C'est une bibliothèque avec une foule de fonctions pour manipuler les tableaux.

C'est le lien pour aller avec le tux de jQuery, et Backbone.js   bretelles.

_.uniq

_.uniq(array, [isSorted], [iterator])  Alias:  unique
  Produit une version sans duplication du tableau, en utilisant === pour tester l'objet   égalité. Si vous savez à l'avance que le tableau est trié, en passant    vrai pour isSorted va exécuter un algorithme beaucoup plus rapide. Si tu veux   calculer des objets uniques basés sur une transformation, passer un itérateur   fonction.

Exemple

var names = ["Mike","Matt","Nancy","Adam","Jenny","Nancy","Carl"];

alert(_.uniq(names, false));

Remarque: Lo-Dash (un souligner concurrent) offre également un comparable .uniq la mise en oeuvre.


68
2018-06-30 03:07



Une seule ligne utilisant les fonctions array filter et indexOf:

arr = arr.filter (function (value, index, array) { 
    return array.indexOf (value) == index;
});

60
2018-02-11 21:18



Vous pouvez simplement le faire en JavaScript, à l'aide du paramètre second-index du filter méthode:

var a = [2,3,4,5,5,4];
a.filter(function(value, index){ return a.indexOf(value) == index });

ou à la main courte

a.filter((v,i) => a.indexOf(v) == i)

46
2018-06-15 11:05



La façon la plus concise de supprimer les doublons d'un tableau en utilisant les fonctions javascript natives est d'utiliser une séquence comme ci-dessous:

vals.sort().reduce(function(a, b){ if (b != a[0]) a.unshift(b); return a }, [])

il n'y a pas besoin de slice ni indexOf dans la fonction de réduction, comme je l'ai vu dans d'autres exemples! il est logique de l'utiliser avec une fonction de filtre si:

vals.filter(function(v, i, a){ return i == a.indexOf(v) })

Encore une autre façon de faire cela ES6 (2015) qui fonctionne déjà sur quelques navigateurs est:

Array.from(new Set(vals))

ou même en utilisant le opérateur de propagation:

[...new Set(vals)]

à votre santé!


28
2017-09-11 23:44



Une ligne:

let names = ['Mike','Matt','Nancy','Adam','Jenny','Nancy','Carl', 'Nancy'];
let dup = [...new Set(names)];
console.log(dup);

28
2017-08-01 01:39