Saltar al contenido

javascript: eliminar valores duplicados de la matriz JS

septiembre 23, 2021
apple touch icon@2

TL; DR

Utilizando el Colocar constructor y el propagación de sintaxis:

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

«Inteligente» pero ingenua

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

Básicamente, iteramos sobre la matriz y, para cada elemento, verificamos si la primera posición de este elemento en la matriz es igual a la posición actual. Obviamente, estas dos posiciones son diferentes para elementos duplicados.

Usando el tercer parámetro («esta matriz») de la devolución de llamada del filtro, podemos evitar un cierre de la variable de la matriz:

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

Aunque conciso, este algoritmo no es particularmente eficiente para arreglos grandes (tiempo cuadrático).

Hashtables al rescate

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

Así es como suele hacerse. La idea es colocar cada elemento en una tabla hash y luego verificar su presencia al instante. Esto nos da un tiempo lineal, pero tiene al menos dos inconvenientes:

  • Dado que las claves hash solo pueden ser cadenas o símbolos en JavaScript, este código no distingue números y «cadenas numéricas». Es decir, uniq([1,"1"]) Regresará solo [1]
  • por la misma razón, todos los objetos se considerarán iguales: uniq([{foo:1},{foo:2}]) Regresará solo [{foo:1}].

Dicho esto, si sus matrices contienen solo primitivas y no le importan los tipos (por ejemplo, siempre son números), esta solución es óptima.

Lo mejor de dos mundos

Una solución universal combina ambos enfoques: utiliza búsquedas hash para primitivas y búsqueda lineal de objetos.

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

ordenar | uniq

Otra opción es ordenar la matriz primero y luego eliminar cada elemento igual al anterior:

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

Nuevamente, esto no funciona con objetos (porque todos los objetos son iguales para sort). Además, cambiamos silenciosamente la matriz original como efecto secundario, ¡no es bueno! Sin embargo, si su entrada ya está ordenada, este es el camino a seguir (simplemente elimine sort de lo anterior).

Único por …

A veces se desea unificar una lista en función de algunos criterios distintos de la igualdad, por ejemplo, para filtrar objetos que son diferentes, pero comparten alguna propiedad. Esto se puede hacer con elegancia pasando una devolución de llamada. Esta devolución de llamada de «clave» se aplica a cada elemento, y se eliminan los elementos con «claves» iguales. Ya que key se espera que devuelva una tabla hash primitiva, funcionará bien aquí:

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

Particularmente útil key() es JSON.stringify que eliminará los objetos que son físicamente diferentes, pero «se ven» iguales:

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 el key no es primitivo, hay que recurrir a la búsqueda lineal:

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 puede utilizar 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 un Map:

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

que ambos también funcionan con claves no primitivas.

¿Primero o último?

Al eliminar objetos con una clave, es posible que desee mantener el primero de los objetos «iguales» o el último.

Utilizar el Set variante anterior para mantener la primera, y la Map para guardar lo último:

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

Bibliotecas

Ambos guion bajo y Lo-Dash proveer uniq métodos. Sus algoritmos son básicamente similares al primer fragmento anterior y se reducen a esto:

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

Esto es cuadrático, pero hay buenos beneficios adicionales, como envolver archivos nativos indexOf, capacidad de unificar mediante una clave (iteratee en su lenguaje) y optimizaciones para matrices ya ordenadas.

Si está usando jQuery y no puede soportar nada sin un dólar antes, es así:

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

que es, nuevamente, una variación del primer fragmento.

Rendimiento

Las llamadas a funciones son caras en JavaScript, por lo que las soluciones anteriores, por concisas que sean, no son particularmente eficientes. Para un rendimiento máximo, reemplace filter con un bucle y deshacerse de otras llamadas a funciones:

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

Este fragmento de código feo hace lo mismo que el fragmento n. ° 3 anterior, pero un orden de magnitud más rápido (a partir de 2017 es solo el doble de rápido: ¡la gente del núcleo de JS está haciendo un gran trabajo!)

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 proporciona Colocar objeto, lo que facilita mucho las cosas:

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

o

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

Tenga en cuenta que, a diferencia de Python, los conjuntos de ES6 se iteran en orden de inserción, por lo que este código conserva el orden de la matriz original.

Sin embargo, si necesita una matriz con elementos únicos, ¿por qué no usar conjuntos desde el principio?

Generadores

Una versión «perezosa» basada en un generador de uniq se puede construir sobre la misma base:

  • tomar el siguiente valor del argumento
  • si ya se ha visto, omítalo
  • de lo contrario, ceda y agréguelo al conjunto de valores ya vistos
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
close