Suppression des valeurs en double dans un tableau JS

TL;DR

Utilisation du constructeur [Set][1] et de la [syntaxe de propagation][2] :

uniq = [...new Set(array)];

"Intelligent" mais naïf

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

En gros, on itère sur le tableau et, pour chaque élément, on vérifie si la première position de cet élément dans le tableau est égale à la position courante. Évidemment, ces deux positions sont différentes pour les éléments dupliqués.

En utilisant le 3ème paramètre ("ce tableau") de la callback du filtre, nous pouvons éviter une fermeture de la variable 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).

Les tables de hachage à la rescousse

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

C'est ainsi que l'on procède généralement. 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 présente au moins deux inconvénients :

• puisque les clés de hachage ne peuvent être que des chaînes de caractères en JavaScript, ce code ne distingue pas les nombres et les "chaînes numériques". En d'autres termes, uniq([1, "1"]) ne retournera que [1].
• pour la même raison, tous les objets seront considérés comme égaux : uniq([{foo:1},{foo:2}]) retournera juste [{foo:1}].

Cela dit, si vos tableaux ne contiennent que des primitives et que vous ne vous souciez pas des types (par exemple, il s'agit toujours de nombres), cette solution est optimale.

Le meilleur de 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 (car tous les objets sont égaux pour sort). De plus, nous modifions silencieusement le tableau original en tant qu'effet secondaire - ce n'est pas bon ! Cependant, si votre entrée est déjà triée, c'est la solution (enlevez simplement sort de l'exemple ci-dessus).

Unique par...

Parfois, il est souhaitable d'unifier une liste en se basant sur des critères autres que l'égalité, par exemple, pour filtrer les objets qui sont différents, mais qui partagent une propriété. Cela peut être fait de manière élégante en passant un callback. Ce callback "key" est appliqué à chaque élément, et les éléments avec des "keys" égaux sont supprimés. Puisque 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);
    })
}

Une key() particulièrement utile est JSON.stringify qui supprimera les objets qui sont physiquement différents, mais qui ont la même apparence :

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

En ES6, vous pouvez utiliser un Set :

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

ou un Map :

function uniqBy(a, key) {
    return [
        ...new Map(
            a.map(x => [key(x), x])
        ).values()
    ]
}

qui fonctionnent également avec des clés non primitives.

Première ou dernière ?

Lorsque vous supprimez des objets par une clé, vous pouvez vouloir garder le premier des objets "égaux" ou le dernier.

Utilisez la variante Set ci-dessus pour garder le premier, et la variante Map pour garder le dernier :

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

function uniqByKeepLast(a, key) {
    return [
        ...new Map(
            a.map(x => [key(x), x])
        ).values()
    ]
}

//

data = [
    {a:1, u:1},
    {a:2, u:2},
    {a:3, u:3},
    {a:4, u:1},
    {a:5, u:2},
    {a:6, u:3},
];

console.log(uniqByKeepFirst(data, it => it.u))
console.log(uniqByKeepLast(data, it => it.u))

Bibliothèques

underscore et Lo-Dash fournissent toutes deux des méthodes uniq. 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 belles choses en plus, comme l'intégration du indexOf natif, la possibilité d'uniqifier par une clé (iteratee dans leur jargon), et des optimisations pour les tableaux déjà triés.

Si vous utilisez jQuery et que vous ne supportez rien qui ne soit précédé d'un dollar, voici comment ça se passe :

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

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

Performance

Les appels de fonction sont coûteux en JavaScript, donc les solutions ci-dessus, aussi concises soient-elles, ne sont pas particulièrement efficaces. Pour des performances maximales, remplacez filter par une boucle et supprimez les 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 laid fait la même chose que le snippet #3 ci-dessus, mais un ordre de grandeur plus rapide (en 2017, il n'est que deux fois plus rapide - les gens du noyau JS font un excellent 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 l'objet Set, qui rend les choses beaucoup plus faciles :

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 sets dès le début ?

Générateurs

Une version "paresseuse", basée sur des générateurs, de uniq peut être construite sur la même base :

• prendre la prochaine valeur de l'argument
• si elle a déjà été vue, on la saute
• sinon, la céder et l'ajouter à 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

[1] : https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set [2] : https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Spread_syntax

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

Vanilla JS : Suppression des doublons en utilisant un objet comme un ensemble.

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

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 : Suppression des doublons par le suivi des valeurs déjà vues (order-safe)

Ou, pour une version plus sûre, utilisez un objet pour stocker toutes les valeurs déjà vues, et vérifiez les valeurs par rapport à cet objet 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 : utilisation de la nouvelle structure de données Set (order-safe).

ECMAScript 6 ajoute la nouvelle structure de données Set, qui vous permet de stocker des valeurs de n'importe quel 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"]