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