Algoritmo: ¿Cómo eliminar elementos duplicados en una lista de manera eficiente?

Hay una lista l . Contiene elementos de tipo arbitrario cada uno . ¿Cómo eliminar todos los elementos duplicados en dicha lista de manera eficiente? ORDEN debe ser preservado

Solo se requiere un algoritmo, por lo que no se permite importar ninguna biblioteca externa.

Preguntas relacionadas

Suponiendo que el orden importa:

  • Crear un conjunto vacío S y una lista vacía M.
  • Escanee la lista L un elemento a la vez.
  • Si el elemento está en el conjunto S, omítelo.
  • De lo contrario, agrégalo a M y a S.
  • Repita para todos los elementos en L.
  • Volver m.

En Python:

 >>> L = [2, 1, 4, 3, 5, 1, 2, 1, 1, 6, 5] >>> S = set() >>> M = [] >>> for e in L: ... if e in S: ... continue ... S.add(e) ... M.append(e) ... >>> M [2, 1, 4, 3, 5, 6] 

Si el orden no importa:

 M = list(set(L)) 

Caso especial: Hashing e igualdad

En primer lugar, debemos determinar algo acerca de los supuestos, a saber, la existencia de una relación de iguales y de función. ¿Qué quiero decir con esto? Quiero decir que para el conjunto de objetos de origen S, dados dos objetos x1 y x2 que son elementos de S, existe una función (hash) F tal que:

 if (x1.equals(x2)) then F(x1) == F(x2) 

Java tiene tal relación. Eso le permite verificar los duplicados como una operación cercana a O (1) y, por lo tanto, reduce el algoritmo a un problema simple de O (n). Si el orden no es importante, es un simple forro:

 List result = new ArrayList(new HashSet(inputList)); 

Si el orden es importante:

 List outputList = new ArrayList(); Set set = new HashSet(); for (Object item : inputList) { if (!set.contains(item)) { outputList.add(item); set.add(item); } } 

Notarás que dije “cerca de O (1)”. Esto se debe a que dichas estructuras de datos (como Java HashMap o HashSet) se basan en un método en el que una parte del código hash se utiliza para encontrar un elemento (a menudo denominado cubo) en el almacenamiento de respaldo. El número de cubos es un poder de 2. De esa manera, el índice en esa lista es fácil de calcular. hashCode () devuelve un int. Si tiene 16 cubos, puede encontrar cuál usar ANDando el código hash con 15, lo que le da un número del 0 al 15.

Cuando intentas poner algo en ese cubo, puede que ya esté ocupado. Si es así, entonces se producirá una comparación lineal de todas las entradas en ese grupo. Si la tasa de colisión es demasiado alta o si intenta colocar demasiados elementos, la estructura boostá, por lo general se duplicará (pero siempre con una potencia de 2) y todos los elementos se colocarán en sus nuevos depósitos (según el nuevo máscara). Por lo tanto, redimensionar tales estructuras es relativamente caro.

La búsqueda también puede ser costosa. Considera esta clase:

 public class A { private final int a; A(int a) { this.a == a; } public boolean equals(Object ob) { if (ob.getClass() != getClass()) return false; A other = (A)ob; return other.a == a; } public int hashCode() { return 7; } } 

Este código es perfectamente legal y cumple el contrato equals-hashCode.

Suponiendo que su conjunto no contiene más que instancias A, su inserción / búsqueda ahora se convierte en una operación O (n), convirtiendo toda la inserción en O (n 2 ).

Obviamente, este es un ejemplo extremo, pero es útil señalar que dichos mecanismos también se basan en una distribución relativamente buena de hashes dentro del espacio de valores que utiliza el mapa o conjunto.

Finalmente, hay que decir que este es un caso especial . Si está utilizando un idioma sin este tipo de “método abreviado de hash”, entonces es una historia diferente.

Caso general: No ordenar

Si no existe una función de ordenamiento para la lista, está atascado con una comparación de fuerza bruta O (n 2 ) de cada objeto con cada otro objeto. Así que en Java:

 List result = new ArrayList(); for (Object item : inputList) { boolean duplicate = false; for (Object ob : result) { if (ob.equals(item)) { duplicate = true; break; } } if (!duplicate) { result.add(item); } } 

Caso General: Pedidos

Si existe una función de ordenamiento (como ocurre con, digamos, una lista de enteros o cadenas), ordene la lista (que es O (n log n)) y luego compare cada elemento de la lista con el siguiente (O (n )) por lo que el algoritmo total es O (n log n). En Java:

 Collections.sort(inputList); List result = new ArrayList(); Object prev = null; for (Object item : inputList) { if (!item.equals(prev)) { result.add(item); } prev = item; } 

Nota: los ejemplos anteriores suponen que no hay nulos en la lista.

Si el orden no importa, es posible que desee probar este algoritmo escrito en Python:

 >>> array = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6] >>> unique = set(array) >>> list(unique) [1, 2, 3, 4, 5, 6] 

en haskell esto estaría cubierto por las funciones nub y nubBy

 nub :: Eq a => [a] -> [a] nub [] = [] nub (x:xs) = x : nub (filter (/= x) xs) nubBy :: (a -> a -> Bool) -> [a] -> [a] nubBy f [] = [] nubBy f (x:xs) = x : nub (filter (not.fx) xs) 

nubBy relaja la dependencia de la clase de tipos Eq , en lugar de eso, le permite definir su propia función de igualdad para filtrar duplicados.

Estas funciones funcionan sobre una lista de tipos arbitrarios consistentes (por ejemplo, [1,2,"three"] no está permitido en haskell), y ambas son preservación de orden.

Para hacer esto más eficiente, se podría usar Data.Map (o implementar un árbol equilibrado) para reunir los datos en un conjunto (la clave es el elemento, y el valor es el índice en la lista original para poder recuperar el pedido original), luego reunir los resultados en una lista y ordenarlos por índice. Intentaré implementar esto más tarde.


 import qualified Data.Map as Map undup x = go x Map.empty where go [] _ = [] go (x:xs) m case Map.lookup xm of Just _ -> go xs m Nothing -> go xs (Map.insert x True m) 

Esta es una traducción directa de la solución de @FogleBird. Desafortunadamente no funciona sin la importación.


Un bash muy básico de reemplazar la importación de Data.Map sería implementar un árbol, algo como esto

 data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Eq, Show, Read) insert x Empty = Node x Empty Empty insert x (Node a left right) | x < a = Node a (insert x left) right | otherwise = Node a left (insert x right) lookup x Empty = Nothing --returning maybe type to maintain compatibility with Data.Map lookup x (Node a left right) | x == a = Just x | x < a = lookup x left | otherwise = lookup x right 

una mejora sería hacerla autobalancing en la inserción manteniendo un atributo de profundidad (evita que el árbol se degrade en una lista vinculada). Lo bueno de esto sobre una tabla hash es que solo requiere que su tipo esté en la clase de tipos Ord, que es fácilmente derivable para la mayoría de los tipos.


Tomo las solicitudes que parece. En respuesta a la consulta de @Jonno_FTWs aquí hay una solución que elimina completamente los duplicados del resultado. No es totalmente diferente al original, simplemente agrega un estuche adicional. Sin embargo, el rendimiento en tiempo de ejecución será mucho más lento, ya que se repite dos veces cada sub-lista, una para el elemento y la segunda para la recusión. También tenga en cuenta que ahora no funcionará en listas infinitas.

 nub [] = [] nub (x:xs) | elem x xs = nub (filter (/=x) xs) | otherwise = x : nub xs 

Curiosamente, no es necesario filtrar en el segundo caso recursivo porque elem ya ha detectado que no hay duplicados.

En python

 >>> L = [2, 1, 4, 3, 5, 1, 2, 1, 1, 6, 5] >>> a=[] >>> for i in L: ... if not i in a: ... a.append(i) ... >>> print a [2, 1, 4, 3, 5, 6] >>> 

En java, es un trazador de líneas.

 Set set = new LinkedHashSet(list); 

le dará una colección con elementos duplicados eliminados.

Para Java podría ir con esto:

 private static  void removeDuplicates(final List list) { final LinkedHashSet set; set = new LinkedHashSet(list); list.clear(); list.addAll(set); } 

Eliminar duplicados en una lista en lugar de Python

Caso: los elementos en la lista no son hashables o comparables

Es decir, no podemos usar set ( dict ) u sort .

 from itertools import islice def del_dups2(lst): """O(n**2) algorithm, O(1) in memory""" pos = 0 for item in lst: if all(item != e for e in islice(lst, pos)): # we haven't seen `item` yet lst[pos] = item pos += 1 del lst[pos:] 

Caso: los artículos son hashable

La solución se toma de aquí :

 def del_dups(seq): """O(n) algorithm, O(log(n)) in memory (in theory).""" seen = {} pos = 0 for item in seq: if item not in seen: seen[item] = True seq[pos] = item pos += 1 del seq[pos:] 

Caso: los artículos son comparables, pero no hashable

Eso es lo que podemos usar sort . Esta solución no conserva el orden original.

 def del_dups3(lst): """O(n*log(n)) algorithm, O(1) memory""" lst.sort() it = iter(lst) for prev in it: # get the first element break pos = 1 # start from the second element for item in it: if item != prev: # we haven't seen `item` yet lst[pos] = prev = item pos += 1 del lst[pos:] 
  • Ir a través de la lista y asignar índice secuencial a cada elemento
  • ordenar la lista basándose en alguna función de comparación para los elementos
  • eliminar duplicados
  • ordenar la lista basándose en índices asignados

para simplificar, los índices de elementos se pueden almacenar en algo como std :: map

se ve como O (n * log n) si no me he perdido nada

Depende de lo que quiere decir con “eficientemente”. El algoritmo ingenuo es O (n ^ 2), y supongo que lo que realmente quieres decir es que quieres algo de un orden inferior a ese.

Como dice Maxim100, puede preservar el orden al vincular la lista con una serie de números, usar el algoritmo que desee y, a continuación, volver a colocar el rest en su orden original. En Haskell se vería así:

 superNub :: (Ord a) => [a] -> [a] superNub xs = map snd . sortBy (comparing fst) . map head . groupBy ((==) `on` snd) . sortBy (comparing snd) . zip [1..] $ xs 

Por supuesto, necesita importar Data.List (sort), Data.Function (on) y Data.Ord (compare). Simplemente podría recitar las definiciones de esas funciones, pero ¿cuál sería el punto?

He escrito un algoritmo para la cadena. En realidad no importa qué tipo tienes.

 static string removeDuplicates(string str) { if (String.IsNullOrEmpty(str) || str.Length < 2) { return str; } char[] arr = str.ToCharArray(); int len = arr.Length; int pos = 1; for (int i = 1; i < len; ++i) { int j; for (j = 0; j < pos; ++j) { if (arr[i] == arr[j]) { break; } } if (j == pos) { arr[pos] = arr[i]; ++pos; } } string finalStr = String.Empty; foreach (char c in arr.Take(pos)) { finalStr += c.ToString(); } return finalStr; } 

Una solución de línea en Python .
Utilizando listas-comprehesion:

 >>> L = [2, 1, 4, 3, 5, 1, 2, 1, 1, 6, 5] >>> M = [] >>> zip(*[(e,M.append(e)) for e in L if not e in M])[0] (2, 1, 4, 3, 5, 6) 

Tal vez debería considerar el uso de matrices asociadas (también conocido como dict en python) para evitar tener elementos duplicados en primer lugar.

Mi código en Java:

 ArrayList list = new ArrayList(); list.addAll({1,2,1,3,4,5,2,3,4,3}); for (int i=0; i 

o simplemente haga esto:

 SetList unique = new SetList(); unique.addAll(list); 

Ambas formas tienen tiempo = nk ~ O (n ^ 2)

donde n es el tamaño de la lista de entrada,

k es el número de miembros únicos de la lista de entrada

Algoritmo delete_duplicates (a [1 …. n])

// Eliminar duplicados de la matriz dada

// parámetros de entrada: a [1: n], una matriz de n elementos

{

temp[1:n]; // una matriz de n elementos

  temp[i]=a[i];for i=1 to n temp[i].value=a[i] temp[i].key=i 

* // basado en ‘valor’ ordena la matriz temp. *

// basado en ‘valor’ eliminar elementos duplicados de temp.

// basado en ‘clave’ ordena la matriz temp.//construye una matriz p usando temp.

 p[i]=temp[i].value return p 

En otro de los elementos se mantiene en la matriz de salida utilizando la ‘clave’. Considere que la clave es de longitud O (n), el tiempo necesario para realizar la clasificación en la clave y el valor es O (nlogn). Por lo tanto, el tiempo necesario para eliminar todos los duplicados de la matriz es O (nlogn).