Python-Listensubtraktionsoperation

227

Ich möchte etwas Ähnliches tun:

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

Dies wird jedoch von Python-Listen nicht unterstützt. Wie geht das am besten?

Tagträumer
quelle
@ezdazuzena Dies ist keine Subtraktion. Dies ist der Unterschied zwischen zwei Listen. Ihr Teilen ist keine Veröffentlichung dieser Frage.
Celik
1
Was soll [2, 2] - [2] zurückgeben? []? [2]?
McKay
@McKay [2,2] - [2] sollte [2] zurückgeben. [2,2] - [1,2,2,3] sollte zurückkehren []
Robino
Bei dieser Frage geht es um Listensubtraktion, aber die akzeptierte Antwort ist näher an der eingestellten Subtraktion.
Robino
2
Was soll [2, 1, 2, 3, 2, 4, 2] - [2, 3, 2] zurückgeben und warum? Sollte es die 232 in der Mitte finden und 2142 zurückgeben? oder sollte es jedes Mal das erste finden und 1242 zurückgeben? Oder etwas anderes? Was ich sage ist, dass dies keine offensichtlichen Antworten sind und von der Notwendigkeit abhängen.
McKay

Antworten:

330

Verwenden Sie ein Listenverständnis:

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

Wenn Sie die -Infix-Syntax verwenden möchten , können Sie einfach Folgendes tun:

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

Sie können es dann wie folgt verwenden:

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

Wenn Sie jedoch keine Listeneigenschaften benötigen (z. B. Reihenfolge), verwenden Sie einfach Sets, wie in den anderen Antworten empfohlen.

aaronasterling
quelle
10
@admica, nicht listfür Variablennamen verwenden, da dies den listKonstruktor beschattet . Wenn Sie "Liste" verwenden, stellen Sie bitte einen Unterstrich voran. Außerdem haben Sie durch das *
Löschen des
19
Wenn Sie dies tun, erhalten [1,1,2,2] - [1,2]Sie eine leere Liste. [1,1,2,2] - [2]gibt [1,1]es also nicht wirklich Listensubtraktion, es ist eher wie "Liste aus Liste X ohne Elemente aus Menge Y " .
Alfred Zien
@ AlfredZien was er sagte
RetroCode
Die Listenverständnismethode ist (in meinem Beispiel) viel langsamer als die eingestellte Differenzmethode.
Redfiloux
1
@BarnabasSzabolcs: Das spart nichts, da es vor jedem Scheck yin einen konvertiert wird (was den Kosten der Originalarbeit ähnlich ist). Sie müssten entweder außerhalb des Listcomp, dann testen oder als ungeheuerlicher Hack, der verschachtelte Listcomps missbraucht, um den als Einzeiler zwischenzuspeichern . Eine etwas weniger hässliche Einzeilerlösung, die eine angemessene Leistung erbringt, wäre die Verwendung, da das Argument to nur einmal konstruiert wird. setyset = set(y)if item not in yset[item for yset in [set(y)] for item in x if item not in yset]ysetlist(itertools.filterfalse(set(y).__contains__, x))filterfalse
ShadowRanger
259

Verwenden Sie die eingestellte Differenz

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

Oder Sie müssen nur x und y setzen, damit Sie keine Konvertierungen vornehmen müssen.

quantumSoup
quelle
50
Dadurch geht jede Bestellung verloren. Das kann je nach Kontext von Bedeutung sein oder auch nicht.
Aaronasterling
63
Dadurch gehen auch mögliche Duplikate verloren, die möglicherweise gewartet werden müssen / müssen.
Opal
Ich bekommeTypeError: unhashable type: 'dict'
Havnar
Dies ist viel schneller in Fällen, in denen die verglichenen Listen groß sind
JqueryToAddNumbers
2
Wenn die Reihenfolge und das Duplizieren von Elementen in der Liste für den Kontext nicht wichtig sind, ist dies eine gute Antwort und gut lesbar.
Watt Iamsuri
37

Das ist eine "Set-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

Ausgabe:

>>> print x - y
set([0, 8, 2, 4, 6])
Santa
quelle
1
list (set ([1,2,3,4,5]) - set ([1,2,3])) = [4, 5], so dass jede Liste zuerst gesetzt und dann subtrahiert (oder in eine Richtung diff.) ) und zurück zur Liste.
Gseattle
2
Nicht gut, wenn Sie die ursprüngliche Artikelreihenfolge des x-Sets beibehalten möchten.
Zahran
34

Wenn doppelte und bestellte Artikel 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]
nguyên
quelle
2
Dies funktioniert, obwohl es O(m * n)Laufzeit ist (und ich erschrecke, wenn ein Listcomp Nebenwirkungen enthält); Sie können es verbessern, indemcollections.Counter Sie die O(m + n)Laufzeit abrufen.
ShadowRanger
Es fällt mir schwer, das zu verstehen. Kann mir jemand erklären?
Anushka
20

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 ein Hybrid zwischen aaronasterling Antwort und quantumSoup Antwort .

Die Version von aaronasterling führt Elementvergleiche len(y)für jedes Element in durch x, daher dauert es quadratisch. In der Version von quantumSoup werden Mengen verwendet, sodass für jedes Element in eine einzelne Mengen-Suche mit konstanter Zeit durchgeführt xwird. Da jedoch beide x und yin Mengen konvertiert werden, verliert sie die Reihenfolge Ihrer Elemente.

Wenn Sie nur yin eine Menge konvertieren und in der richtigen xReihenfolge iterieren , erhalten Sie das Beste aus beiden Welten - lineare Zeit und Ordnungserhaltung. *


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

Wenn Sie Ihre Werte so dekorieren können, dass sie hashbar sind, löst dies das Problem. 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. häufig mit JSON-kompatiblen Werten, die hashbar sind, oder Listen oder Diktaten, deren Werte rekursiv vom gleichen Typ sind), können Sie diese Lösung weiterhin verwenden. Einige Typen können jedoch nicht in etwas Hashbares konvertiert werden.


Wenn Ihre Elemente nicht hashbar sind und nicht erstellt werden können, aber vergleichbar sind, können Sie zumindest eine logarithmisch lineare Zeit erhalten ( O(N*log M)die viel besser ist als die O(N*M)Zeit der Listenlösung , aber nicht so gut wie) die O(N+M)Zeit der eingestellten Lösung) durch Sortieren und Verwenden von 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.


* Beachten Sie, dass Sie dies auch tun können, indem Sie ein Objektpaar verwenden OrderedSet, für das Sie Rezepte und Module von Drittanbietern finden. Aber ich denke das ist einfacher.

** Der Grund, warum Set-Lookups eine konstante Zeit sind, ist, dass sie nur den Wert hashen und prüfen müssen, ob es einen Eintrag für diesen Hash gibt. Wenn der Wert nicht gehasht werden kann, funktioniert dies nicht.

abarnert
quelle
7

Das Nachschlagen von Werten in Sätzen ist schneller als das Nachschlagen in Listen:

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

Ich glaube, das wird etwas besser skalieren als:

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

Beide behalten die Reihenfolge der Listen bei.

rudolfbyker
quelle
Wird es in jeder Schleife zwischengespeichert set(y)und nicht yin einen neuen Satz konvertiert ? Andernfalls benötigen Sie die Antwort von abarnert : ys = set(y); [i for i in x if i not in ys].
Jacktose
2
Einige grobe Tests legen nahe, dass dies if i not in set(y)25% länger dauert als if i not in y(wo yist eine Liste). Das Vorkonvertieren des Sets dauert 55% weniger Zeit. Getestet mit ziemlich kurzen xund y, aber Unterschiede sollten mit der Länge stärker werden, wenn überhaupt.
Jacktose
1
@Jacktose: Ja, diese Lösung macht mehr Arbeit, weil sie jedes Element von yfür jedes Element von iterieren und hashen muss x; Wenn der Gleichheitsvergleich im Vergleich zur Hash-Berechnung nicht wirklich teuer ist, verliert dies immer an Klarheit item not in y.
ShadowRanger
@ShadowRanger was Sinn macht. Wenn die Set-Konvertierung eine zuverlässig schnellere Möglichkeit wäre, diese Überprüfung durchzuführen, würde man meinen, der Compiler würde die Überprüfung einfach immer auf diese Weise durchführen.
Jacktose
5

Wenn die Listen doppelte Elemente zulassen, können Sie Zähler aus Sammlungen 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]) ]
Alain T.
quelle
Das ist gut, obwohl es die Bestellung verliert; Das zu beheben ist etwas komplizierter .
ShadowRanger
@ ShadowRanger, das ist es tatsächlich. aber nur ein bisschen.
Alain T.
Es macht mir nichts aus, ich werde nur bei Listcomps mit Caching und Nebenwirkungen schaudern (obwohl ich vermute, dass die Kombination der beiden die äußerlich sichtbaren Nebenwirkungen beseitigt?). :-)
ShadowRanger
Außerdem funktioniert dieser Code nicht wie geschrieben. Counter.subtractentfernt keine nullwertigen Elemente ( -und -=tut dies, aber nicht subtract), sodass Sie niemals aufhören würden, Elemente zu entfernen. Sie würden ersetzen möchten not v in cmit not c[v](die Renditen für nicht vorhandene Elemente Null, so dass Sie sicher die Rückkehr für „zeroiness“ über testen not).
ShadowRanger
@ ShadowRanger, guter Fang! Es wurde jetzt behoben.
Alain T.
3

Die anderen Lösungen haben eines der wenigen Probleme:

  1. Sie bewahren keine Ordnung oder
  2. Sie entfernen keine genaue Anzahl von Elementen, z. B. für x = [1, 2, 2, 2]und y = [2, 2]konvertieren yin a set, und entfernen entweder alle übereinstimmenden Elemente ( [1]nur verlassen) oder entfernen jedes einzelne eindeutige Element (verlassen [1, 2, 2]), wenn das richtige Verhalten darin besteht, 2zweimal zu entfernen . verlassen [1, 2], oder
  3. Sie O(m * n)arbeiten dort, wo eine optimale Lösung O(m + n)funktionieren kann

Alain war auf dem richtigen WegCounter , um # 2 und # 3 zu lösen, aber diese Lösung wird die Bestellung verlieren. Die Lösung, die die Reihenfolge beibehält (Entfernen der ersten nKopien jedes Werts für nWiederholungen in den listzu entfernenden Werten), lautet:

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 die letzten Kopien jedes Elements zu entfernen , ändern Sie einfach die forSchleife in for val in reversed(x):und fügen Sie sie out.reverse()unmittelbar nach dem Verlassen der forSchleife hinzu.

Die Konstruktion der Countersich O(n)in Bezug auf die y‚s Länge, Iterieren xist O(n)in Bezug auf die x‘ s Länge und CounterMitgliedschaft Tests und Mutation sind O(1), während list.appendabgeschrieben O(1)(a gegeben appendsein kann O(n), aber für viele appends, die Gesamt Big-O mittelt , O(1)da immer weniger von ihnen erfordern eine Neuzuweisung), so dass die Gesamtarbeit erledigt ist O(m + n).

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

remaining = +remaining  # Removes all keys with zero counts from Counter
if remaining:
    # remaining contained elements with non-zero counts
ShadowRanger
quelle
Hinweis: Dazu müssen die Werte hashbar sein, aber jede Lösung, für die keine hashbaren Objekte erforderlich sind, ist entweder nicht allgemein verwendbar (z. B. kann ints in ein Array mit fester Länge zählen) oder muss mehr als nur O(m + n)arbeiten (z. B. die nächstbeste große -O wäre, eine Sortierung listvon eindeutigen Wert / Anzahl-Paaren zu O(1) dicterstellen und O(log n)Suchvorgänge in binäre Suchvorgänge umzuwandeln . Sie benötigen eindeutige Werte mit ihrer Anzahl , nicht nur sortierte nicht eindeutige Werte, da Sie sonst O(n)Kosten für das Entfernen der Werte zahlen würden Elemente aus dem sortierten list).
ShadowRanger
2

Versuche dies.

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
>>>
user3435376
quelle
2

Ich denke, der einfachste Weg, dies zu erreichen, ist die Verwendung von 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]
Loochie
quelle
1

Die Antwort , die von gut aussieht @aaronasterling, ist es jedoch nicht mit der Standardoberfläche von Liste kompatibel: x = MyList(1, 2, 3, 4)vs x = MyList([1, 2, 3, 4]). Daher kann der folgende Code als Python-Listen-freundlicher verwendet werden:

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

Beispiel:

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

Ich denke das geht schneller:

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}
Eds_k
quelle
Dies ist keine Subtraktion. Tatsächlich ist dies der symmetrische Unterschied zwischen zwei Listen.
Parth Chauhan
Darüber hinaus funktioniert dies nur für hashbare Objekte in den Listen
zhukovgreen
-1

In diesem Beispiel werden zwei Listen abgezogen:

# 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))
Joao Nicolau
quelle
8
Vermeiden Sie dies, es ist O (N ^ 2)
Alexander - Reinstate Monica