Usuń wszystkie elementy występujące na jednej liście z drugiej


365

Powiedzmy, że mam dwie listy l1i l2. Chcę wykonać l1 - l2, która zwraca wszystkie elementy l1nie w l2.

Mogę wymyślić naiwne podejście do tego, ale będzie to naprawdę nieefektywne. Jaki jest pytoniczny i skuteczny sposób to zrobić?

Jako przykład, jeśli mam l1 = [1,2,6,8] and l2 = [2,3,5,8], l1 - l2powinien wrócić[1,6]


12
Tylko wskazówka: PEP8 stwierdza, że ​​nie należy używać małych liter „L”, ponieważ wygląda zbyt podobnie jak 1.
spelchekr

2
Zgadzam się. Przeczytałem całe to pytanie i odpowiedzi, zastanawiając się, dlaczego ludzie wciąż używają jedenastu i dwunastu. Miałem sens tylko wtedy, gdy przeczytałem komentarz @spelchekr.
robline


@JimG. Ramka danych i lista to nie to samo.
ograniczenie aktywności

Odpowiedzi:


491

Python ma funkcję językową o nazwie Listy, która doskonale nadaje się do tego, aby tego rodzaju rzeczy były niezwykle łatwe. Poniższa instrukcja robi dokładnie to, co chcesz i zapisuje wynik l3:

l3 = [x for x in l1 if x not in l2]

l3będzie zawierać [1, 6].


8
Bardzo pytoniczny; Lubię to! Jaka jest wydajność?
fandom

2
Uważam, że jest dość wydajny i ma tę zaletę, że jest wyjątkowo czytelny i jasny, co próbujesz osiągnąć. Natknąłem się na blogu można znaleźć interesujący odnoszące się do efektywności: blog.cdleary.com/2010/04/efficiency-of-list-comprehensions
Donut

6
@ fandom: samo rozumienie listy jest dość wydajne (chociaż rozumienie generatora może być bardziej wydajne, nie powielając elementów w pamięci), ale inoperator nie jest tak wydajny na liście. inna liście jest O (n), podczas gdy inna zestawie jest O (1). Jednak dopóki nie dojdziesz do tysięcy elementów lub więcej, raczej nie zauważysz różnicy.
Daniel Pryden,

1
l3 = [x for x in l1 if x not in set(l2)]? Jestem pewien, czy set(l2)zostałbym powołany więcej niż jeden raz.
Danosaure

5
Możesz także ustawić, l2s = set(l2)a następnie powiedzieć l3 = [x for x in l1 if x not in l2s]. Nieco łatwiej.
spelchekr

149

Jednym ze sposobów jest użycie zestawów:

>>> set([1,2,6,8]) - set([2,3,5,8])
set([1, 6])

58
Spowoduje to również usunięcie duplikatów l1, co może być niepożądanym efektem ubocznym.
kindall

37
.. i stracić kolejność elementów (jeśli kolejność jest ważna).
Danosaure,

3
Chcę tylko dodać, że to czasowe vs. Zaakceptowanych odpowiedź i to było bardziej wydajnych przez współczynnik wynoszący około 3: timeit.timeit('a = [1,2,3,4]; b = [1,3]; c = [i for i in a if a not in b]', number=100000) -> 0.12061533199999985 timeit.timeit('a = {1,2,3,4}; b = {1,3}; c = a - b', number=100000) -> 0.04106225999998969. Więc jeśli wydajność jest znaczącym czynnikiem, ta odpowiedź może być bardziej odpowiednia (a także, jeśli nie obchodzi cię duplikat lub zamówienie)
wfgeo

37

Alternatywnie możesz również użyć filterwyrażenia lambda, aby uzyskać pożądany wynik. Na przykład:

>>> l1 = [1,2,6,8]
>>> l2 = set([2,3,5,8])

#     v  `filter` returns the a iterator object. Here I'm type-casting 
#     v  it to `list` in order to display the resultant value
>>> list(filter(lambda x: x not in l2, l1))
[1, 6]

Porównanie wydajności

Tutaj porównuję wyniki wszystkich wymienionych tutaj odpowiedzi. Zgodnie z oczekiwaniami operacja set oparta na Arkku jest najszybsza.

  • Różnica zestawu Arkku - pierwsza ( 0,122 usec na pętlę)

    mquadri$ python -m timeit -s "l1 = set([1,2,6,8]); l2 = set([2,3,5,8]);" "l1 - l2"
    10000000 loops, best of 3: 0.124 usec per loop
    
  • Zrozumienie listy Daniela Prydena z setwyszukiwaniem - drugie (0,302 usec na pętlę)

    mquadri$ python -m timeit -s "l1 = [1,2,6,8]; l2 = set([2,3,5,8]);" "[x for x in l1 if x not in l2]"
    1000000 loops, best of 3: 0.302 usec per loop
    
  • Zrozumienie listy pączków na zwykłej liście - trzecia (0,552 usec na pętlę)

    mquadri$ python -m timeit -s "l1 = [1,2,6,8]; l2 = [2,3,5,8];" "[x for x in l1 if x not in l2]"
    1000000 loops, best of 3: 0.552 usec per loop
    
  • Używanie Moinuddina Quadrifilter - czwarte (0,972 usec na pętlę)

    mquadri$ python -m timeit -s "l1 = [1,2,6,8]; l2 = set([2,3,5,8]);" "filter(lambda x: x not in l2, l1)"
    1000000 loops, best of 3: 0.972 usec per loop
    
  • Akshay Hazari używa kombinacji reduce+filter - piąta (3,97 usec na pętlę)

    mquadri$ python -m timeit "l1 = [1,2,6,8]; l2 = [2,3,5,8];" "reduce(lambda x,y : filter(lambda z: z!=y,x) ,l1,l2)"
    100000 loops, best of 3: 3.97 usec per loop
    

PS: set nie utrzymuje kolejności i usuwa zduplikowane elementy z listy. Dlatego nie używaj ustawionej różnicy, jeśli potrzebujesz którejkolwiek z nich.


32

Rozwijając odpowiedź Donut i inne odpowiedzi tutaj, możesz uzyskać jeszcze lepsze wyniki, używając zrozumienia generatora zamiast zrozumienia listy i setstruktury danych (ponieważ inoperator jest O (n) na liście, ale O (1) na planie).

Oto funkcja, która zadziała dla Ciebie:

def filter_list(full_list, excludes):
    s = set(excludes)
    return (x for x in full_list if x not in s)

Wynik będzie iterowalny, który leniwie pobierze przefiltrowaną listę. Jeśli potrzebujesz prawdziwego obiektu listy (np. Jeśli musisz zrobić len()na wyniku), możesz łatwo zbudować listę w ten sposób:

filtered_list = list(filter_list(full_list, excludes))

29

Użyj typu zestawu Python. To byłoby najbardziej pytoniczne. :)

Ponadto, ponieważ jest natywny, powinna być również najbardziej zoptymalizowaną metodą.

Widzieć:

http://docs.python.org/library/stdtypes.html#set

http://docs.python.org/library/sets.htm (dla starszych python)

# Using Python 2.7 set literal format.
# Otherwise, use: l1 = set([1,2,6,8])
#
l1 = {1,2,6,8}
l2 = {2,3,5,8}
l3 = l1 - l2

5
Używając zestawów należy zauważyć, że wyjście jest uporządkowane, tzn. {1,3,2} staje się {1,2,3}, a {"A", "C", "B"} staje się {"A", „B”, „C”} i możesz tego nie chcieć.
Pablo Reyes

2
ta metoda nie będzie działać, jeśli lista l1zawiera powtarzające się elementy.
jdhao,

10

użyj Ustawić wyrażenia {x dla x w l2} lub ustaw (l2), aby uzyskać zestaw, a następnie użyj Wyjaśnienia listy, aby uzyskać listę

l2set = set(l2)
l3 = [x for x in l1 if x not in l2set]

kod testu porównawczego:

import time

l1 = list(range(1000*10 * 3))
l2 = list(range(1000*10 * 2))

l2set = {x for x in l2}

tic = time.time()
l3 = [x for x in l1 if x not in l2set]
toc = time.time()
diffset = toc-tic
print(diffset)

tic = time.time()
l3 = [x for x in l1 if x not in l2]
toc = time.time()
difflist = toc-tic
print(difflist)

print("speedup %fx"%(difflist/diffset))

wynik testu porównawczego:

0.0015058517456054688
3.968189239501953
speedup 2635.179227x    

1
l2set = set( l2 )zamiastl2set = { x for x in l2 }
cz

1
Niezła dusza! Należy jednak pamiętać, że działa tylko z obiektami, które można haszować.
Eerik Sven Puudist,

7

Alternatywne rozwiązanie:

reduce(lambda x,y : filter(lambda z: z!=y,x) ,[2,3,5,8],[1,2,6,8])

2
Czy korzystanie z tej metody jest zaletą? Wygląda na to, że jest bardziej złożony i trudniejszy do odczytania bez większych korzyści.
skrrgwasme

To może wydawać się skomplikowane. Redukcja jest bardzo elastyczna i może być używana do wielu celów. Jest znany jako fold. redukcja jest w rzeczywistości zwijana. Załóżmy, że chcesz dodać do niej bardziej złożone rzeczy, będzie to możliwe w tej funkcji, ale zrozumienie listy, która jest wybraną najlepszą odpowiedzią, da ci tylko wynik tego samego typu, tj. Listę i prawdopodobnie tej samej długości, a przy fałdach możesz zmień także typ wyjścia. en.wikipedia.org/wiki/Fold_%28higher-order_function%29 . To rozwiązanie jest n * m lub mniej złożone. Inni mogą, ale nie muszą być lepsi.
Akshay Hazari

1
zmniejszyć (funkcja, lista, akumulator początkowy (który może być dowolnego typu))
Akshay Hazari
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.