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 ?
źródło
seen.add
mógł zmieniać się 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 spojrzysz na kod bajtowy za pomocądis.dis(f)
, zobaczysz, że wykonuje się onLOAD_ATTR
dla elementuadd
członkowskiego przy każdej iteracji. ideone.com/tz1Tllseen_add
jest poprawą, ale na zasoby czasowe mogą mieć wpływ zasoby systemowe w tym czasie.seen_add = seen.add
daje jedynie 1% wzrost prędkości. To mało znaczące.Edytuj 2016
Jak zauważył Raymond , w Pythonie 3.5+, gdzie
OrderedDict
jest 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+ jestOrderedDict
.Ważna edycja 2015
Jak zauważa @abarnert ,
more_itertools
biblioteka (pip install more_itertools
) zawieraunique_everseen
funkcję zbudowaną w celu rozwiązania tego problemu bez żadnych nieczytelnych (not seen.add
) mutacji w zrozumieniu listy. Jest to również najszybsze rozwiązanie:Tylko jeden prosty import biblioteki i bez włamań. Wynika to z implementacji przepisu itertools,
unique_everseen
który wygląda następująco: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_everseen
collections.OrderedDict
Runtime: O (N)
Wygląda to o wiele ładniej niż:
i nie wykorzystuje brzydkiego hacka :
który opiera się na fakcie, że
set.add
jest to metoda lokalna, która zawsze zwracaNone
więcnot None
oceniaTrue
.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).
źródło
[seen.add(x) for x in seq if x not in seen]
, lub jeśli nie lubisz rozumienia skutków ubocznych, po prostu użyjfor
pętli:for x in seq: seen.add(x) if x not in seen else None
(wciąż jest to jedna linijka, chociaż w tym przypadku myślę, że jedna linijka jest głupią właściwością, którą można mieć w rozwiązanieseen = set(seq)
.W Pythonie 2.7 nowy sposób usuwania duplikatów z iterowalnych przy jednoczesnym zachowaniu ich w oryginalnej kolejności to:
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:
W Pythonie 3.7 regularny słownik jest gwarantowany zarówno we wszystkich implementacjach. Zatem najkrótszym i najszybszym rozwiązaniem jest:
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.
źródło
OrderedDict
na listę. Jeśli muszę przekonwertować go na listę, w przypadku małych danych wejściowych podejście do listy jest jeszcze szybsze nawet 1,5 razy. To powiedziawszy, to rozwiązanie jest znacznie czystsze.set()
pomógłby bardziej naiwnym użytkownikom opracować powtarzalne kody.unikalny →
['1', '2', '3', '6', '4', '5']
źródło
n^2
None
referencji w trakcie!)for
Zamiast tego użyj pętliNie 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.
źródło
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”.
źródło
Myślę, że jeśli chcesz utrzymać porządek,
możesz spróbować:
LUB podobnie możesz to zrobić:
Możesz także to zrobić:
Można go również zapisać w następujący sposób:
źródło
W Pythonie 3.7 i nowszych gwarantuje się , że słowniki zapamiętują kolejność wprowadzania kluczy. Odpowiedź na to pytanie podsumowuje obecny stan rzeczy.
OrderedDict
Rozwiązanie staje się przestarzałe i bez jakichkolwiek oświadczeń importowych możemy po prostu wydać:źródło
Na kolejną bardzo późną odpowiedź na inne bardzo stare pytanie:
Te
itertools
przepisy mają funkcję, która robi to, stosującseen
technikę zestaw, ale:key
.seen.add
zamiast wyszukiwania N razy. (f7
robi to również, ale niektóre wersje nie.)ifilterfalse
, więc wystarczy zapętlić tylko unikalne elementy w Pythonie, a nie wszystkie. (Wciąż iterujesz je wszystkie wewnątrzifilterfalse
, 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,f7
używa listcomp i nie ma na to sposobu. (Możesz bezpośrednioappend
zamiastyield
ing 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
key
przypadek, możesz go uprościć:źródło
more-itertools
że jest to zdecydowanie najlepsza odpowiedź. Prostefrom more_itertools import unique_everseen
list(unique_everseen(items))
O wiele szybsze podejście niż moje i znacznie lepsze niż zaakceptowana odpowiedź, myślę, że warto pobrać bibliotekę. Idę do wiki społeczności moją odpowiedź i dodaję to.Wystarczy dodać kolejny (bardzo wydajnych) realizacja takiej funkcjonalności z modułu zewnętrznego 1 :
iteration_utilities.unique_everseen
: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
,f7
imore_itertools.unique_everseen
:I żeby się upewnić, że zrobiłem test z większą liczbą duplikatów, żeby sprawdzić, czy to robi różnicę:
I jedna zawierająca tylko jedną wartość:
We wszystkich tych przypadkach
iteration_utilities.unique_everseen
funkcja jest najszybsza (na moim komputerze).Ta
iteration_utilities.unique_everseen
funkcja może również obsługiwać wartości niehashowane na wejściu (jednak zO(n*n)
wydajnością zamiastO(n)
wydajności, gdy wartości są możliwe do skrótu).1 Zastrzeżenie: Jestem autorem tego pakietu.
źródło
seen_add = seen.add
- czy jest to potrzebne do testów?dict.fromkeys()
metodę do wykresu?ordereddict.fromkeys
?Dla typów haszujących (np. Listy list), opartych na MizardX:
źródło
Pożyczając rekursywną ideę używaną do zdefiniowania
nub
funkcji Haskella dla list, byłoby to podejście rekurencyjne:na przykład:
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).
Uważam również za interesujące, że można to łatwo uogólnić na wyjątkowość przez inne operacje. Lubię to:
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:
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 .:
źródło
filter
prawie nie skorzysta z poprzedniego połączenia. Ale jeśli liczba unikalnych elementów jest niewielka w stosunku do rozmiaru tablicy, powinno to działać całkiem dobrze.5-krotnie szybsza redukcja wariantu, ale bardziej wyrafinowana
Wyjaśnienie:
źródło
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.
Próbny:
Wynik:
źródło
Odpowiedź MizardX daje dobry zbiór wielu podejść.
Oto, co wymyśliłem, głośno myśląc:
źródło
O(n)
operacją i wykonuje się ją na każdym elemencie, złożoność wynikającego z niej rozwiązania byłaby następującaO(n^2)
. Jest to po prostu niedopuszczalne w przypadku tak trywialnego problemu.oto prosty sposób, aby to zrobić:
co daje wynik:
źródło
Możesz zrobić coś w rodzaju brzydkiego włamania do listy.
źródło
i,e in enumerate(l)
sięl[i] for i in range(len(l))
.Stosunkowo skuteczne podejście z
_sorted_
anumpy
tablic:Wyjścia:
źródło
Wyrażenie generatora, które korzysta z wyszukiwania O (1) zestawu w celu ustalenia, czy element ma zostać uwzględniony na nowej liście.
źródło
extend
z wyrażeniem generatora, które zależy od rozszerzenia rzeczy (więc +1), aleset(n)
jest przeliczane na każdym etapie (który jest liniowy), co podważa ogólne podejście do bycia kwadratowym. W rzeczywistości jest to prawie na pewno gorsze niż zwykłe używanieele in n
. Utworzenie zestawu do pojedynczego testu członkostwa nie jest warte kosztów stworzenia zestawu. Mimo to - to ciekawe podejście.Proste rozwiązanie rekurencyjne:
źródło
Eliminowanie zduplikowanych wartości w sekwencji, ale zachowaj kolejność pozostałych elementów. Zastosowanie funkcji generatora ogólnego przeznaczenia.
źródło
użytkownicy pand powinni sprawdzić
pandas.unique
.Funkcja zwraca tablicę NumPy. W razie potrzeby można przekonwertować go na listę za pomocą
tolist
metodyźródło
Jeśli potrzebujesz jednej wkładki, może to pomogłoby:
... powinien działać, ale popraw mnie, jeśli się mylę
źródło
Jeśli rutynowo używasz
pandas
, a estetyka jest lepsza niż wydajność, rozważ wbudowaną funkcjępandas.Series.drop_duplicates
:Wyczucie czasu:
źródło
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ć.
źródło
Rozwiązanie bez użycia importowanych modułów lub zestawów:
Daje wynik:
źródło
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
del
s).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
Prosty test wdrożenia
źródło
l[:] = <one of the the faster methods>
jeśli chcesz operacji na miejscu, nie?a=[1]; b=a; a[:]=[2]
wtedyb==[2]
wartość jestTrue
i możemy powiedzieć, że robią to w miejscu, mimo to co proponujesz jest za pomocą nowego miejsca, aby mieć nową listę, należy wymienić stare dane z nowych danych i zaznaczyć stare dane do wyrzucania elementów bezużytecznych, ponieważ nic już nie ma w nich odniesienia, więc powiedzenie, że działa w miejscu, nieco rozszerza koncepcję, co pokazałem, że jest możliwe ... czy jest nieefektywne? tak, ale powiedziałem to wcześniej.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ę.
Do ściśle powiązanych funkcji należą:
źródło
Zrozumienie jednej listy liniowej:
Po prostu dodaj warunek, aby sprawdzić, czy wartość nie znajduje się na poprzedniej pozycji
źródło