Jak usunąć duplikaty z listy, zachowując porządek?

769

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 ?

Josh Glover
źródło

Odpowiedzi:

762

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

Markus Jarderot
źródło
20
@JesseDhillon seen.addmó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ę on LOAD_ATTRdla elementu addczłonkowskiego przy każdej iteracji. ideone.com/tz1Tll
Markus Jarderot
5
Kiedy próbuję tego na liście, otrzymuję: TypeError: unhashable type: 'list'
Jens Timmerman
7
Twoje rozwiązanie nie jest najszybsze. W Pythonie 3 (nie testowałem 2) jest to szybsze (lista 300 000 wpisów - 0,045s (twoje) w porównaniu do 0,035s (ta)): seen = set (); zwraca [x dla xw liniach, jeśli x nie jest widoczny i nie seen.add (x)]. Nie mogłem znaleźć żadnego efektu prędkości linii seen_add, który zrobiłeś
user136036 24.10.14
3
@ user136036 Link do swoich testów. Ile razy je uruchamiałeś? seen_addjest poprawą, ale na zasoby czasowe mogą mieć wpływ zasoby systemowe w tym czasie.
Byłbym
2
Dla każdego, kto pisze kod Pythona, naprawdę powinieneś pomyśleć dwa razy, zanim poświęcisz czytelność i wspólnie uzgodnione konwencje Pythona, aby wycisnąć jeszcze kilka nanosekund na pętlę. Testowanie z lub bez seen_add = seen.adddaje jedynie 1% wzrost prędkości. To mało znaczące.
sleblanc
343

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

jamylak
źródło
5
Konwertujesz na niestandardowy słownik, aby wziąć klucze? Kolejna kula.
Nakilon
3
@Nakilon Nie bardzo rozumiem, jak to jest kula. Nie ujawnia żadnego stanu zmiennego, więc jest bardzo czysty w tym sensie. Wewnętrznie zestawy Pythona są implementowane za pomocą dict () ( stackoverflow.com/questions/3949310/… ), więc w zasadzie robisz to, co zrobiłby interpreter.
Imran
Po prostu użyj efektów ubocznych i zrób to [seen.add(x) for x in seq if x not in seen], lub jeśli nie lubisz rozumienia skutków ubocznych, po prostu użyj forpę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ązanie
ely
@EMS To nie zachowuje porządku. Równie dobrze możesz seen = set(seq).
trzęsienie ziemi
1
@CommuSoft Zgadzam się, chociaż praktycznie zawsze jest to O (n) ze względu na bardzo mało prawdopodobny najgorszy przypadek
jamylak
110

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.

Raymond Hettinger
źródło
Jest szybszy niż jakiekolwiek inne podejście na mojej maszynie (python 3.5), o ile w końcu nie przekonwertuję OrderedDictna 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.
maks.
7
Jedyną przeszkodą jest to, że iterowalne „elementy” muszą być haszowalne - fajnie byłoby mieć odpowiednik dla iteracyjnych z dowolnymi elementami (jako lista list)
Mr_and_Mrs_D
Iteracja kolejności wstawiania nad dykta zapewnia funkcjonalność, która obsługuje więcej przypadków użycia niż usuwanie duplikatów. Na przykład analizy naukowe opierają się na odtwarzalnych obliczeniach, których nie obsługuje niedeterministyczna iteracja dyktanda. Powtarzalność jest obecnie głównym celem obliczeniowego modelowania naukowego, dlatego z zadowoleniem przyjmujemy tę nową funkcję. Chociaż wiem, że budowanie za pomocą deterministycznego dyktanda jest banalne, wysoce deterministyczny set()pomógłby bardziej naiwnym użytkownikom opracować powtarzalne kody.
Arthur
41
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']

dansalmo
źródło
28
Warto zauważyć, że to działan^2
goncalopp
25
Ick. 2 ostrzeżenia: Używanie listy do testowania członkostwa (powolne, O (N)) i używanie rozumienia listy dla skutków ubocznych (budowanie kolejnej listy Nonereferencji w trakcie!)
Martijn Pieters
1
Zgadzam się z @MartijnPieters, że absolutnie nie ma powodu, aby lista zawierała skutki uboczne. forZamiast tego użyj pętli
jamylak
31

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]
Alexander
źródło
27
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”.

Rafał Dowgird
źródło
1
Ale to nie zachowuje porządku!
1
Hrm, jest to problematyczne, ponieważ nie mogę zagwarantować, że równe wartości zostaną zgrupowane bez zapętlenia raz na liście, do tego czasu mógłbym przyciąć duplikaty.
Josh Glover
Zakładałem, że „zachowanie porządku” sugeruje, że lista jest faktycznie uporządkowana.
Rafał Dowgird
1
Może specyfikacja listy danych wejściowych jest nieco niejasna. Wartości nie trzeba nawet grupować razem: [2, 1, 3, 1]. Więc jakie wartości zachować, a które usunąć?
1
@igorkf Ignorowanie drugiego elementu pary.
Rafał Dowgird
24

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 
koniczyna
źródło
3
Pierwsze dwie odpowiedzi zakładają, że kolejność listy można odbudować za pomocą funkcji sortowania, ale może tak nie być.
Richard
5
Większość odpowiedzi dotyczy wydajności. W przypadku list, które nie są wystarczająco duże, aby martwić się wydajnością, posortowane (set (list1), key = list1.index) to najlepsza rzecz, jaką widziałem. Bez dodatkowego importu, bez dodatkowej funkcji, bez dodatkowej zmiennej i jest dość prosty i czytelny.
Derek Veit
23

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]
timb
źródło
11

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
abarnert
źródło
Całkowicie przeoczyłem, more-itertoolsże jest to zdecydowanie najlepsza odpowiedź. Proste from 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.
jamylak
11

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

wprowadź opis zdjęcia tutaj

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

wprowadź opis zdjęcia tutaj

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

wprowadź opis zdjęcia tutaj

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

1 Zastrzeżenie: Jestem autorem tego pakietu.

MSeifert
źródło
Nie rozumiem konieczności tej linii: seen_add = seen.add- czy jest to potrzebne do testów?
Alex
@Alex Takie podejście podano w tej odpowiedzi . Bardziej sensowne byłoby zapytać tam. Właśnie wykorzystałem podejście z tej odpowiedzi, aby porównać czasy.
MSeifert,
czy możesz dodać dict.fromkeys()metodę do wykresu?
Boris
Nie jestem do końca pewien, czy mam to samo, żeby szybko wykonać pomiary. Czy uważasz, że jest znacznie szybszy niż ordereddict.fromkeys?
MSeifert
6

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 ) )]
zmk
źródło
3

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]
Ely
źródło
1
Zauważ, że wydajność pogorszy się, gdy liczba unikalnych elementów będzie bardzo duża w stosunku do całkowitej liczby elementów, ponieważ użycie każdego kolejnego wywołania rekurencyjnego filterprawie 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.
ely
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]
Sergey M. Nikitin
źródło
3

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]
Zhifeng Hu
źródło
2
Zauważ też, że uczyniłoby to z operacji O (n ^ 2), w której tworzenie zestawu / dict (który ma stały czas wyszukiwania) i dodawanie tylko wcześniej niewidocznych elementów będzie liniowe.
ely
To jest tylko Python 2.6. I tak, to O (N ^ 2)
jamylak,
2

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:]]
Saurabh Hirani
źródło
Twoje rozwiązanie jest fajne, ale wymaga ostatniego wyglądu każdego elementu. Aby wziąć pierwszy występ, użyj: [x dla i, x w wyliczeniu (lista), jeśli x nie w liście [: i]]
Rivka
7
Ponieważ wyszukiwanie na liście jest O(n)operacją i wykonuje się ją na każdym elemencie, złożoność wynikającego z niej rozwiązania byłaby następująca O(n^2). Jest to po prostu niedopuszczalne w przypadku tak trywialnego problemu.
Nikita Volkov
2

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"]
Ahmed4end
źródło
1

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]

źródło
Wolę i,e in enumerate(l)się l[i] for i in range(len(l)).
Evpok
1

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])
dominecf
źródło
1
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.

kylie.a
źródło
1
Sprytne użycie extendz wyrażeniem generatora, które zależy od rozszerzenia rzeczy (więc +1), ale set(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żywanie ele in n. Utworzenie zestawu do pojedynczego testu członkostwa nie jest warte kosztów stworzenia zestawu. Mimo to - to ciekawe podejście.
John Coleman,
1

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]]
Ilya Prokin
źródło
1

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}]
Srivastava
źródło
1

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

timb
źródło
1
Niezłe. Nigdy nie wyobrażam sobie używania do tego pand, ale to działa
seralouk
0

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ę

code22
źródło
jest to wyrażenie warunkowe, więc jest dobre
code22
0

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
Lei
źródło
0

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]
Soham Joshi
źródło
0

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']
Rob Murray
źródło
jest to złożoność O (N ** 2) + segmentacja listy za każdym razem.
Jean-François Fabre
0

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]:                                                                                                                             
gboffi
źródło
Przed opublikowaniem przeszukałem treść odpowiedzi pod kątem „miejsca”, ale bezskutecznie. Jeśli inni rozwiązali problem w podobny sposób, proszę o powiadomienie, a jak najszybciej usunę moją odpowiedź.
gboffi
Możesz użyć, l[:] = <one of the the faster methods>jeśli chcesz operacji na miejscu, nie?
timgeb
@timgeb Tak i nie ... Kiedy ja a=[1]; b=a; a[:]=[2]wtedy b==[2]wartość jest Truei 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.
gboffi
0

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())))
Hewey Dewey
źródło
0

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

Jože Ws
źródło