Wie subtrahiere ich eine Liste von einer anderen?

Ich möchte die nehmen Unterschied zwischen Listen x Und y:

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

Verwenden Sie ein Listenverständnis, um den Unterschied zu berechnen und dabei das Original beizubehalten Befehl aus x:

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

Wenn Sie Listeneigenschaften (z. B. Sortierung) nicht benötigen, verwenden Sie a Unterschied einstellenwie die anderen Antworten vermuten lassen:

list(set(x) - set(y))

Erlauben x - y Infix-Syntax, überschreiben __sub__ auf eine Klasse erben von list:

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

Verwendung:

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

Verwenden Unterschied einstellen

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

Oder Sie haben vielleicht nur x und y gesetzt, damit Sie keine Konvertierungen durchführen müssen.

Wenn Duplikate und Bestellartikel ein Problem sind:

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

Das ist eine “Satz-Subtraktions”-Operation. Verwenden Sie dazu die eingestellte Datenstruktur.

In Python 2.7:

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

Ausgang:

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

Für viele Anwendungsfälle lautet die gewünschte Antwort:

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

Dies ist eine Mischung aus der Antwort von Aaronasterling und der Antwort von Quantensoup.

Aaronasterlings Version tut es len(y) Artikelvergleiche für jedes Element in x, also dauert es quadratisch. Die Version von quantumSoup verwendet Sets, also führt es eine einzelne Set-Suche mit konstanter Zeit für jedes Element darin durch x– aber, weil es konvertiert beide x Und y in Mengen, verliert es die Reihenfolge Ihrer Elemente.

Nur durch Konvertieren y in eine Menge und Iteration x In der Reihenfolge erhalten Sie das Beste aus beiden Welten – lineare Zeit und Ordnungserhaltung.*

Dies hat jedoch immer noch ein Problem von der Version von quantumSoup: Es erfordert, dass Ihre Elemente hashbar sind. Das ist so ziemlich in die Natur von Mengen eingebaut.** Wenn Sie zB versuchen, eine Liste von Diktaten von einer anderen Liste von Diktaten zu subtrahieren, aber die zu subtrahierende Liste groß ist, was tun Sie dann?

Wenn Sie Ihre Werte so dekorieren können, dass sie hashbar sind, wird das Problem gelöst. Zum Beispiel mit einem flachen Wörterbuch, dessen Werte selbst hashbar sind:

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

Wenn Ihre Typen etwas komplizierter sind (z. B. wenn Sie es häufig mit JSON-kompatiblen Werten zu tun haben, die hashbar sind, oder mit Listen oder Diktaten, deren Werte rekursiv denselben Typ haben), können Sie diese Lösung dennoch verwenden. Aber einige Typen können einfach nicht in etwas Hashbares umgewandelt werden.

Wenn Ihre Artikel nicht hashbar sind und auch nicht erstellt werden können, aber vergleichbar sind, können Sie zumindest log-lineare Zeit (O(N*log M)das ist viel besser als die O(N*M) Zeit der Listenlösung, aber nicht so gut wie die O(N+M) Zeit der ausgehärteten Lösung) durch Sortieren und Verwenden 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)]

Wenn Ihre Artikel weder hashbar noch vergleichbar sind, bleiben Sie bei der quadratischen Lösung hängen.

_{* Beachten Sie, dass Sie dies auch tun könnten, indem Sie ein Paar verwenden OrderedSet Objekte, für die Sie Rezepte und Module von Drittanbietern finden können. Aber ich denke, das ist einfacher.}

_{** Der Grund, warum Set-Lookups konstant sind, ist, dass alles, was es tun muss, ist, den Wert zu hashen und zu sehen, ob es einen Eintrag für diesen Hash gibt. Wenn der Wert nicht gehasht werden kann, funktioniert dies nicht.}

Wenn die Listen doppelte Elemente zulassen, können Sie Counter from collections verwenden:

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

Wenn Sie die Reihenfolge der Elemente von x beibehalten müssen:

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

Die anderen Lösungen haben eines von wenigen Problemen:

1. Sie wahren keine Ordnung, oder
2. Sie entfernen keine genaue Anzahl von Elementen, z x = [1, 2, 2, 2] Und y = [2, 2] sie konvertieren y zu einem setund entfernen Sie entweder alle übereinstimmenden Elemente (wobei Sie [1] nur) oder eines von jedem einzigartigen Element entfernen (wobei [1, 2, 2]), wenn das richtige Verhalten das Entfernen wäre 2 zweimal, verlassen [1, 2]oder
3. Tun sie O(m * n) arbeiten, wo eine optimale Lösung ausreichen kann O(m + n) arbeiten

Alain war mit auf dem richtigen Weg Counter um Nr. 2 und Nr. 3 zu lösen, aber diese Lösung verliert die Ordnung. Die Lösung, die Ordnung bewahrt (Entfernen der ersten n Kopien von jedem Wert für n Wiederholungen in der list der zu entfernenden Werte) ist:

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.

Probieren Sie es online aus!

Um es zu entfernen zuletzt Kopien jedes Elements, ändern Sie einfach die for Schleife zu for val in reversed(x): und hinzufügen out.reverse() unmittelbar nach dem Verlassen der for Schleife.

Aufbau der Counter Ist O(n) bezüglich y‘s Länge, Iteration x Ist O(n) bezüglich x‘s Länge und Counter Mitgliedschaftstests und Mutationen sind O(1)während list.append ist amortisiert O(1) (ein gegebenes append kann sein O(n)aber für viele appends, die gesamten Big-O-Durchschnitte O(1) da immer weniger von ihnen eine Neuzuweisung erfordern), so ist die geleistete Gesamtarbeit O(m + n).

Sie können auch testen, ob Elemente darin enthalten sind y die nicht entfernt wurden x durch testen:

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