Blog ElCodiguero
30 Jan 2011 Python

Eliminar objetos repetidos de una lista

En Python las listas y tuplas permiten elementos duplicados. Cuando se quiere manejar elementos únicos, se recurre normalmente a conjuntos (set), o a diccionarios (donde lo que debe ser único es cada clave, no hay restricciones en el contenido).

Pero si se recibe una lista con duplicados y queremos eliminarlos, ¿cuál es la forma más sencilla?

Con un bucle for

Si no se conoce de antemano un método, uno podría pensar en resolver el problema recorriendo la lista, y construyendo una segunda lista solamente con los elementos que no pertenezcan ya a ella, algo así:

1 lista_nueva = []
2 for i in lista_original:
3     if i not in lista_nueva:
4         lista_nueva.append(i)

Si bien esta solución es simple, vale notar que es O(n^2) peor caso (cuando no hay duplicados), ya que por cada elemento de la lista original se debe recorrer potencialmente toda la lista nueva. Como ventaja se puede mencionar que preserva el orden de la lista original.

Pero vamos, ¡esto es Python! ¡Debe haber un método mejor! :-)

Con un diccionario

Aprovechando que los diccionarios no pueden contener claves duplicadas, se puede crear un diccionario tal que cada una de sus claves es un elemento de la lista. Luego, con el método keys se obtiene una lista de las claves.

dict.fromkeys(lista_original).keys()

Este método es O(n), pero tiene la desventaja de que no preserva el orden de los elementos de la lista original.

Usando conjuntos

Este método es muy similar al anterior, de hecho tiene la misma ventaja (es O(n)) y la misma desventaja (no preserva el orden de la lista original). Se trata de crear un conjunto a partir de la lista, y luego (en caso de requerirlo) volver a convertir el conjunto a una lista. Los conjuntos no pueden contener elementos repetidos, por lo que se eliminan los duplicados.

list(set(lista_original))

Usando comprensión de listas

Este es un ejemplo útil y eficiente aunque complejo, que encontré en bytes.com. La idea es utilizar las propiedades de los diccionarios para eliminar los elementos duplicados.

[ d.setdefault(x,x) for x in lista_original if x not in d ]

Para cada elemento de la lista original, si el elemento no es una clave del diccionario (x not in d) se agrega al diccionario via setdefault. Este método tiene la particularidad de que si la clave no existe, la agrega (por lo que no se la volverá a agregar gracias al x not in d) y devuelve el valor que se le pasó como segundo parámetro, generando efectivamente una lista de elementos únicos y preservando el orden original.

Como los diccionarios (también los conjuntos) son O(1) caso promedio para la búsqueda de elementos (por estar implementados como tablas hash), el costo de este método es O(n), por el recorrido de los elementos de la lista.

En general preferiría usar conjuntos, ya que es la forma más sencilla. Pero si hay que preservar el orden de la lista original, sin duda este es un buen método, y no es tan complejo como parece a primera vista.

Enlaces relacionados

Activa Javascript para para cargar los comentarios, basados en DISQUS

El Blog de ElCodiguero funciona sobre Pelican

Inicio | Blog | Acerca de