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

¿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 este:

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

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

Pero me gustaría aprovecharme de un lenguaje incorporado o de un lenguaje más pythonico 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 ?

    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 dynamic, 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, quizás le convendría más con un conjunto ordenado: http://code.activestate.com/recipes/528878/

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

    (Nota adicional pequeña: seen.add () siempre devuelve Ninguno, por lo que el o superior es solo como una forma de intentar una actualización del conjunto, y no como una parte integral de la prueba lógica).

    Editar 2016

    Como Raymond señaló , en Python OrderedDict donde OrderedDict se implementa en C, el enfoque de comprensión de lista será más lento que en 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') --> ABCD # unique_everseen('ABBCcAD', str.lower) --> ABCD 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 función 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 está pre-dimensionada 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.

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

     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 los valores iguales.

    Edición: asumí que “preservar el orden” implica que la lista está en realidad 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”.

    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 

    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 utiliza pandas que es bastante rápida en muchas circunstancias y es muy fácil de usar.

     import pandas as pd 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] 

    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 mediante el enlace previo de 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 

    Solo para agregar otra implementación (muy eficaz) de tal funcionalidad desde un módulo externo 1 : 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() 

    introduzca la descripción de la imagen aquí

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

    introduzca la descripción de la imagen aquí

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

    introduzca la descripción de la imagen aquí

    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 no lavables 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}] 

    1 Descargo de responsabilidad: Soy el autor de ese paquete.

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

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

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

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

    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 boost 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 número entero como si fuera “igualdad” para propósitos de exclusividad, 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 singularidad ya no significaba la igualdad tradicional (lo que se implica mediante el uso de cualquier tipo de enfoque basado en conjuntos o basado en dict-key para este problema) solo el primer elemento que 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] 

    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] 

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

    Puede hacer referencia a una lista de comprensión, ya que está siendo construida por 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 lista de comprensión.

     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] 

    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] 

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

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

    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

    Si habitualmente usa pandas , y se prefiere la estética al rendimiento, entonces 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 

    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] 

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

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