¿Cómo eliminar duplicados en una lista, mientras que la preservación del orden?

Question

Hay un integrado que elimina los duplicados de la lista en Python, mientras que la preservación del orden?Sé que se puede utilizar un conjunto de eliminar los duplicados, pero que destruye el orden original.También sé que puedo rodar mis propios como este:

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

(Gracias a relajarse para que ejemplo de código.)

Pero me gustaría aprovechar de una o más Python el lenguaje, si es posible.

Relacionadas con la pregunta: En Python, ¿cuál es el algoritmo más rápido para la eliminación de duplicados de una lista, de modo que todos los elementos son únicos mientras que la preservación del orden?

Answer 1

Aquí tiene algunas alternativas: http://www.peterbe.com/plog/uniqifiers- punto de referencia

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 a seen.add()? Python es un lenguaje dinámico, y resolver None cada iteración es más costoso que resolver una variable local. or 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, quizás 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.

(Pequeña nota adicional: <=> siempre devuelve <=>, por lo que el <=> anterior solo está allí como una forma de intentar una actualización establecida, y no como una parte integral del prueba lógica.)

Answer 2

Editar 2016

Como Raymond señaló , en python 3.5+ donde OrderedDict se implementa en C, el enfoque de comprensión de la lista será ser más lento que more_itertools (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 pip install more_itertools.

Edición importante 2015

Como @abarnert señala, las unique_everseen (not seen.add) contiene una 2.7+ función creada para resolver este problema sin ninguna ilegible (collections.OrderedDict) mutaciones en las listas de comprensión. Esta también es la solución más rápida:

>>> 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 de biblioteca simple y sin hacks. Esto proviene de una implementación de la receta de itertools set.add 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 None the aceptó modismo común (que funciona pero no está optimizado para la velocidad, ahora usaría not None ) para esto utiliza True :

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 <=> es un método en el lugar que siempre devuelve <=> por lo que <=> evalúa a <=>.

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

Answer 3

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 hizo 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 deducir mientras se conserva el orden:

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

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

<*>

---

Respuesta a @max: una vez que pasa a 3.6 o 3.7 y usa el dict regular en lugar de OrderedDict , realmente no puede 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á dimensionada previamente para len (d), lo que guarda todos los cambios de tamaño que se producen en una comprensión de la lista. Además, dado que la lista de claves internas es densa, copiar los punteros es casi tan rápido como una copia de la lista.

Answer 4

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

único & # 8594; ['1', '2', '3', '6', '4', '5']

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

Editar: Supuse 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: sin embargo, esta es la forma más elegante de " comprimir elementos consecutivos duplicados en un solo elemento " ;.

Answer 6

No patear un caballo muerto (esta pregunta es muy antigua y ya tiene muchas buenas respuestas), pero aquí hay una solución con 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]

Answer 7

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

Answer 8

Sólo para agregar otro (muy eficiente) implementación de una funcionalidad de 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]

Los tiempos

Hice algunos tiempos (Python 3.6) y estos muestran que es más rápido que el de todas las otras alternativas que he probado, 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 sólo para asegurarse de que también se hizo una prueba con más de duplicados sólo para comprobar si se 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()

Y una que contiene sólo 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()

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

---

Este iteration_utilities.unique_everseen la función también puede manejar unhashable valores en la entrada (sin embargo, con un O(n*n) el rendimiento en lugar de la O(n) el rendimiento 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.

Answer 9

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

Las itertools recetas tienen una función que hace esto, usando el < => establecer técnica, pero:

• Maneja una función seen estándar.
• No utiliza hacks indecorosos.
• Optimiza el bucle pre-vinculando key en lugar de buscarlo N veces. (seen.add también hace esto, pero algunas versiones no.)
• Optimiza el bucle usando f7, por lo que solo tiene que recorrer los elementos únicos en Python, en lugar de todos ellos. (Todavía iteras 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 append? Depende de sus datos, por lo que tendrá que probarlos y verlos. Si desea una lista al final, yield usa una listacomp, y no hay forma de hacerlo aquí. (Puede directamente list en lugar de more-iterools ing, o puede alimentar el generador en la función <=>, pero ninguno puede ser tan rápido como el LIST_APPEND dentro de una lista). En cualquier caso, por lo general, exprimiendo unos pocos microsegundos no van a ser tan importantes como tener una función fácil de entender, reutilizable y ya escrita que no requiera DSU para decorar.

Como con todas las recetas, también está disponible en <=> .

Si solo desea el caso no - <=>, 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

Answer 10

En Python 3.7 y superiores, los diccionarios son garantizado para recordar su orden de inserción de clave. La respuesta a esta 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:

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

Answer 11

Para tipos no hashaable (por ejemplo, lista de listas), basado 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 ) )]

Answer 12

Tomando prestada la idea recursiva utilizada para definir la función nub de Haskell para 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:]))

por ejemplo:

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 sub-lineal (no definitiva, pero sugiere que esto debería estar bien para los 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 otras operaciones puedan generalizar fácilmente a la unicidad. Así:

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 unicidad, como este:

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

luego único (some_list, test_round) proporcionaría los elementos únicos de la lista donde la unicidad ya no significa igualdad tradicional (lo que está implícito al usar cualquier tipo de enfoque basado en conjuntos o en dict-key para este problema), sino en su lugar pretendía tomar 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]

Answer 13

Variante de reducción 5 veces más rápida pero más sofisticada

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

Answer 14

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

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

Answer 15

Puede hacer referencia a una comprensión de la lista, ya que se está construyendo con el símbolo '_ [1]'.
Por ejemplo, la siguiente función unifica 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]']]

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

Answer 16

Podría hacer una especie de truco de comprensión de listas feo.

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

Answer 17

Enfoque relativamente efectivo con _sorted_ a numpy matrices:

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

Answer 18

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 se incluye o no un elemento en la nueva lista.

Answer 19

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

Answer 20

Si necesita un revestimiento, quizás 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 estoy equivocado

Answer 21

Si utiliza habitualmente pandas , y la estética es preferible al rendimiento, considere la función integrada 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

Tiempo:

    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

Answer 22

esto preservará el orden y se ejecutará en O (n) tiempo. Básicamente, la idea es crear un agujero donde se encuentre un duplicado y hundirlo hasta el fondo. hace uso de un puntero de lectura y escritura. cada vez que se encuentra 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]

Answer 23

Una solución sin usar 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']

Answer 24

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 los del s).

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 sublista 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 prueba simple 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]:                                                                                                                             

Answer 25

Elimina los valores duplicados en una secuencia, pero conserva el orden de los elementos restantes. Uso de la función de generador de propósito general.

# for hashable sequence
def remove_duplicates(items):
    seen = set()
    for item in items:
        if item not in seen:
            yield item
            seen.add(item)

a = [1, 5, 2, 1, 9, 1, 5, 10]
list(remove_duplicates(a))
# [1, 5, 2, 9, 10]



# for unhashable sequence
def remove_duplicates(items, key=None):
    seen = set()
    for item in items:
        val = item if key is None else key(item)
        if val not in seen:
            yield item
            seen.add(val)

a = [ {'x': 1, 'y': 2}, {'x': 1, 'y': 3}, {'x': 1, 'y': 2}, {'x': 2, 'y': 4}]
list(remove_duplicates(a, key=lambda d: (d['x'],d['y'])))
# [{'x': 1, 'y': 2}, {'x': 1, 'y': 3}, {'x': 2, 'y': 4}]

Answer 26

El enfoque de

zmk utiliza la comprensión de listas que es muy rápida, pero mantiene el orden de forma natural. Para aplicar a cadenas sensibles a mayúsculas y minúsculas, se puede modificar fácilmente. Esto también conserva el caso original.

def DelDupes(aseq) :
    seen = set()
    return [x for x in aseq if (x.lower() not in seen) and (not seen.add(x.lower()))]

Las funciones estrechamente asociadas son:

def HasDupes(aseq) :
    s = set()
    return any(((x.lower() in s) or s.add(x.lower())) for x in aseq)

def GetDupes(aseq) :
    s = set()
    return set(x for x in aseq if ((x.lower() in s) or s.add(x.lower())))