Czy istnieje wbudowany moduł, który usuwa duplikaty z listy w Pythonie, zachowując jednocześnie porządek? Wiem, że mogę użyć zestawu do usuwania duplikatów, ale to niszczy pierwotną kolejność. Wiem też, że mogę wykonać własne:

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

(Dzięki odprężeniu dla tego przykładu kodu .)

Ale chciałbym skorzystać z wbudowanego lub bardziej Pythonowego idiomu, jeśli to możliwe.

Powiązane pytanie: Jaki jest najszybszy algorytm usuwania duplikatów z listy, aby wszystkie elementy były unikalne przy zachowaniu porządku ?

Tutaj masz kilka alternatyw: http://www.peterbe.com/plog/uniqifiers-benchmark

Najszybszy:

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

Po co przypisywać seen.adddo seen_addzamiast tylko dzwonić seen.add? Python jest językiem dynamicznym, a rozwiązywanie seen.addkażdej iteracji jest droższe niż rozwiązywanie zmiennej lokalnej. seen.addmógł się zmieniać między iteracjami, a środowisko wykonawcze nie jest wystarczająco inteligentne, aby to wykluczyć. Aby grać bezpiecznie, musi za każdym razem sprawdzać obiekt.

Jeśli planujesz dużo korzystać z tej funkcji w tym samym zbiorze danych, być może lepiej byłoby, gdybyś zamówił zestaw: http://code.activestate.com/recipes/528878/

O (1) wstawianie, usuwanie i sprawdzanie członków na operację.

(Mała dodatkowa uwaga: seen.add()zawsze powraca None, więc orpowyższe jest tylko jako próba próby zestawu aktualizacji, a nie jako integralna część testu logicznego.)

Edytuj 2016

Jak zauważył Raymond , w Pythonie 3.5+, gdzie OrderedDictjest zaimplementowany w C, podejście do listowania będzie wolniejsze niż OrderedDict(chyba że faktycznie potrzebujesz listy na końcu - i nawet wtedy, tylko jeśli dane wejściowe są bardzo krótkie). Tak więc najlepszym rozwiązaniem dla wersji 3.5+ jest OrderedDict.

Ważna edycja 2015

Jak zauważa @abarnert , more_itertoolsbiblioteka ( pip install more_itertools) zawiera unique_everseenfunkcję zbudowaną w celu rozwiązania tego problemu bez żadnych nieczytelnych ( not seen.add) mutacji w zrozumieniu listy. Jest to również najszybsze rozwiązanie:

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

Tylko jeden prosty import biblioteki i bez włamań. Wynika to z implementacji przepisu itertools, unique_everseenktóry wygląda następująco:

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

W Pythonie Zaakceptowany wspólny idiom (który działa, ale nie jest zoptymalizowana pod kątem szybkości, chciałbym teraz wykorzystać ) dla tych zastosowań :2.7+unique_everseencollections.OrderedDict

Runtime: O (N)

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

Wygląda to o wiele ładniej niż:

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

i nie wykorzystuje brzydkiego hacka :

not seen.add(x)

który opiera się na fakcie, że set.addjest to metoda lokalna, która zawsze zwracaNone więc not Noneocenia True.

Należy jednak pamiętać, że rozwiązanie hakerskie jest szybsze z prędkością pierwotną, chociaż ma tę samą złożoność środowiska wykonawczego O (N).

W Pythonie 2.7 nowy sposób usuwania duplikatów z iterowalnych przy jednoczesnym zachowaniu ich w oryginalnej kolejności to:

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

W Python 3.5 OrDERDict ma implementację C. Moje czasy wskazują, że jest to zarówno najszybsze, jak i najkrótsze z różnych podejść do Pythona 3.5.

W Pythonie 3.6 zwykły słownik stał się uporządkowany i zwarty. (Ta funkcja dotyczy CPython i PyPy, ale może nie występować w innych implementacjach). To daje nam nowy najszybszy sposób deduplikacji przy zachowaniu porządku:

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

W Pythonie 3.7 regularny słownik jest gwarantowany zarówno we wszystkich implementacjach. Zatem najkrótszym i najszybszym rozwiązaniem jest:

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

Odpowiedź na @max: po przejściu do wersji 3.6 lub 3.7 i użyciu zwykłego dykta zamiast OrdersDict , nie można naprawdę pobić wydajności w żaden inny sposób. Słownik jest gęsty i łatwo przekształca się w listę prawie bez narzutów. Lista docelowa ma wstępnie ustawiony rozmiar na len (d), co powoduje zapisanie wszystkich rozmiarów, które występują w zrozumieniu listy. Ponadto, ponieważ wewnętrzna lista kluczy jest gęsta, kopiowanie wskaźników jest prawie szybkie jak kopiowanie listy.

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

unikalny → ['1', '2', '3', '6', '4', '5']

Nie kopać martwego konia (to pytanie jest bardzo stare i ma już wiele dobrych odpowiedzi), ale oto rozwiązanie wykorzystujące pandy, które jest dość szybkie w wielu okolicznościach i jest martwe proste w użyciu.

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]

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

Lista nie musi nawet być sortowana , wystarczającym warunkiem jest zgrupowanie równych wartości.

Edycja: założyłem, że „zachowanie porządku” oznacza, że ​​lista jest faktycznie uporządkowana. Jeśli tak nie jest, to rozwiązanie od MizardX jest właściwe.

Edycja społeczności: jest to jednak najbardziej elegancki sposób na „skompresowanie zduplikowanych kolejnych elementów w jeden element”.

Myślę, że jeśli chcesz utrzymać porządek,

możesz spróbować:

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

LUB podobnie możesz to zrobić:

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

Możesz także to zrobić:

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

Można go również zapisać w następujący sposób:

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

W Pythonie 3.7 i nowszych gwarantuje się , że słowniki zapamiętują kolejność wprowadzania kluczy. Odpowiedź na to pytanie podsumowuje obecny stan rzeczy.

OrderedDictRozwiązanie staje się przestarzałe i bez jakichkolwiek oświadczeń importowych możemy po prostu wydać:

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

Na kolejną bardzo późną odpowiedź na inne bardzo stare pytanie:

Te itertoolsprzepisy mają funkcję, która robi to, stosując seentechnikę zestaw, ale:

• Obsługuje funkcję standardową key.
• Nie używa niestosownych hacków.
• Optymalizuje pętlę przez wstępne wiązanie seen.addzamiast wyszukiwania N razy. ( f7robi to również, ale niektóre wersje nie.)
• Optymalizuje pętlę za pomocą ifilterfalse, więc wystarczy zapętlić tylko unikalne elementy w Pythonie, a nie wszystkie. (Wciąż iterujesz je wszystkie wewnątrz ifilterfalse, oczywiście, ale jest to w C i znacznie szybciej).

Czy to jest rzeczywiście szybsze niż f7? To zależy od twoich danych, więc będziesz musiał je przetestować i zobaczyć. Jeśli chcesz listę w końcu, f7używa listcomp i nie ma na to sposobu. (Możesz bezpośrednio appendzamiast yielding lub możesz wprowadzić generator dolist funkcji, ale żaden nie może być tak szybki, jak LIST_APPEND wewnątrz listcomp.) W każdym razie zwykle wyciśnięcie kilku mikrosekund nie będzie tak szybkie ważne, aby mieć łatwą do zrozumienia, nadającą się do wielokrotnego użytku, już napisaną funkcję, która nie wymaga DSU, gdy chcesz ozdobić.

Podobnie jak w przypadku wszystkich przepisów, jest również dostępny w more-iterools .

Jeśli chcesz tylko niepotrzebny keyprzypadek, możesz go uprościć:

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

Wystarczy dodać kolejny (bardzo wydajnych) realizacja takiej funkcjonalności z modułu zewnętrznego ¹ : 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]

Czasy

Zrobiłem kilka czasy (Python 3.6) i te pokazują, że jest to szybsze niż wszystkich innych testowanych rozwiązań alternatywnych, w tym ja OrderedDict.fromkeys, f7i 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()

I żeby się upewnić, że zrobiłem test z większą liczbą duplikatów, żeby sprawdzić, czy to robi różnicę:

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

I jedna zawierająca tylko jedną wartość:

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

We wszystkich tych przypadkach iteration_utilities.unique_everseenfunkcja jest najszybsza (na moim komputerze).

Ta iteration_utilities.unique_everseenfunkcja może również obsługiwać wartości niehashowane na wejściu (jednak z O(n*n)wydajnością zamiast O(n)wydajności, gdy wartości są możliwe do skrótu).

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

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

¹ Zastrzeżenie: Jestem autorem tego pakietu.

Dla typów haszujących (np. Listy list), opartych na 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 ) )]

Pożyczając rekursywną ideę używaną do zdefiniowania nubfunkcji Haskella dla list, byłoby to podejście rekurencyjne:

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

na przykład:

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

Próbowałem tego w celu zwiększenia rozmiarów danych i zobaczyłem sublinearną złożoność czasową (nie jest to ostateczne, ale sugeruje, że powinno być dobrze w przypadku normalnych danych).

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

Uważam również za interesujące, że można to łatwo uogólnić na wyjątkowość przez inne operacje. Lubię to:

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)

Na przykład możesz przekazać funkcję, która używa pojęcia zaokrąglania do tej samej liczby całkowitej, jakby to była „równość” dla celów wyjątkowości, jak poniżej:

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

następnie unikatowy (some_list, test_round) zapewniłby unikalne elementy listy, w których wyjątkowość nie oznaczała już tradycyjnej równości (co implikowane jest przez zastosowanie jakiegokolwiek podejścia opartego na zestawie lub kluczu dict do tego problemu), ale zamiast tego miała na celu tylko pierwszy element, który zaokrągla do K dla każdej możliwej liczby całkowitej K, do której elementy mogą zaokrąglać, np .:

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-krotnie szybsza redukcja wariantu, ale bardziej wyrafinowana

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

Wyjaśnienie:

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]

Możesz odnieść się do opisu listy, ponieważ jest ona budowana za pomocą symbolu „_ [1]”.
Na przykład następująca funkcja unikatowa wyświetla listę elementów bez zmiany ich kolejności przez odwołanie się do jej zrozumienia listy.

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

Próbny:

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

Wynik:

[1, 2, 3, 4, 5]

Odpowiedź MizardX daje dobry zbiór wielu podejść.

Oto, co wymyśliłem, głośno myśląc:

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

oto prosty sposób, aby to zrobić:

list1 = ["hello", " ", "w", "o", "r", "l", "d"]
sorted(set(list1 ), key=lambda x:list1.index(x))

co daje wynik:

["hello", " ", "w", "o", "r", "l", "d"]

Możesz zrobić coś w rodzaju brzydkiego włamania do listy.

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

Stosunkowo skuteczne podejście z _sorted_a numpytablic:

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

Wyjścia:

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

Wyrażenie generatora, które korzysta z wyszukiwania O (1) zestawu w celu ustalenia, czy element ma zostać uwzględniony na nowej liście.

Proste rozwiązanie rekurencyjne:

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

Eliminowanie zduplikowanych wartości w sekwencji, ale zachowaj kolejność pozostałych elementów. Zastosowanie funkcji generatora ogólnego przeznaczenia.

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

użytkownicy pand powinni sprawdzić pandas.unique.

>>> import pandas as pd
>>> lst = [1, 2, 1, 3, 3, 2, 4]
>>> pd.unique(lst)
array([1, 2, 3, 4])

Funkcja zwraca tablicę NumPy. W razie potrzeby można przekonwertować go na listę za pomocą tolistmetody

Jeśli potrzebujesz jednej wkładki, może to pomogłoby:

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

... powinien działać, ale popraw mnie, jeśli się mylę

Jeśli rutynowo używasz pandas, a estetyka jest lepsza niż wydajność, rozważ wbudowaną funkcję 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

Wyczucie czasu:

    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

pozwoli to zachować porządek i działać w czasie O (n). w zasadzie chodzi o utworzenie dziury w każdym miejscu, w którym znaleziono duplikat, i zatopienie go na dole. korzysta ze wskaźnika odczytu i zapisu. za każdym razem, gdy zostanie znaleziony duplikat, tylko wskaźnik odczytu przesuwa się i wskaźnik zapisu pozostaje na zduplikowanym wpisie, aby go zastąpić.

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]

Rozwiązanie bez użycia importowanych modułów lub zestawów:

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)

Daje wynik:

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

Metoda na miejscu

Ta metoda jest kwadratowa, ponieważ mamy liniowy przegląd listy dla każdego elementu listy (do tego musimy doliczyć koszt zmiany kolejności listy z powodu dels).

To powiedziawszy, możliwe jest działanie w miejscu, jeśli zaczniemy od końca listy i przejdziemy do źródła usuwając każdy termin, który jest obecny na liście podrzędnej po lewej stronie

Ten pomysł w kodzie jest po prostu

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

Prosty test wdrożenia

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

Podejście zmk wykorzystuje bardzo szybkie zrozumienie listy, ale naturalnie utrzymuje porządek. W przypadku ciągów rozróżniających wielkość liter można go łatwo modyfikować. To także zachowuje oryginalną obudowę.

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

Do ściśle powiązanych funkcji należą:

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

Zrozumienie jednej listy liniowej:

values_non_duplicated = [value for index, value in enumerate(values) if value not in values[ : index]]

Po prostu dodaj warunek, aby sprawdzić, czy wartość nie znajduje się na poprzedniej pozycji