Operacja odejmowania listy w języku Python

Chcę zrobić coś podobnego do tego:

>>> x = [1,2,3,4,5,6,7,8,9,0]  
>>> x  
[1, 2, 3, 4, 5, 6, 7, 8, 9, 0]  
>>> y = [1,3,5,7,9]  
>>> y  
[1, 3, 5, 7, 9]  
>>> y - x   # (should return [2,4,6,8,0])

Ale nie jest to obsługiwane przez listy python Jaki jest najlepszy sposób na zrobienie tego?

Użyj zrozumienia listy:

[item for item in x if item not in y]

Jeśli chcesz użyć -składni infix, możesz po prostu:

class MyList(list):
    def __init__(self, *args):
        super(MyList, self).__init__(args)

    def __sub__(self, other):
        return self.__class__(*[item for item in self if item not in other])

możesz użyć go w następujący sposób:

x = MyList(1, 2, 3, 4)
y = MyList(2, 5, 2)
z = x - y   

Ale jeśli nie potrzebujesz absolutnie właściwości listy (na przykład zamawiania), po prostu użyj zestawów, które zalecają inne odpowiedzi.

Użyj ustawionej różnicy

>>> z = list(set(x) - set(y))
>>> z
[0, 8, 2, 4, 6]

Lub możesz mieć po prostu xiy, więc nie musisz wykonywać żadnych konwersji.

Jest to operacja „ustawiania odejmowania”. Użyj do tego ustawionej struktury danych.

W Python 2.7:

x = {1,2,3,4,5,6,7,8,9,0}
y = {1,3,5,7,9}
print x - y

Wynik:

>>> print x - y
set([0, 8, 2, 4, 6])

jeśli zduplikowane i zamawiane elementy stanowią problem:

[i for i in a if not i in b or b.remove(i)]

a = [1,2,3,3,3,3,4]
b = [1,3]
result: [2, 3, 3, 3, 4]

W wielu przypadkach użycia odpowiedź brzmi:

ys = set(y)
[item for item in x if item not in ys]

Jest to hybryda między odpowiedzią aaronasterling a odpowiedzią quantumSoup .

Wersja aaronasterlinga len(y)porównuje elementy dla każdego elementu x, więc zajmuje kwadratowy czas. Wersja quantumSoup używa zestawów, więc wykonuje pojedyncze wyszukiwanie zestawu w czasie stałym dla każdego elementu w x—Ale ponieważ konwertuje oba x i yna zestawy, traci kolejność elementów.

Konwertując tylko yna zbiór i iterując xpo kolei, otrzymujesz to, co najlepsze z obu światów - czas liniowy i zachowanie porządku. *

Jednak nadal ma to problem z wersją quantumSoup: wymaga, aby twoje elementy mogły być haszowalne. Jest to dość wbudowane w naturę zbiorów. ** Jeśli próbujesz np. Odjąć listę nagrań z innej listy nagrań, ale lista do odjęcia jest duża, co robisz?

Jeśli potrafisz udekorować swoje wartości w sposób umożliwiający ich haszowanie, rozwiąże to problem. Na przykład za pomocą płaskiego słownika, którego wartości same są haszowalne:

ys = {tuple(item.items()) for item in y}
[item for item in x if tuple(item.items()) not in ys]

Jeśli Twoje typy są nieco bardziej skomplikowane (np. Często masz do czynienia z wartościami kompatybilnymi z JSON, które są haszowalne, lub listami lub słownikami, których wartości są rekurencyjnie tego samego typu), możesz nadal korzystać z tego rozwiązania. Ale niektórych typów po prostu nie można przekształcić w nic, co da się mieszać.

Jeśli twoje przedmioty nie są i nie można ich utworzyć haszowalne, ale są porównywalne, możesz przynajmniej uzyskać log-liniowy czas ( O(N*log M)który jest znacznie lepszy niż O(N*M)czas rozwiązania listy, ale nie tak dobry jak O(N+M)czas zbioru roztworem) do sortowania i przy użyciu bisect:

ys = sorted(y)
def bisect_contains(seq, item):
    index = bisect.bisect(seq, item)
    return index < len(seq) and seq[index] == item
[item for item in x if bisect_contains(ys, item)]

Jeśli twoje przedmioty nie są haszowalne ani porównywalne, to utkniesz w kwadratowym rozwiązaniu.

_{* Pamiętaj, że możesz to również zrobić za pomocą pary OrderedSetobiektów, dla których możesz znaleźć przepisy i moduły innych firm. Ale myślę, że to jest prostsze.}

_{** Powodem wyszukiwania zestawów jest stały czas, ponieważ wszystko, co musi zrobić, to haszować wartość i sprawdzić, czy istnieje wpis dla tego skrótu. Jeśli nie może uzyskać wartości skrótu, to nie zadziała.}

Wyszukiwanie wartości w zestawach jest szybsze niż wyszukiwanie ich na listach:

[item for item in x if item not in set(y)]

Uważam, że będzie to skalować nieco lepiej niż:

[item for item in x if item not in y]

Oba zachowują kolejność list.

Jeśli listy pozwalają na duplikowanie elementów, możesz użyć Licznika z kolekcji:

from collections import Counter
result = list((Counter(x)-Counter(y)).elements())

Jeśli chcesz zachować kolejność elementów od x:

result = [ v for c in [Counter(y)] for v in x if not c[v] or c.subtract([v]) ]

Inne rozwiązania mają jeden z kilku problemów:

1. Nie zachowują porządku, lub
2. Nie usuwają dokładnej liczby elementów, np. Dla x = [1, 2, 2, 2]i y = [2, 2]konwertują yna a set, albo usuwają wszystkie pasujące elementy (pozostawiając [1]tylko) lub usuwają jeden z każdego unikalnego elementu (pozostawiając [1, 2, 2]), gdy właściwym zachowaniem byłoby usunięcie go 2dwukrotnie, pozostawiając [1, 2], lub
3. Działają tam O(m * n), gdzie optymalne rozwiązanie może O(m + n)działać

Alain był na dobrej drodzeCounter do rozwiązania # 2 i # 3, ale to rozwiązanie straci porządek. Rozwiązaniem, które zachowuje porządek (usuwanie pierwszych nkopii każdej wartości w celu npowtórzeń w listwartościach do usunięcia) jest:

from collections import Counter

x = [1,2,3,4,3,2,1]  
y = [1,2,2]  
remaining = Counter(y)

out = []
for val in x:
    if remaining[val]:
        remaining[val] -= 1
    else:
        out.append(val)
# out is now [3, 4, 3, 1], having removed the first 1 and both 2s.

Wypróbuj online!

Aby usunąć ostatnie kopie każdego elementu, wystarczy zmienić forpętlę na for val in reversed(x):i dodać out.reverse()natychmiast po wyjściu z forpętli.

Konstruowanie Counterjest O(n)pod względem ydługości, iteracja xjest O(n)pod względem xdługości, a Countertesty członkostwa i mutacje są O(1), podczas gdy, list.appendamortyzowane O(1)(dane appendmogą być O(n), ale dla wielu appends, ogólnymi średnimi wielkimi O, O(1)ponieważ coraz mniej z nich wymaga realokacji), więc cała wykonana praca jest O(m + n).

Możesz również przetestować, aby ustalić, czy były w nim elementy y, które nie zostały usunięte z xtestowania:

remaining = +remaining  # Removes all keys with zero counts from Counter
if remaining:
    # remaining contained elements with non-zero counts

Spróbuj tego.

def subtract_lists(a, b):
    """ Subtracts two lists. Throws ValueError if b contains items not in a """
    # Terminate if b is empty, otherwise remove b[0] from a and recurse
    return a if len(b) == 0 else [a[:i] + subtract_lists(a[i+1:], b[1:]) 
                                  for i in [a.index(b[0])]][0]

>>> x = [1,2,3,4,5,6,7,8,9,0]
>>> y = [1,3,5,7,9]
>>> subtract_lists(x,y)
[2, 4, 6, 8, 0]
>>> x = [1,2,3,4,5,6,7,8,9,0,9]
>>> subtract_lists(x,y)
[2, 4, 6, 8, 0, 9]     #9 is only deleted once
>>>

Myślę, że najłatwiejszym sposobem na osiągnięcie tego jest użycie set ().

>>> x = [1,2,3,4,5,6,7,8,9,0]  
>>> y = [1,3,5,7,9]  
>>> list(set(x)- set(y))
[0, 2, 4, 6, 8]

Odpowiedź udzielana przez @aaronasterling wygląda dobrze, jednak nie jest kompatybilny z interfejsem domyślnej listy: x = MyList(1, 2, 3, 4)vs x = MyList([1, 2, 3, 4]). Zatem poniższy kod może być użyty jako bardziej przyjazna dla listy python:

class MyList(list):
    def __init__(self, *args):
        super(MyList, self).__init__(*args)

    def __sub__(self, other):
        return self.__class__([item for item in self if item not in other])

Przykład:

x = MyList([1, 2, 3, 4])
y = MyList([2, 5, 2])
z = x - y

Myślę, że to jest szybsze:

In [1]: a = [1,2,3,4,5]

In [2]: b = [2,3,4,5]

In [3]: c = set(a) ^ set(b)

In [4]: c
Out[4]: {1}

Ten przykład odejmuje dwie listy:

# List of pairs of points
list = []
list.append([(602, 336), (624, 365)])
list.append([(635, 336), (654, 365)])
list.append([(642, 342), (648, 358)])
list.append([(644, 344), (646, 356)])
list.append([(653, 337), (671, 365)])
list.append([(728, 13), (739, 32)])
list.append([(756, 59), (767, 79)])

itens_to_remove = []
itens_to_remove.append([(642, 342), (648, 358)])
itens_to_remove.append([(644, 344), (646, 356)])

print("Initial List Size: ", len(list))

for a in itens_to_remove:
    for b in list:
        if a == b :
            list.remove(b)

print("Final List Size: ", len(list))