Alle Elemente, die in einer Liste vorkommen, aus einer anderen entfernen

Question

Nehmen wir an, ich habe zwei Listen, l1 y l2 . Ich möchte auftreten l1 - l2 die alle Elemente von l1 nicht in l2 .

Ich kann mir eine naive Schleifenlösung vorstellen, aber das wäre wirklich ineffizient. Was ist ein pythonischer und effizienter Weg, dies zu tun?

Ein Beispiel: Wenn ich l1 = [1,2,6,8] and l2 = [2,3,5,8] , l1 - l2 sollte zurückkehren [1,6]

Answer 1

Python hat eine Sprachfunktion namens Auflistung von Zusammenfassungen die perfekt geeignet ist, um diese Art von Dingen extrem einfach zu machen. Die folgende Anweisung tut genau das, was Sie wollen, und speichert das Ergebnis in l3 :

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

l3 wird enthalten [1, 6] .

Answer 2

Eine Möglichkeit ist die Verwendung von Sets:

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

Beachten Sie jedoch, dass Sets die Reihenfolge der Elemente nicht beibehalten und dass doppelte Elemente entfernt werden. Die Elemente müssen außerdem hashfähig sein. Wenn diese Einschränkungen tolerierbar sind, ist dies oft die einfachste und leistungsfähigste Option.

Answer 3

Performance-Vergleiche

Vergleicht man die Leistung aller hier genannten Antworten auf Python 3.9.1 y Python 2.7.16 .

Python 3.9.1

Die Antworten werden in der Reihenfolge ihrer Erfüllung aufgeführt:

1. Arkku's set Differenz durch Subtraktion Operation "-" - (91,3 ns pro Schleife)

   mquadri$ python3 -m timeit -s "l1 = set([1,2,6,8]); l2 = set([2,3,5,8]);" "l1 - l2"
   5000000 loops, best of 5: 91.3 nsec per loop

2. Moinuddin Quadri's mit set().difference() - (133 ns pro Schleife)

   mquadri$ python3 -m timeit -s "l1 = set([1,2,6,8]); l2 = set([2,3,5,8]);" "l1.difference(l2)"
   2000000 loops, best of 5: 133 nsec per loop

3. Moinuddin Quadri's Listenverständnis mit set basiertes Nachschlagen - (366 ns pro Schleife)

    mquadri$ python3 -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 5: 366 nsec per loop

4. Donut's Listenverständnis auf einfacher Liste - (489 ns pro Schleife)

    mquadri$ python3 -m timeit -s "l1 = [1,2,6,8]; l2 = [2,3,5,8];" "[x for x in l1 if x not in l2]"
    500000 loops, best of 5: 489 nsec per loop

5. Daniel Pryden's Generatorausdruck mit set basiertes Nachschlagen und Typisierung auf list - (583 ns pro Schleife) : Explizite Typisierung auf Liste, um das endgültige Objekt zu erhalten als list wie von OP gewünscht. Wenn Generatorausdruck wird ersetzt durch Listenverstehen wird es genauso wie Moinuddin Quadri's Listenverständnis mit set basierte Suche.

    mquadri$ mquadri$ python3 -m timeit -s "l1 = [1,2,6,8]; l2 = set([2,3,5,8]);" "list(x for x in l1 if x not in l2)"
    500000 loops, best of 5: 583 nsec per loop

6. Moinuddin Quadri's mit filter() und explizite Typisierung auf list (muss explizit typisiert werden, wie in Python 3.x, es gibt einen Iterator zurück) - (681 ns pro Schleife)

    mquadri$ python3 -m timeit -s "l1 = [1,2,6,8]; l2 = set([2,3,5,8]);" "list(filter(lambda x: x not in l2, l1))"
    500000 loops, best of 5: 681 nsec per loop

7. Akshay Hazari's durch Kombination von functools.reduce + filter -(3,36 usec pro Schleife) : Explizite Typenzuweisung an list wie von Python 3.x begann es zurückkehren Iterator. Außerdem müssen wir importieren functools zu verwenden reduce in Python 3.x

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

Python 2.7.16

Die Antworten werden in der Reihenfolge ihrer Erfüllung aufgeführt:

1. Arkku's set Differenz durch Subtraktion Operation "-" - (0,0783 usec pro Schleife)

   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.0783 usec per loop

2. Moinuddin Quadri's mit set().difference() - (0,117 usec pro Schleife)

   mquadri$ mquadri$ python -m timeit -s "l1 = set([1,2,6,8]); l2 = set([2,3,5,8]);" "l1.difference(l2)"
   10000000 loops, best of 3: 0.117 usec per loop

3. Moinuddin Quadri's Listenverständnis mit set basiertes Nachschlagen - (0,246 usec pro Schleife)

    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.246 usec per loop

4. Donut's Listenverständnis auf einfacher Liste - (0,372 usec pro Schleife)

    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.372 usec per loop

5. Moinuddin Quadri's mit filter() - (0,593 usec pro Schleife)

    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.593 usec per loop

6. Daniel Pryden's Generatorausdruck mit set basiertes Nachschlagen und Typisierung auf list - (0,964 pro Schleife) : Explizite Typisierung auf Liste, um das endgültige Objekt zu erhalten als list wie von OP gewünscht. Wenn Generatorausdruck wird ersetzt durch Listenverstehen wird es genauso wie Moinuddin Quadri's Listenverständnis mit set basierte Suche.

    mquadri$ python -m timeit -s "l1 = [1,2,6,8]; l2 = set([2,3,5,8]);" "list(x for x in l1 if x not in l2)"
    1000000 loops, best of 3: 0.964 usec per loop

7. Akshay Hazari's durch Kombination von functools.reduce + filter -(2,78 usec pro Schleife)

    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: 2.78 usec per loop

Answer 4

Wenn man die Antwort von Donut und die anderen Antworten hier weiter ausführt, kann man sogar noch bessere Ergebnisse erzielen, indem man ein Generator-Verständnis anstelle eines Listen-Verständnisses verwendet, und indem man ein set Datenstruktur (da die in Operator ist O(n) für eine Liste, aber O(1) für eine Menge).

Hier ist also eine Funktion, die für Sie geeignet wäre:

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

Das Ergebnis wird eine Iterable sein, die die gefilterte Liste nach und nach abruft. Wenn Sie ein echtes Listenobjekt benötigen (z.B. wenn Sie eine len() auf das Ergebnis), dann können Sie leicht eine Liste wie folgt erstellen:

filtered_list = list(filter_list(full_list, excludes))

Answer 5

Verwenden Sie den Python-Satztyp. Das wäre das Pythonischste :)

Da es sich um eine systemeigene Methode handelt, sollte sie auch die am besten optimierte Methode sein.

Siehe:

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

http://docs.python.org/library/sets.htm (für älteres 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