Python List Subtrraction Werking

Ik wil iets dergelijks doen:

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

Maar dit wordt niet ondersteund door Python-lijsten
Wat is de beste manier om het te doen?

Antwoord 1, Autoriteit 100%

Gebruik een lijstbegrip:

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

Als u de -Infix Syntax wilt gebruiken, kunt u gewoon doen:

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

U kunt het dan gebruiken zoals:

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

Maar als u niet absoluut een lijstse eigenschappen nodig heeft (bijvoorbeeld bestellingen), gebruikt u alleen sets als de andere antwoorden aanbevelen.

Antwoord 2, Autoriteit 78%

Gebruik verschil instellen

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

of je hebt misschien x en y geserveerd, zodat je geen conversies hoeft te doen.

Antwoord 3, Autoriteit 10%

Dat is een “SET-subtractie” -bewerking. Gebruik daarvoor de ingestelde gegevensstructuur.

in Python 2.7:

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

Uitvoer:

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

Antwoord 4, autoriteit 10%

als dubbele items en het bestellen van items een probleem zijn:

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

Antwoord 5, autoriteit 6%

Voor veel gevallen is het gewenste antwoord:

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

Dit is een hybride tussen het antwoord van Aaronasterlingen antwoord van QuantumSoup.

De versie van

aaronasterling doet len(y)itemvergelijkingen voor elk element in x, dus het kost kwadratische tijd. De versie van quantumSoup gebruikt sets, dus het doet een enkele constante-tijd set-zoekopdracht voor elk element in x, maar omdat het beidexen yin sets, het verliest de volgorde van je elementen.

Door alleen yom te zetten in een set en xin volgorde te herhalen, krijg je het beste van twee werelden: lineaire tijd en orderbehoud.*

Dit heeft echter nog steeds een probleem met de versie van quantumSoup: het vereist dat je elementen hashbaar zijn. Dat zit zo’n beetje in de aard van sets.** Als je bijvoorbeeld een lijst met dictaten probeert af te trekken van een andere lijst met dictaten, maar de lijst die moet worden afgetrokken is groot, wat doe je dan?

Als u uw waarden op de een of andere manier kunt versieren die ze hashable zijn, lost het probleem op. Bijvoorbeeld, met een vlak woordenboek waarvan de waarden zelf hashable zijn:

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

Als uw typen een beetje ingewikkelder zijn (bijvoorbeeld u te maken met JSON-compatibele waarden, die hashable of lijsten of dicts zijn waarvan de waarden recursief hetzelfde type zijn), kunt u deze oplossing nog steeds gebruiken. Maar sommige typen kunnen gewoon niet worden omgezet in iets hashable.

Als uw items niet zijn, en niet kunnen worden gemaakt, hashable, maar ze zijn vergelijkbaar, kunt u op zijn minst log-lineaire tijd krijgen (O(N*log M), is een stuk beter dan de O(N*M)tijd van de lijstoplossing, maar niet zo goed als de O(N+M)tijd van de set-oplossing) door het sorteren en gebruiken van 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)]

Als uw items geen hashable noch vergelijkbaar zijn, dan zit u vast met de kwadratische oplossing.

_{* Merk op dat u dit ook kunt doen door een paar OrderedSetObjects te gebruiken, waarvoor u recepten en modules van derden kunt vinden. Maar ik denk dat dit eenvoudiger is.}

_{** De opzoekoplagen instellen zijn constant tijd, is dat alles wat het hoeft te doen is de waarde heeft en kijk of er een invoer is voor die hash. Als het de waarde niet kan haten, werkt dit niet.}

Antwoord 6, Autoriteit 3%

Ik denk dat de eenvoudigste manier om dit te bereiken is door Set () te gebruiken.

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

Antwoord 7, autoriteit 3%

Als de lijsten dubbele elementen toestaan, kunt u Teller uit verzamelingen gebruiken:

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

Als u de volgorde van elementen van x wilt behouden:

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

Antwoord 8, autoriteit 2%

Het opzoeken van waarden in sets gaat sneller dan het opzoeken in lijsten:

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

Ik denk dat dit iets beter zal schalen dan:

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

Beide behouden de volgorde van de lijsten.

Antwoord 9, autoriteit 2%

De andere oplossingen hebben een van de weinige problemen:

1. Ze bewaren de orde niet, of
2. Ze verwijderen geen precieze telling van elementen, b.v. voor x = [1, 2, 2, 2]en y = [2, 2]converteren ze ynaar een set, en verwijder alle overeenkomende elementen (waarbij alleen [1]overblijft) of verwijder één van elk uniek element (waarbij [1, 2, 2]achterblijft), wanneer het juiste gedrag zou zijn om 2twee keer te verwijderen, waarbij [1, 2]of

achterblijft

3. Ze doen O(m * n)werk, waar een optimale oplossing O(m + n)werk kan doen

Alain was op de goede weg met Counterom #2 en #3 op te lossen, maar die oplossing zal de bestelling verliezen. De oplossing die de volgorde behoudt (de eerste n-kopieën van elke waarde verwijderen voor nherhalingen in de listmet te verwijderen waarden) is:

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.

Probeer het online!

Om de laatstekopieën van elk element te laten verwijderen, verandert u de for-lus in for val in reversed(x):en voeg out.reverse()toe onmiddellijk na het verlaten van de for-lus.

Het bouwen van de Counteris O(n)in termen van de lengte van y, het herhalen van xis O(n)in termen van de lengte van x, en Counterlidmaatschapstest en mutatie zijn O(1), terwijl list.appendwordt afgeschreven O(1)(een gegeven appendkan O(n)zijn , maar voor veel append‘s is de algehele big-O gemiddeld O(1)aangezien steeds minder ervan een hertoewijzing vereisen), dus het totale werk dat gedaan wordt is O(m + n).

Je kunt ook testen om te bepalen of er elementen in ywaren die niet zijn verwijderd uit xdoor te testen:

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

Antwoord 10

Probeer dit.

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

Antwoord 11

Het antwoord van @aaronasterling ziet er goed uit, maar is niet compatibel met de standaardinterface van list: x = MyList(1, 2, 3, 4)vs x = MyList([1, 2, 3, 4]). De onderstaande code kan dus worden gebruikt als een meer python-lijstvriendelijke:

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

Voorbeeld:

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

Antwoord 12

Dit voorbeeld trekt twee lijsten af:

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