una - repetidos python

¿Cómo se eliminan los duplicados de una lista y se conserva el orden? (30)

¿Hay algún componente incorporado que elimine los duplicados de la lista en Python, al mismo tiempo que conserva el orden? Sé que puedo usar un conjunto para eliminar duplicados, pero eso destruye el pedido original. También sé que puedo rodar mi propio como esto:

def uniq(input): output = [] for x in input: if x not in output: output.append(x) return output

(Gracias a unwind para esa muestra del código .)

Pero me gustaría aprovecharme de un lenguaje incorporado o de un lenguaje más pitónico si es posible.

Pregunta relacionada: En Python, ¿cuál es el algoritmo más rápido para eliminar duplicados de una lista, de modo que todos los elementos sean únicos y preserven el orden ?

Un método en el lugar

Este método es cuadrático, porque tenemos una búsqueda lineal en la lista para cada elemento de la lista (a eso tenemos que agregar el costo de reorganizar la lista debido a las características).

Dicho esto, es posible operar en su lugar si comenzamos desde el final de la lista y procedemos hacia el origen eliminando cada término que está presente en la sub-lista a su izquierda

Esta idea en código es simplemente

for i in range(len(l)-1,0,-1): if l[i] in l[:i]: del l[i]

Una simple prueba de la implementación.

In [91]: from random import randint, seed In [92]: seed(''20080808'') ; l = [randint(1,6) for _ in range(12)] # Beijing Olympics In [93]: for i in range(len(l)-1,0,-1): ...: print(l) ...: print(i, l[i], l[:i], end='''') ...: if l[i] in l[:i]: ...: print( '': remove'', l[i]) ...: del l[i] ...: else: ...: print() ...: print(l) [6, 5, 1, 4, 6, 1, 6, 2, 2, 4, 5, 2] 11 2 [6, 5, 1, 4, 6, 1, 6, 2, 2, 4, 5]: remove 2 [6, 5, 1, 4, 6, 1, 6, 2, 2, 4, 5] 10 5 [6, 5, 1, 4, 6, 1, 6, 2, 2, 4]: remove 5 [6, 5, 1, 4, 6, 1, 6, 2, 2, 4] 9 4 [6, 5, 1, 4, 6, 1, 6, 2, 2]: remove 4 [6, 5, 1, 4, 6, 1, 6, 2, 2] 8 2 [6, 5, 1, 4, 6, 1, 6, 2]: remove 2 [6, 5, 1, 4, 6, 1, 6, 2] 7 2 [6, 5, 1, 4, 6, 1, 6] [6, 5, 1, 4, 6, 1, 6, 2] 6 6 [6, 5, 1, 4, 6, 1]: remove 6 [6, 5, 1, 4, 6, 1, 2] 5 1 [6, 5, 1, 4, 6]: remove 1 [6, 5, 1, 4, 6, 2] 4 6 [6, 5, 1, 4]: remove 6 [6, 5, 1, 4, 2] 3 4 [6, 5, 1] [6, 5, 1, 4, 2] 2 1 [6, 5] [6, 5, 1, 4, 2] 1 5 [6] [6, 5, 1, 4, 2] In [94]:

5 veces más rápido reducir variante pero más sofisticado

>>> l = [5, 6, 6, 1, 1, 2, 2, 3, 4] >>> reduce(lambda r, v: v in r[1] and r or (r[0].append(v) or r[1].add(v)) or r, l, ([], set()))[0] [5, 6, 1, 2, 3, 4]

Explicación:

default = (list(), set()) # use list to keep order # use set to make lookup faster def reducer(result, item): if item not in result[1]: result[0].append(item) result[1].add(item) return result >>> reduce(reducer, l, default)[0] [5, 6, 1, 2, 3, 4]

Aquí están mis 2 centavos en esto:

def unique(nums): unique = [] for n in nums: if n not in unique: unique.append(n) return unique

Saludos, Yuriy

Aquí tiene algunas alternativas: http://www.peterbe.com/plog/uniqifiers-benchmark

El más rápido:

def f7(seq): seen = set() seen_add = seen.add return [x for x in seq if not (x in seen or seen_add(x))]

¿Por qué asignar seen.add a seen_add lugar de solo llamar a seen.add ? Python es un lenguaje dinámico, y resolver seen.add cada iteración es más costoso que resolver una variable local. seen.add podría haber cambiado entre iteraciones, y el tiempo de ejecución no es lo suficientemente inteligente como para descartarlo. Para jugar con seguridad, tiene que revisar el objeto cada vez.

Si planea usar mucho esta función en el mismo conjunto de datos, tal vez estaría mejor con un conjunto ordenado: http://code.activestate.com/recipes/528878/

O (1) inserción, eliminación y verificación de miembros por operación.

Creo que si quieres mantener el orden,

puedes probar esto

list1 = [''b'',''c'',''d'',''b'',''c'',''a'',''a''] list2 = list(set(list1)) list2.sort(key=list1.index) print list2

O similarmente puedes hacer esto:

list1 = [''b'',''c'',''d'',''b'',''c'',''a'',''a''] list2 = sorted(set(list1),key=list1.index) print list2

También puedes hacer esto:

list1 = [''b'',''c'',''d'',''b'',''c'',''a'',''a''] list2 = [] for i in list1: if not i in list2: list2.append(i)` print list2

También se puede escribir así:

list1 = [''b'',''c'',''d'',''b'',''c'',''a'',''a''] list2 = [] [list2.append(i) for i in list1 if not i in list2] print list2

Debido a que estaba buscando un dup y recopilé información relacionada, pero diferente, relacionada y útil que no forma parte de las otras respuestas, aquí hay otras dos soluciones posibles.

.get (True) XOR .setdefault (False)

La primera es muy parecida a la aceptada función de seen_add pero con efectos secundarios explícitos utilizando get(x,<default>) y setdefault(x,<default>) del diccionario:

# Explanation of d.get(x,True) != d.setdefault(x,False) # # x in d | d[x] | A = d.get(x,True) | x in d | B = d.setdefault(x,False) | x in d | d[x] | A xor B # False | None | True (1) | False | False (2) | True | False | True # True | False | False (3) | True | False (4) | True | False | False # # Notes # (1) x is not in the dictionary, so get(x,<default>) returns True but does __not__ add the value to the dictionary # (2) x is not in the dictionary, so setdefault(x,<default>) adds the {x:False} and returns False # (3) since x is in the dictionary, the <default> argument is ignored, and the value of the key is returned, which was # set to False in (2) # (4) since the key is already in the dictionary, its value is returned directly and the argument is ignored # # A != B is how to do boolean XOR in Python # def sort_with_order(s): d = dict() return [x for x in s if d.get(x,True) != d.setdefault(x,False)]

get(x,<default>) devuelve <default> si x no está en el diccionario, pero no agrega la clave al diccionario. set(x,<default>) devuelve el valor si la clave está en el diccionario, de lo contrario, lo establece y devuelve <default> .

Aparte: a != b es cómo hacer un XOR en python

__RESCRIBIR ___ desaparecer_____ (inspirado en esta respuesta )

La segunda técnica es anular el método __missing__ que se llama cuando la clave no existe en un diccionario, al que solo se llama cuando se usa la notación d[k] :

class Tracker(dict): # returns True if missing, otherwise sets the value to False # so next time d[key] is called, the value False will be returned # and __missing__ will not be called again def __missing__(self, key): self[key] = False return True t = Tracker() unique_with_order = [x for x in samples if t[x]]

De la documentación :

Nuevo en la versión 2.5: Si una subclase de dict define un método _____ falta _____ (), si la clave no está presente, la operación d [key] llama a ese método con la clave como argumento. La operación d [tecla] luego devuelve o levanta lo que sea devuelto o generado por la llamada _____ faltante _____ (tecla) si la tecla no está presente. Ninguna otra operación o método invoca a _____ falta _____ (). Si _____ falta _____ () no está definido, se genera KeyError. _____ falta _____ () debe ser un método; no puede ser una variable de instancia. Para un ejemplo, vea colecciones.defaultdict.

En Python 3.7 y superior, se guaranteed que los diccionarios recordarán su orden de inserción de claves. La respuesta a this pregunta resume el estado actual de las cosas.

La solución OrderedDict se vuelve obsoleta y, sin ninguna declaración de importación, simplemente podemos emitir:

>>> list(dict.fromkeys([1, 2, 1, 3, 3, 2, 4]).keys()) [1, 2, 3, 4]

Enfoque relativamente efectivo con _sorted_ a arrays numpy :

b = np.array([1,3,3, 8, 12, 12,12]) numpy.hstack([b[0], [x[0] for x in zip(b[1:], b[:-1]) if x[0]!=x[1]]])

Salidas:

array([ 1, 3, 8, 12])

Esta es la forma inteligente de eliminar duplicados de una lista en Python mientras se conserva su orden, incluso puede hacerlo en una línea de código:

a_list = ["a", "b", "a", "c"] sorted_list = [x[0] for x in (sorted({x:a_list.index(x) for x in set(a_list)}.items(), key=lambda x: x[1]))] print sorted_list

La respuesta de MizardX ofrece una buena colección de enfoques múltiples.

Esto es lo que se me ocurrió mientras pensaba en voz alta:

mylist = [x for i,x in enumerate(mylist) if x not in mylist[i+1:]]

Manera rápida y sucia: list(set([1,2,2,1,3,4,5,5]))

Mi amigo Wes me dio esta dulce respuesta usando listas de comprensión.

Código de ejemplo:

>>> l = [3, 4, 3, 6, 4, 1, 4, 8] >>> l = [l[i] for i in range(len(l)) if i == l.index(l[i])] >>> l = [3, 4, 6, 1, 8]

No es para patear a un caballo muerto (esta pregunta es muy antigua y ya tiene muchas respuestas buenas), pero aquí hay una solución que usa pandas que es bastante rápida en muchas circunstancias y es muy fácil de usar.

import pandas as pd my_list = my_list = [0, 1, 2, 3, 4, 1, 2, 3, 5] >>> pd.Series(my_list).drop_duplicates().tolist() # Output: # [0, 1, 2, 3, 4, 5]

Para los tipos sin hashable (por ejemplo, lista de listas), basados en MizardX:

def f7_noHash(seq) seen = set() return [ x for x in seq if str( x ) not in seen and not seen.add( str( x ) )]

Podrías hacer una especie de hackeo de comprensión de lista fea.

[l[i] for i in range(len(l)) if l.index(l[i]) == i]

Por otra respuesta muy tardía a otra pregunta muy antigua:

Las recetas de itertools tienen una función que hace esto, utilizando la técnica del conjunto seen , pero:

Maneja una función de key estándar.
No utiliza hacks impropios.
Optimiza el bucle pre- seen.add lugar de buscarlo N veces. ( f7 también hace esto, pero algunas versiones no).
Optimiza el bucle utilizando ifilterfalse , de modo que solo tienes que recorrer los elementos únicos de Python, en lugar de todos ellos. (Aún ifilterfalse , ifilterfalse sobre todos ellos dentro de ifilterfalse , por supuesto, pero eso está en C, y mucho más rápido).

¿Es realmente más rápido que f7 ? Depende de sus datos, por lo que tendrá que probarlo y ver. Si quieres una lista al final, f7 usa una lista comp, y no hay manera de hacerlo aquí. (Puede append directamente en lugar de yield , o puede list el generador en la función de list , pero ninguno puede ser tan rápido como LIST_APPEND dentro de una lista comp.) En cualquier caso, por lo general, no es suficiente con extraer algunos microsegundos. ser tan importante como tener una función ya comprensible, reutilizable y ya escrita que no requiere DSU cuando se desea decorar.

Al igual que con todas las recetas, también está disponible en more-iterools .

Si solo desea el caso sin key , puede simplificarlo como:

def unique(iterable): seen = set() seen_add = seen.add for element in itertools.ifilterfalse(seen.__contains__, iterable): seen_add(element) yield element

Puede hacer referencia a una lista de comprensión, ya que se está construyendo con el símbolo ''_ [1]''.
Por ejemplo, la siguiente función unique-ifies es una lista de elementos sin cambiar su orden haciendo referencia a su comprensión de la lista.

def unique(my_list): return [x for x in my_list if x not in locals()[''_[1]'']]

Manifestación:

l1 = [1, 2, 3, 4, 1, 2, 3, 4, 5] l2 = [x for x in l1 if x not in locals()[''_[1]'']] print l2

Salida:

[1, 2, 3, 4, 5]

Si habitualmente usa pandas , y se prefiere la estética al rendimiento, considere la función pandas.Series.drop_duplicates :

import pandas as pd import numpy as np uniquifier = lambda alist: pd.Series(alist).drop_duplicates().tolist() # from the chosen answer def f7(seq): seen = set() seen_add = seen.add return [ x for x in seq if not (x in seen or seen_add(x))] alist = np.random.randint(low=0, high=1000, size=10000).tolist() print uniquifier(alist) == f7(alist) # True

Sincronización:

In [104]: %timeit f7(alist) 1000 loops, best of 3: 1.3 ms per loop In [110]: %timeit uniquifier(alist) 100 loops, best of 3: 4.39 ms per loop

Si necesita un trazador de líneas entonces tal vez esto ayude:

reduce(lambda x, y: x + y if y[0] not in x else x, map(lambda x: [x],lst))

... debería funcionar pero corrígeme si me equivoco

Solo para agregar otra implementación (muy eficaz) de tal funcionalidad desde un módulo externo ¹ : iteration_utilities.unique_everseen :

>>> from iteration_utilities import unique_everseen >>> lst = [1,1,1,2,3,2,2,2,1,3,4] >>> list(unique_everseen(lst)) [1, 2, 3, 4]

Tiempos

Hice algunos tiempos (Python 3.6) y estos muestran que es más rápido que todas las otras alternativas que probé, incluyendo OrderedDict.fromkeys , f7 y more_itertools.unique_everseen :

%matplotlib notebook from iteration_utilities import unique_everseen from collections import OrderedDict from more_itertools import unique_everseen as mi_unique_everseen def f7(seq): seen = set() seen_add = seen.add return [x for x in seq if not (x in seen or seen_add(x))] def iteration_utilities_unique_everseen(seq): return list(unique_everseen(seq)) def more_itertools_unique_everseen(seq): return list(mi_unique_everseen(seq)) def odict(seq): return list(OrderedDict.fromkeys(seq)) from simple_benchmark import benchmark b = benchmark([f7, iteration_utilities_unique_everseen, more_itertools_unique_everseen, odict], {2**i: list(range(2**i)) for i in range(1, 20)}, ''list size (no duplicates)'') b.plot()

Y solo para asegurarme de que también hice una prueba con más duplicados para comprobar si hay alguna diferencia:

import random b = benchmark([f7, iteration_utilities_unique_everseen, more_itertools_unique_everseen, odict], {2**i: [random.randint(0, 2**(i-1)) for _ in range(2**i)] for i in range(1, 20)}, ''list size (lots of duplicates)'') b.plot()

Y uno que contiene un solo valor:

b = benchmark([f7, iteration_utilities_unique_everseen, more_itertools_unique_everseen, odict], {2**i: [1]*(2**i) for i in range(1, 20)}, ''list size (only duplicates)'') b.plot()

En todos estos casos, la función iteration_utilities.unique_everseen es la más rápida (en mi computadora).

Esta función iteration_utilities.unique_everseen también puede manejar valores inestables en la entrada (sin embargo, con un rendimiento O(n*n) lugar del rendimiento O(n) cuando los valores son hashable).

>>> lst = [{1}, {1}, {2}, {1}, {3}] >>> list(unique_everseen(lst)) [{1}, {2}, {3}]

¹ Descargo ^de responsabilidad: Soy el autor de ese paquete.

Solo para agregar otra respuesta que no he visto en la lista

>>> a = [''f'', ''F'', ''F'', ''G'', ''a'', ''b'', ''b'', ''c'', ''d'', ''d'', ''d'', ''f''] >>> [a[i] for i in sorted(set([a.index(elem) for elem in a]))] [''f'', ''F'', ''G'', ''a'', ''b'', ''c'', ''d''] >>>

Esto está usando .index para obtener el primer índice de cada elemento de la lista y deshacerse de los resultados duplicados (para elementos repetidos) con el set , y luego ordenarlos porque no hay orden en los conjuntos. Tenga en cuenta que no perdemos información de orden porque el primer índice de cada elemento nuevo siempre está en orden ascendente. Así ordenado siempre lo arreglará.

Acabo de considerar la sintaxis fácil, no el rendimiento.

Tomando prestada la idea recursiva utilizada en la definición de la función nub de Haskell para las listas, este sería un enfoque recursivo:

def unique(lst): return [] if lst==[] else [lst[0]] + unique(filter(lambda x: x!= lst[0], lst[1:]))

p.ej:

In [118]: unique([1,5,1,1,4,3,4]) Out[118]: [1, 5, 4, 3]

Lo probé para aumentar el tamaño de los datos y vi una complejidad de tiempo sublineal (no es definitivo, pero sugiere que esto debería estar bien para datos normales).

In [122]: %timeit unique(np.random.randint(5, size=(1))) 10000 loops, best of 3: 25.3 us per loop In [123]: %timeit unique(np.random.randint(5, size=(10))) 10000 loops, best of 3: 42.9 us per loop In [124]: %timeit unique(np.random.randint(5, size=(100))) 10000 loops, best of 3: 132 us per loop In [125]: %timeit unique(np.random.randint(5, size=(1000))) 1000 loops, best of 3: 1.05 ms per loop In [126]: %timeit unique(np.random.randint(5, size=(10000))) 100 loops, best of 3: 11 ms per loop

También creo que es interesante que esto pueda generalizarse fácilmente a la singularidad de otras operaciones. Me gusta esto:

import operator def unique(lst, cmp_op=operator.ne): return [] if lst==[] else [lst[0]] + unique(filter(lambda x: cmp_op(x, lst[0]), lst[1:]), cmp_op)

Por ejemplo, podría pasar una función que usa la noción de redondeo al mismo entero como si fuera "igualdad" para propósitos de unicidad, como esto:

def test_round(x,y): return round(x) != round(y)

entonces unique (some_list, test_round) proporcionaría los elementos únicos de la lista donde la singularidad ya no significaba la igualdad tradicional (lo que implica el uso de cualquier tipo de enfoque basado en conjuntos o basado en dict-key para este problema) solo el primer elemento que se redondea a K para cada posible entero K al que los elementos podrían redondear, por ejemplo:

In [6]: unique([1.2, 5, 1.9, 1.1, 4.2, 3, 4.8], test_round) Out[6]: [1.2, 5, 1.9, 4.2, 3]

Una solución recursiva simple:

def uniquefy_list(a): return uniquefy_list(a[1:]) if a[0] in a[1:] else [a[0]]+uniquefy_list(a[1:]) if len(a)>1 else [a[0]]

Una solución sin utilizar módulos o conjuntos importados:

text = "ask not what your country can do for you ask what you can do for your country" sentence = text.split(" ") noduplicates = [(sentence[i]) for i in range (0,len(sentence)) if sentence[i] not in sentence[:i]] print(noduplicates)

Da salida:

[''ask'', ''not'', ''what'', ''your'', ''country'', ''can'', ''do'', ''for'', ''you'']

esto conservará el orden y se ejecutará en tiempo O (n). Básicamente, la idea es crear un agujero donde se encuentre un duplicado y hundirlo en el fondo. Utiliza un puntero de lectura y escritura. siempre que se encuentre un duplicado, solo el puntero de lectura avanza y el puntero de escritura permanece en la entrada duplicada para sobrescribirlo.

def deduplicate(l): count = {} (read,write) = (0,0) while read < len(l): if l[read] in count: read += 1 continue count[l[read]] = True l[write] = l[read] read += 1 write += 1 return l[0:write]

Editar 2016

Como señaló Raymond, en Python OrderedDict donde OrderedDict se implementa en C, el enfoque de comprensión de lista será más lento que OrderedDict (a menos que realmente necesite la lista al final, e incluso entonces, solo si la entrada es muy corta). Así que la mejor solución para OrderedDict es OrderedDict .

Edición importante 2015

Como observa @abarnert , la biblioteca more_itertools ( pip install more_itertools ) contiene una función unique_everseen que está diseñada para resolver este problema sin ninguna mutación ilegible ( not seen.add ) en la lista de comprensión. Esta es también la solución más rápida también:

>>> from more_itertools import unique_everseen >>> items = [1, 2, 0, 1, 3, 2] >>> list(unique_everseen(items)) [1, 2, 0, 3]

Solo una simple biblioteca de importación y no hacks. Esto viene de una implementación de la receta unique_everseen que se parece a:

def unique_everseen(iterable, key=None): "List unique elements, preserving order. Remember all elements ever seen." # unique_everseen(''AAAABBBCCDAABBB'') --> A B C D # unique_everseen(''ABBCcAD'', str.lower) --> A B C D seen = set() seen_add = seen.add if key is None: for element in filterfalse(seen.__contains__, iterable): seen_add(element) yield element else: for element in iterable: k = key(element) if k not in seen: seen_add(k) yield element

En Python 2.7+ el ~~idioma común aceptado~~ (que funciona pero no está optimizado para la velocidad, ahora usaría unique_everseen ) para esto usa collections.OrderedDict :

Tiempo de ejecución: O (N)

>>> from collections import OrderedDict >>> items = [1, 2, 0, 1, 3, 2] >>> list(OrderedDict.fromkeys(items)) [1, 2, 0, 3]

Esto se ve mucho mejor que

seen = set() [x for x in seq if x not in seen and not seen.add(x)]

y no utiliza el truco feo :

not seen.add(x)

que se basa en el hecho de que set.add es un método in situ que siempre devuelve None por not None evalúa como True .

Sin embargo, tenga en cuenta que la solución de pirateo es más rápida en velocidad bruta, aunque tiene la misma complejidad de tiempo de ejecución O (N).

En Python 2.7 , la nueva forma de eliminar duplicados de un iterable mientras se mantiene en el orden original es:

>>> from collections import OrderedDict >>> list(OrderedDict.fromkeys(''abracadabra'')) [''a'', ''b'', ''r'', ''c'', ''d'']

En Python 3.5 , OrderedDict tiene una implementación en C. Mis tiempos muestran que este es ahora el más rápido y el más corto de los diversos enfoques para Python 3.5.

En Python 3.6 , el dict regular se volvió ordenado y compacto. (Esta característica es válida para CPython y PyPy, pero puede no estar presente en otras implementaciones). Eso nos da una nueva forma más rápida de dedupir y retener el orden:

>>> list(dict.fromkeys(''abracadabra'')) [''a'', ''b'', ''r'', ''c'', ''d'']

En Python 3.7 , el dictado regular está garantizado para ambos ordenados en todas las implementaciones. Entonces, la solución más rápida y rápida es:

>>> list(dict.fromkeys(''abracadabra'')) [''a'', ''b'', ''r'', ''c'', ''d'']

Respuesta a @max: una vez que te mueves a 3.6 o 3.7 y usas el dict regular en lugar de OrderedDict , no puedes superar el rendimiento de ninguna otra manera. El diccionario es denso y se convierte fácilmente en una lista casi sin sobrecarga. La lista de destino tiene un tamaño predeterminado para len (d) que guarda todos los tamaños que se producen en una lista de comprensión. Además, como la lista de claves internas es densa, copiar los punteros es casi tan rápido como una copia de lista.

from itertools import groupby [ key for key,_ in groupby(sortedList)]

La lista ni siquiera tiene que estar ordenada , la condición suficiente es que se agrupen valores iguales.

Edición: asumí que "preservar el orden" implica que la lista está realmente ordenada. Si este no es el caso, entonces la solución de MizardX es la correcta.

Edición comunitaria: esta es, sin embargo, la forma más elegante de "comprimir elementos consecutivos duplicados en un solo elemento".

l = [1,2,2,3,3,...] n = [] n.extend(ele for ele in l if ele not in set(n))

Una expresión generadora que utiliza la búsqueda O (1) de un conjunto para determinar si incluir o no un elemento en la nueva lista.

sequence = [''1'', ''2'', ''3'', ''3'', ''6'', ''4'', ''5'', ''6''] unique = [] [unique.append(item) for item in sequence if item not in unique]

único → [''1'', ''2'', ''3'', ''6'', ''4'', ''5'']