Pregunta ¿Cómo se eliminan los duplicados de una lista sin perder el orden?


¿Hay un built-in que elimine los duplicados de la lista en Python, mientras se preserva el orden? Sé que puedo usar un conjunto para eliminar duplicados, pero eso destruye el orden original. También sé que puedo rodar el mío así:

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

(Gracias a relajarse para eso muestra de código.)

Pero me gustaría aprovechar un idioma incorporado o más idiotizado si es posible.

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


603
2018-01-26 15:43


origen


Respuestas:


Aquí tienes 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 en lugar de simplemente llamar seen.add? Python es un lenguaje dinámico y resolutivo seen.add cada iteración es más costosa 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 ir a lo seguro, tiene que verificar el objeto cada vez.

Si planea usar esta función mucho en el mismo conjunto de datos, tal vez serí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.


640
2018-01-26 15:47



Editar 2016

Como Raymond señalado, en Python 3.5+ donde OrderedDict se implementa en C, el enfoque de la lista de comprensión 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). Entonces, la mejor solución para 3.5+ es OrderedDict.

Importante Edición 2015

Como @abarnert notas, el more_itertools biblioteca (pip install more_itertools) contiene una unique_everseen función que está construida para resolver este problema sin ningún ilegible (not seen.add) mutaciones en lista de comprensiones. 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 importación simple de biblioteca y no hacks. Esto proviene de una implementación de la receta itertools unique_everseen que se ve así:

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 lenguaje 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: EN)

>>> 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 hack feo:

not seen.add(x)

que se basa en el hecho de que set.add es un método en el lugar que siempre regresa None asi que not None evalúa a True.

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


289
2017-10-03 15:47



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, el 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ó tanto ordenado como compacto. (Esta característica es válida para CPython y PyPy, pero puede no presentarse en otras implementaciones). Eso nos brinda una nueva forma más rápida de deduplicación al tiempo que conservamos el orden:

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

En Python 3.7, el dict regular está garantizado para ambos pedidos en todas las implementaciones. Entonces, la solución más rápida y corta 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 se puede superar el rendimiento de ninguna otra manera. El diccionario es denso y se convierte fácilmente en una lista casi sin gastos generales. La lista de objetivos está pre-dimensionada para len (d), lo que ahorra todos los cambios de tamaño que ocurren en una lista de comprensión. Además, dado que la lista de claves internas es densa, copiar los punteros es casi una copia de lista.


54
2018-04-13 17:32



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


39
2018-01-26 15:47



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

La lista ni siquiera tiene que ser ordenado, la condición suficiente es que los valores iguales se agrupen.

Editar: 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 manera más elegante de "comprimir elementos consecutivos duplicados en un solo elemento".


22
2018-05-27 21:37



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 de manera similar, 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 

18
2017-10-09 18:27



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

los itertools recetas tener una función que hace esto, usando el seen establecer la técnica, pero:

  • Maneja un estándar key función.
  • No utiliza impropios hacks.
  • Optimiza el ciclo mediante enlaces previos seen.add en lugar de buscarlo N veces. (f7 también lo hace, pero algunas versiones no lo hacen).
  • Optimiza el ciclo al usar ifilterfalse, por lo que solo tiene que recorrer los elementos únicos en Python, en lugar de todos. (Todavía iteras sobre todos ellos dentro ifilterfalse, por supuesto, pero eso está en C, y mucho más rápido).

¿Es realmente más rápido que f7? Depende de tus datos, por lo que tendrás que probarlo y verlo. Si quieres una lista al final, f7 usa un listcomp, y no hay manera de hacerlo aquí. (Puedes directamente append en lugar de yielding, o puede alimentar el generador en el list función, pero ninguno puede ser tan rápido como el LIST_APPEND dentro de un listcomp). En cualquier caso, por lo general, exprimir algunos microsegundos no va a ser tan importante como tener una función fácil de entender, reutilizable y ya escrita que no funcione No requiere DSU cuando quiere decorar.

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

Si solo quieres el no-key caso, 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

11
2018-01-10 19:55



Solo para agregar otra implementación (muy completa) de dicha funcionalidad desde un módulo externo1: 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()

enter image description here

Y solo para asegurarme de que también hice una prueba con más duplicados solo para comprobar si hace una 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()

enter image description here

Y uno que contiene solo un 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()

enter image description here

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


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

>>> lst = [{1}, {1}, {2}, {1}, {3}]

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

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


10
2017-08-21 20:04



Para los tipos no intercambiables (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 ) )]

6
2017-08-18 00:35