Rimuovere i valori duplicati dall'array JS

Ho un array JavaScript molto semplice che può contenere o meno duplicati.

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

Ho bisogno di rimuovere i duplicati e mettere i valori unici in un nuovo array.

Potrei indicare tutti i codici che ho provato ma penso che sia inutile perché non funzionano. Accetto anche soluzioni jQuery.

Domanda simile:

John Slegers
Domanda modificata 1º maggio 2018 в 10:47
Programmazione
arrays javascript unique duplicates
10º febbraio 2012 в 2:53
20 visualizzazioni

TL;DR

Usando il costruttore Set e la sintassi di diffusione:

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

Intelligente" ma naïvia

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

Fondamentalmente, iteriamo sull'array e, per ogni elemento, controlliamo se la prima posizione di questo elemento nell'array è uguale alla posizione corrente. Ovviamente, queste due posizioni sono diverse per gli elementi duplicati. Usando il terzo ("questo array") parametro della callback del filtro possiamo evitare una chiusura della variabile array:

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

Anche se conciso, questo algoritmo non è particolarmente efficiente per array di grandi dimensioni (tempo quadratico). Hashtables in soccorso

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

Questo è il modo in cui viene fatto di solito. L'idea è di mettere ogni elemento in una hashtable e poi controllare la sua presenza istantaneamente. Questo ci dà un tempo lineare, ma ha almeno due svantaggi:

  • poiché le chiavi hash possono essere solo stringhe in JavaScript, questo codice non distingue numeri e "stringhe numeriche". Cioè, uniq([1,"1"]) restituirà solo [1]

  • per la stessa ragione, tutti gli oggetti saranno considerati uguali: uniq([{foo:1},{foo:2}]) restituirà solo [{foo:1}]. Detto questo, se i vostri array contengono solo primitive e non vi importa dei tipi (ad esempio sono sempre numeri), questa soluzione è ottimale. Il meglio di due mondi

    Una soluzione universale combina entrambi gli approcci: usa gli hash lookup per le primitive e la ricerca lineare per gli oggetti.

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

sort | uniq

Un'altra opzione è quella di ordinare prima l'array, e poi rimuovere ogni elemento uguale al precedente:

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

Di nuovo, questo non funziona con gli oggetti (perché tutti gli oggetti sono uguali per sort). Inoltre, cambiamo silenziosamente l'array originale come effetto collaterale - non va bene! Tuttavia, se il vostro input è già ordinato, questa è la strada da seguire (basta rimuovere sort da quanto sopra). Unico da...

A volte si desidera unificare una lista in base a qualche criterio diverso dalla semplice uguaglianza, per esempio, per filtrare gli oggetti che sono diversi, ma condividono qualche proprietà. Questo può essere fatto elegantemente passando un callback. Questo "key" callback viene applicato ad ogni elemento, e gli elementi con "key" uguali vengono rimossi. Poiché ci si aspetta che chiave restituisca una primitiva, la tabella hash funzionerà bene qui:

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

Una chiave() particolarmente utile è JSON.stringify che rimuoverà oggetti che sono fisicamente diversi, ma "sembrano" uguali:

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

Se la chiave non è primitiva, devi ricorrere alla ricerca lineare:

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

In ES6 si può usare 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);
    });
}

o una Mappa:

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

che funzionano entrambe anche con chiavi non primitive. Prima o ultima?

Quando si rimuovono oggetti da una chiave, si potrebbe voler mantenere il primo degli oggetti "uguali" o l'ultimo. Usate la variante Set sopra per mantenere il primo, e la Map per mantenere l'ultimo:

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

Biblioteche

Sia underscore che Lo-Dash forniscono i metodi uniq. I loro algoritmi sono fondamentalmente simili al primo snippet sopra e si riducono a questo:

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

Questo è quadratico, ma ci sono belle chicche aggiuntive, come il wrapping nativo indexOf, la capacità di uniqificare per una chiave (iteratee nel loro linguaggio), e le ottimizzazioni per gli array già ordinati. Se stai usando jQuery e non puoi sopportare nulla senza un dollaro prima, fa così:

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

che è, di nuovo, una variazione del primo snippet. Prestazioni

Le chiamate di funzione sono costose in JavaScript, quindi le soluzioni di cui sopra, per quanto concise, non sono particolarmente efficienti. Per ottenere le massime prestazioni, sostituire il filtro con un ciclo e sbarazzarsi delle altre chiamate di funzione:

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

Questo pezzo di codice brutto fa la stessa cosa dello snippet #3 sopra, ma un ordine di grandezza più veloce (al 2017 è solo due volte più veloce - quelli del nucleo JS stanno facendo un gran lavoro!)

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 fornisce l'oggetto Set, che rende le cose molto più facili:

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

o

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

Si noti che, a differenza di python, i set ES6 sono iterati in ordine di inserimento, quindi questo codice conserva l'ordine dell'array originale. Tuttavia, se avete bisogno di un array con elementi unici, perché non usare gli insiemi fin dall'inizio? Generatori

Una versione "pigra", basata su generatori, di uniq può essere costruita sulla stessa base:

  • prendere il prossimo valore dall'argomento
  • se è già stato visto, saltalo
  • altrimenti, cederlo e aggiungerlo all'insieme dei valori già visti
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
georg
Risposta modificata 9º aprile 2019 в 10:14
Commentari (38)
Soluzione

Veloce e sporco usando 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);
});
Martijn Pieters
Risposta modificata 26º dicembre 2016 в 10:53
Commentari (15)

Vanilla JS: rimuovere i duplicati usando un oggetto come un set

Potete sempre provare a metterlo in un oggetto e poi iterare attraverso le sue chiavi:

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: Rimuovere i duplicati tracciando i valori già visti (order-safe)

Oppure, per una versione order-safe, usare un oggetto per memorizzare tutti i valori visti in precedenza, e controllare i valori rispetto ad esso prima di aggiungerli ad un array.

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: Utilizzare la nuova struttura dati Set (order-safe)

ECMAScript 6 aggiunge la nuova struttura dati Set, che permette di memorizzare valori di qualsiasi tipo. Set.values restituisce elementi in ordine di inserimento.

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

Esempio d'uso:

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"]
Casey Kuball
Risposta modificata 18º ottobre 2016 в 5:11
Commentari (7)