unique() para matrices en javascript

Question

Como todos saben, no hay una función incorporada para eliminar los duplicados de una matriz en javascript. Me he dado cuenta de que esto también falta en jQuery (que tiene una función única para selecciones DOM solamente), y el fragmento más común que encontré comprueba toda la matriz y un subconjunto de ella para cada elemento (no muy eficiente, creo), como :

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

así que hice mi propia:

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

me pregunto si hay algún otro algoritmo aceptado como el mejor para este caso (o si observa cualquier defecto obvio que podría ser fijo), o , ¿qué haces cuando necesitas esto en javascript (soy consciente de que jQuery no es el único marco y algunos otros pueden tener esto ya cubierto).

Answer 1

Usar el objeto literal es exactamente lo que haría. Un lote de gente extraña esta técnica mucho del tiempo, optando en su lugar por paseos típicos de matriz como el código original que mostró. La única optimización sería evitar la búsqueda arr.length cada vez. Aparte de eso, O (n) es tan bueno como se obtiene para la singularidad y es mucho mejor que el ejemplo original de 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 

complejidades de tiempo para resumir

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 

Al igual que con la mayoría de los algoritmos, hay compensaciones. Si solo está ordenando valores escalares, sus modificaciones al algoritmo original le dan la solución más óptima. Sin embargo, si necesita ordenar valores no escalares, entonces usar o imitar el método uniq de cualquiera de las bibliotecas analizadas sería su mejor opción.

Answer 2

Creo que su versión no funcionará cuando tenga objetos o funciones en la matriz que den una representación de cadenas como [Object object]. Porque solo puedes tener cadenas como claves en objetos (en el objeto "hash" aquí). Tendrá que entrar en la matriz de resultados para encontrar si la nueva entrada ya existe. Todavía será más rápido que el primer método.

Prototype JS tiene un método "uniq", puede obtener inspiración de él.

Answer 3

No soy un experto en algoritmos de ninguna manera, pero he estado vigilando underscore.js. Ellos tienen esto como una función llamada uniq:

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

Miré el código en su biblioteca, y se copian aquí para referencia (no es mi código, el código pertenece 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; 
    }); 
}; 

EDITAR: Necesita recorrer el resto del código underscore.js, y casi saqué este código por ello. Dejé el fragmento de código por si acaso esto todavía era útil.

Answer 4

Desafortunadamente, los objetos JS no tienen identidad accesible desde el idioma, como otros carteles han mencionado, usar objetos como claves en un diccionario fallará cuando diferentes objetos tengan representaciones de cadenas iguales y no haya id() función en el idioma.

Hay una forma de evitar la verificación de todos los pares O (n^2) para la identidad === si puede modificar los objetos.Elija una cadena aleatoria, recorra la matriz una vez para verificar que ningún objeto tenga una propiedad con ese nombre, luego simplemente haga arr[i][randomPropertyName]=1 para cada i. Si el siguiente objeto en la matriz ya tiene esa propiedad, entonces es un duplicado.

Lamentablemente, lo anterior solo funcionará para objetos modificables. Se produce un error de valores de la matriz que no permiten la configuración de la propiedad (por ejemplo, números enteros, 42['random']=1 simplemente no funciona :()

Answer 5

diversión con diversión (ficticia)

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