Come si rimuovono i duplicati da un elenco preservando l'ordine?

Question

Esiste un built-in che rimuove i duplicati dall'elenco in Python, preservando l'ordine? So che posso usare un set per rimuovere i duplicati, ma questo distrugge l'ordine originale. So anche che posso rotolare il mio in questo modo:

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

(Grazie a svolgersi per questo esempio di codice .)

Ma mi piacerebbe avvalermi di un linguaggio incorporato o più un linguaggio Pythonic, se possibile.

Domanda correlata: In Python, qual è l'algoritmo più veloce per rimuovere i duplicati da un elenco in modo che tutti gli elementi siano unici preservando l'ordine ?

Answer 1

Ecco alcune alternative: http://www.peterbe.com/plog/uniqifiers- punto di riferimento

Il più veloce:

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

Perché assegnare seen.add a seen_add invece di chiamare semplicemente seen.add()? Python è un linguaggio dinamico e la risoluzione di None ogni iterazione è più costosa della risoluzione di una variabile locale. or potrebbe essere cambiato tra le iterazioni e il runtime non è abbastanza intelligente da escluderlo. Per giocare in sicurezza, deve controllare l'oggetto ogni volta.

Se prevedi di utilizzare questa funzione molto sullo stesso set di dati, forse staresti meglio con un set ordinato: http://code.activestate.com/recipes/528878/

O (1) inserimento, cancellazione e controllo dei membri per operazione.

(Piccola nota aggiuntiva: <=> restituisce sempre <=>, quindi il <=> sopra è solo un modo per tentare un aggiornamento impostato e non come parte integrante del test logico.)

Answer 2

Modifica 2016

Come sottolineato da Raymond , in Python 3.5+ dove OrderedDict è implementato in C, l'approccio alla comprensione dell'elenco sarà essere più lento di more_itertools (a meno che non sia effettivamente necessario l'elenco alla fine - e anche in questo caso, solo se l'input è molto breve). Quindi la migliore soluzione per 3.5+ è pip install more_itertools.

Importante modifica 2015

Come @abarnert , la unique_everseen la libreria (not seen.add) contiene una 2.7+ creata per risolvere questo problema senza illeggibili (collections.OrderedDict) mutazioni nelle comprensioni dell'elenco. Questa è anche la soluzione più veloce:

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

Solo una semplice importazione di librerie e nessun hack. Questo deriva da un'implementazione della ricetta di itertools set.add che sembra:

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

---

In Python None il ha accettato il linguaggio comune (che funziona ma non è ottimizzato per la velocità, ora userei not None ) per questo usi True :

Runtime: O(N)

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

Sembra molto più bello di:

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

e non utilizza il brutto hack :

not seen.add(x)

che si basa sul fatto che <=> è un metodo sul posto che restituisce sempre <=> quindi <=> restituisce <=>.

Si noti tuttavia che la soluzione di hacking è più veloce nella velocità raw sebbene abbia la stessa complessità di runtime O (N).

Answer 3

In Python 2.7 , il nuovo modo di rimuovere i duplicati da un iterabile mantenendolo nell'ordine originale è:

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

In Python 3.5 , OrderedDict ha un'implementazione C. I miei tempi mostrano che questo è ora sia il più veloce sia il più breve dei vari approcci per Python 3.5.

In Python 3.6 , il dict regolare è diventato sia ordinato che compatto. (Questa funzione è valida per CPython e PyPy ma potrebbe non essere presente in altre implementazioni). Questo ci dà un nuovo modo più veloce di dedurre mantenendo l'ordine:

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

In Python 3.7 , il dict regolare è garantito per entrambi ordinato in tutte le implementazioni. Quindi, la soluzione più breve e veloce è:

<*>

---

Risposta a @max: una volta passati a 3.6 o 3.7 e usando il dict normale invece di OrderedDict , non puoi davvero battere la performance in nessun altro modo. Il dizionario è denso e si converte prontamente in un elenco quasi senza spese generali. L'elenco di destinazione è pre-dimensionato in len (d) che salva tutti i ridimensionamenti che si verificano in una comprensione dell'elenco. Inoltre, poiché l'elenco delle chiavi interne è denso, la copia dei puntatori è quasi veloce come una copia dell'elenco.

Answer 4

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

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

Answer 5

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

L'elenco non deve nemmeno essere ordinato , la condizione sufficiente è che valori uguali siano raggruppati insieme.

Modifica: ho ipotizzato che " preservando l'ordine " implica che l'elenco sia effettivamente ordinato. In caso contrario, la soluzione di MizardX è quella giusta.

Modifica comunità: questo è comunque il modo più elegante per " comprimere elementi consecutivi duplicati in un singolo elemento " ;.

Answer 6

Non calciare un cavallo morto (questa domanda è molto vecchia e ha già molte buone risposte), ma qui c'è una soluzione che usa i panda che è abbastanza veloce in molte circostanze ed è morto semplice da usare.

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

Penso che se vuoi mantenere l'ordine,

puoi provare questo:

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

O allo stesso modo puoi farlo:

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

Puoi anche farlo:

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

Può anche essere scritto come questo:

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

Solo per aggiungere un'altra implementazione (molto performante) di tale funzionalità da un modulo esterno ¹ : 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]

Tempi

Ho fatto alcuni cronometri (Python 3.6) e questi mostrano che è più veloce di tutte le altre alternative che ho testato, tra cui OrderedDict.fromkeys, f7 e 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()

E solo per essere sicuro di aver fatto anche un test con più duplicati solo per verificare se fa la differenza:

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

E uno contenente un solo valore:

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

In tutti questi casi la funzione O(n*n) è la più veloce (sul mio computer).

---

Questa funzione O(n) può anche gestire valori non lavabili nell'input (tuttavia con una prestazione <=> invece che <=> quando i valori sono hash).

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

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

---

¹ Disclaimer: sono l'autore di quel pacchetto.

Answer 9

Per un'altra risposta molto tardiva a un'altra domanda molto antica:

Le itertools ricette hanno una funzione che lo fa, usando < => imposta tecnica, ma:

• Gestisce una funzione seen standard.
• Non utilizza hack sconvenienti.
• Ottimizza il loop pre-binding key invece di cercarlo N volte. (seen.add lo fa anche, ma alcune versioni no.)
• Ottimizza il ciclo usando f7, quindi devi solo passare in rassegna gli elementi univoci in Python, anziché tutti. (Ovviamente continui a scorrere tutti all'interno di ifilterfalse, ovviamente, ma è in C e molto più velocemente.)

In realtà è più veloce di append? Dipende dai tuoi dati, quindi dovrai provarli e vedere. Se vuoi un elenco alla fine, yield usa un elenco completo e non c'è modo di farlo qui. (Puoi direttamente list invece di more-iterools ing, oppure puoi alimentare il generatore nella funzione <=>, ma nessuno dei due può essere veloce come il LIST_APPEND all'interno di un elenco.) Ad ogni modo, di solito, spremere alcuni microsecondi non saranno così importanti come avere una funzione già comprensibile, riutilizzabile, già scritta che non richiede DSU quando si desidera decorare.

Come per tutte le ricette, è disponibile anche in <=> .

Se vuoi solo il caso no - <=>, puoi semplificarlo come:

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

Answer 10

In Python 3.7 e versioni successive, i dizionari sono garantito per ricordare il loro ordine di inserimento delle chiavi. La risposta a questa domanda sintetizza lo stato attuale delle cose.

La soluzione OrderedDict diventa così obsoleta e senza dichiarazioni di importazione possiamo semplicemente emettere:

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

Answer 11

Per nessun tipo hash (es. elenco di elenchi), basato su 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

Prendendo in prestito l'idea ricorsiva utilizzata nella definizione della funzione nub di Haskell per gli elenchi, questo sarebbe un approccio ricorsivo:

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

per esempio:.

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

L'ho provato per dimensioni di dati crescenti e ho visto la complessità temporale lineare (non definitiva, ma suggerisce che dovrebbe andare bene per i dati normali).

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

Penso anche che sia interessante che questo possa essere prontamente generalizzato all'unicità da altre operazioni. In questo modo:

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)

Ad esempio, potresti passare una funzione che usa la nozione di arrotondamento allo stesso numero intero come se fosse " uguaglianza " per motivi di unicità, in questo modo:

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

quindi unico (some_list, test_round) fornirebbe gli elementi unici dell'elenco in cui l'unicità non significava più l'uguaglianza tradizionale (che è implicita usando qualsiasi tipo di approccio basato su set o dict-key a questo problema) ma invece intendeva prendere solo il primo elemento che viene arrotondato a K per ogni possibile numero intero K che gli elementi potrebbero arrotondare, ad esempio:

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

5 volte più veloce per ridurre la variante ma più sofisticato

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

Spiegazione:

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 risposta di MizardX offre una buona raccolta di approcci multipli.

Questo è quello che mi è venuto in mente pensando ad alta voce:

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

Answer 15

È possibile fare riferimento a una comprensione dell'elenco in quanto è stata creata dal simbolo '_ [1]'.
Ad esempio, la seguente funzione rende unico un elenco di elementi senza modificarne l'ordine facendo riferimento alla sua comprensione dell'elenco.

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

Demo:

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

Output:

[1, 2, 3, 4, 5]

Answer 16

Potresti fare una specie di brutto hack di comprensione dell'elenco.

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

Answer 17

Approccio relativamente efficace con _sorted_ a numpy array:

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

Uscite:

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

Un'espressione di generatore che utilizza la ricerca O (1) di un set per determinare se includere o meno un elemento nel nuovo elenco.

Answer 19

Una semplice soluzione ricorsiva:

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

Se hai bisogno di una fodera, forse questo sarebbe d'aiuto:

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

... dovrebbe funzionare ma correggimi se sbaglio

Answer 21

Se usi abitualmente pandas e l'estetica è preferita rispetto alle prestazioni, prendi in considerazione il built-in funzione 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

Tempi:

    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

questo conserverà l'ordine e verrà eseguito in O (n) tempo. fondamentalmente l'idea è quella di creare un buco ovunque ci sia un duplicato trovato e affondarlo fino in fondo. utilizza un puntatore di lettura e scrittura. ogni volta che viene trovato un duplicato, solo il puntatore di lettura avanza e il puntatore di scrittura rimane sulla voce duplicata per sovrascriverlo.

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 soluzione senza utilizzare moduli o set importati:

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)

Fornisce output:

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

Answer 24

Un metodo sul posto

Questo metodo è quadratico, perché abbiamo una ricerca lineare nella lista per ogni elemento della lista (a ciò dobbiamo aggiungere il costo di riorganizzare la lista a causa della del s).

Detto questo, è possibile operare sul posto se iniziamo dalla fine dell'elenco e procediamo verso l'origine rimuovendo ogni termine presente nell'elenco secondario alla sua sinistra

Questa idea nel codice è semplicemente

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

---

Un semplice test di implementazione

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

Eliminando i valori duplicati in una sequenza, ma preservando l'ordine degli elementi rimanenti. Uso della funzione del generatore per uso generico.

# 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

L'approccio di zmk usa la comprensione dell'elenco che è molto veloce, ma mantiene l'ordine naturalmente. Per l'applicazione a stringhe maiuscole e minuscole può essere facilmente modificato. Ciò preserva anche il caso originale.

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

Le funzioni strettamente associate sono:

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