unico() per array in JavaScript

Question

Come tutti sanno non c'è alcuna funzione incorporata per rimuovere i duplicati da un array in JavaScript. Ho notato che manca anche in jQuery (che ha una funzione unica solo per le selezioni DOM), e lo snippet più comune che ho trovato controlla l'intero array e un sottoinsieme di esso per ogni elemento (non molto efficiente, penso), come :

for (var i = 0; i < arr.length; i++) 
    for (var j = i + 1; j < arr.length; j++) 
     if (arr[i] === arr[j]) 
      //whatever 

così ho fatto il mio:

function unique (arr) { 
    var hash = {}, result = []; 
    for (var i = 0; i < arr.length; i++) 
     if (!(arr[i] in hash)) { //it works with objects! in FF, at least 
      hash[arr[i]] = true; 
      result.push(arr[i]); 
     } 
    return result; 
} 

mi chiedo se c'è qualche altro algoritmo accettato come il migliore per questo caso (o se si vede alcun difetto evidente che poteva essere risolto), o , cosa fai quando hai bisogno di questo in javascript (sono consapevole che jQuery non è l'unico framework e alcuni altri potrebbero averlo già trattato).

Answer 1

Utilizzando l'oggetto letterale è esattamente quello che vorrei fare. Un sacco di persone perdere questa tecnica un sacco del tempo, optando invece per allineamento tipico cammina come il codice originale che avete dimostrato. L'unica ottimizzazione sarebbe evitare la ricerca arr.length ogni volta. Oltre a questo, O (n) è tanto buono quanto si ottiene per l'unicità ed è molto meglio dell'esempio originale di O (n^2).

function unique(arr) { 
    var hash = {}, result = []; 
    for (var i = 0, l = arr.length; i < l; ++i) { 
     if (!hash.hasOwnProperty(arr[i])) { //it works with objects! in FF, at least 
      hash[ arr[i] ] = true; 
      result.push(arr[i]); 
     } 
    } 
    return result; 
} 

// * Edited to use hasOwnProperty per comments 

complessità di tempo per riassumere

f() | unsorted | sorted | objects | scalar | library 
____________________________________________________________ 
unique | O(n) | O(n) | no | yes | n/a 
original | O(n^2) | O(n^2) | yes | yes | n/a 
uniq  | O(n^2) | O(n) | yes | yes | Prototype 
_.uniq | O(n^2) | O(n) | yes | yes | Underscore 

Come con la maggior parte degli algoritmi, ci sono compromessi. Se si stanno solo ordinando valori scalari, le modifiche all'algoritmo originale forniscono la soluzione ottimale. Tuttavia, se è necessario ordinare i valori non scalari, utilizzare o imitare il metodo uniq di una delle librerie descritte sarà la scelta migliore.

Answer 2

penso che la versione non funziona quando si dovrà oggetti o funzione nella matrice che danno stringa di rappresentazione come [Object object]. Perché puoi avere solo stringhe come chiavi negli oggetti (nell'oggetto "hash" qui). Avrai bisogno di collegarti alla matrice dei risultati per scoprire se la nuova voce esiste già. Sarà ancora più veloce del primo metodo.

Il prototipo JS ha un metodo "uniq", potresti trarre ispirazione da esso.

Answer 3

io non sono un esperto di algoritmi con qualsiasi mezzo, ma ho tenuto d'occhio underscore.js. Hanno questo come una funzione chiamata uniq:

http://documentcloud.github.com/underscore/#uniq

ho guardato il codice nella loro biblioteca, e copiati qui per riferimento (non il mio codice, il codice appartiene a underscore.js):

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

EDIT: Hai bisogno di camminare per il resto del codice underscore.js, e ho quasi preso questo codice fuori a causa di esso. Ho lasciato lo snippet di codice nel caso in cui fosse ancora utile.

Answer 4

Sfortunatamente gli oggetti JS non hanno identità accessibile dalla lingua - come altri locatori hanno menzionato, l'uso di oggetti come chiavi in ​​un dizionario fallisce quando oggetti diversi hanno rappresentazioni di stringa uguali e non c'è la funzione id() nella lingua.

Esiste un modo per evitare il controllo di tutte le coppie O (n^2) per l'identità === se è possibile modificare gli oggetti.Scegli una stringa casuale, cammina l'array una volta per verificare che nessun oggetto abbia una proprietà con quel nome, quindi fai semplicemente arr[i][randomPropertyName]=1 per ogni i. Se il prossimo oggetto dell'array ha già quella proprietà, allora è un duplicato.

Sfortunatamente, quanto sopra funzionerà solo per oggetti modificabili. Non riesce a valori di matrice che non consentono l'impostazione di proprietà (ad esempio, numeri interi, 42['random']=1 semplicemente non funziona :()

Answer 5

divertimento con il divertimento (finzionale)

function uniqueNum(arr) { 
    return Object.keys(arr.reduce(
     function(o, x) {o[x]=1; return o;}, {})).map(Number); 
}