Wie entferne ich Duplikate aus einer Liste, während ich die Reihenfolge beibehalte?

Wie entferne ich Duplikate aus einer Liste, während ich die Reihenfolge beibehalte? Die Verwendung eines Sets zum Entfernen von Duplikaten zerstört die ursprüngliche Reihenfolge. Gibt es ein eingebautes oder ein pythonisches Idiom?

Verwandte Frage: Was ist in Python der schnellste Algorithmus zum Entfernen von Duplikaten aus einer Liste, sodass alle Elemente eindeutig sind? unter Wahrung der Ordnung?

Die beste Lösung variiert je nach Python-Version und Umgebungseinschränkungen:

Python 3.7+ (und die meisten Interpreter, die 3.6 unterstützen, als Implementierungsdetail):

Zuerst in PyPy 2.5.0 eingeführt und in CPython 3.6 als Implementierungsdetail übernommen, bevor es in Python 3.7, plain, zu einer Sprachgarantie gemacht wurde dict ist einfügungsgeordnet und sogar effizienter als die (ebenfalls in C implementiert ab CPython 3.5) collections.OrderedDict. Die bei weitem schnellste Lösung ist also auch die einfachste:

>>> items = [1, 2, 0, 1, 3, 2]
>>> list(dict.fromkeys(items))  # Or [*dict.fromkeys(items)] if you prefer
[1, 2, 0, 3]

Wie list(set(items)) Dies verschiebt die gesamte Arbeit auf die C-Schicht (auf CPython), aber seitdem dicts sind nach Einfügung geordnet, dict.fromkeys verliert nicht die Bestellung. Es ist langsamer als list(set(items)) (dauert normalerweise 50-100 % länger), aber viel schneller als jede andere ordnungserhaltende Lösung (dauert etwa die Hälfte der Zeit von Hacks mit Verwendung von sets in einem listcomp).

Wichtiger Hinweis: Das unique_everseen Lösung aus more_itertools (siehe unten) hat einige einzigartige Vorteile in Bezug auf Faulheit und Unterstützung für nicht hashfähige Eingabeelemente; Wenn Sie diese Funktionen benötigen, ist es das nur Lösung, die funktionieren wird.

Python 3.5 (und alle älteren Versionen, wenn die Leistung es nicht ist kritisch)

Wie Raymond betonte, in CPython 3.5 wo OrderedDict in C implementiert ist, sind hässliche Listenverständnis-Hacks langsamer als OrderedDict.fromkeys (es sei denn, Sie brauchen die Liste wirklich am Ende – und auch dann nur, wenn die Eingabe sehr kurz ist). Sowohl hinsichtlich der Leistung als auch der Lesbarkeit ist die beste Lösung für CPython 3.5 die OrderedDict Äquivalent der 3.6+ Verwendung von plain dict:

>>> from collections import OrderedDict
>>> items = [1, 2, 0, 1, 3, 2]
>>> list(OrderedDict.fromkeys(items))
[1, 2, 0, 3]

Auf CPython 3.4 und früheren Versionen ist dies langsamer als bei einigen anderen Lösungen. Wenn also die Profilerstellung zeigt, dass Sie eine bessere Lösung benötigen, lesen Sie weiter.

Python 3.4 und früher, wenn die Leistung kritisch ist und Module von Drittanbietern akzeptabel sind

Wie @abarnert feststellt, die more_itertools Bibliothek (pip install more_itertools) enthält ein unique_everseen Funktion, die gebaut wurde, um dieses Problem ohne irgendwelche zu lösen unlesbar (not seen.add) Mutationen im Listenverständnis. Dies ist auch die schnellste Lösung:

>>> from more_itertools import unique_everseen
>>> items = [1, 2, 0, 1, 3, 2]
>>> list(unique_everseen(items))
[1, 2, 0, 3]

Nur ein einfacher Bibliotheksimport und keine Hacks.

Das Modul passt das itertools-Rezept an unique_everseen das sieht aus wie:

def unique_everseen(iterable, key=None):
    "List unique elements, preserving order. Remember all elements ever seen."
    # unique_everseen('AAAABBBCCDAABBB') --> A B C D
    # unique_everseen('ABBCcAD', str.lower) --> A B C D
    seen = set()
    seen_add = seen.add
    if key is None:
        for element in filterfalse(seen.__contains__, iterable):
            seen_add(element)
            yield element
    else:
        for element in iterable:
            k = key(element)
            if k not in seen:
                seen_add(k)
                yield element

aber anders als die itertools Rezept unterstützt es nicht hashfähige Elemente (auf Kosten der Leistung; wenn alle Elemente in iterable nicht hashfähig sind, wird der Algorithmus O(n²)vs. O(n) wenn sie alle hashbar sind).

Wichtiger Hinweis: Im Gegensatz zu allen anderen Lösungen hier, unique_everseen kann faul verwendet werden; die maximale Speicherauslastung wird dieselbe sein (schließlich die zugrunde liegende set auf die gleiche Größe wächst), aber wenn Sie dies nicht tun listWenn Sie das Ergebnis verifizieren, iterieren Sie es einfach, Sie können eindeutige Elemente verarbeiten, sobald sie gefunden werden, anstatt zu warten, bis die gesamte Eingabe dedupliziert wurde, bevor Sie das erste eindeutige Element verarbeiten.

Python 3.4 und früher, wenn die Leistung kritisch ist und Module von Drittanbietern sind nicht verfügbar

Sie haben zwei Möglichkeiten:

1. Kopieren und einfügen das unique_everseen Rezept zu Ihrem Code und verwenden Sie es pro die more_itertools Beispiel oben

2. Verwenden Sie hässliche Hacks, um einem einzelnen listcomp sowohl das Überprüfen als auch das Aktualisieren von a zu ermöglichen set um zu verfolgen, was gesehen wurde:

   seen = set()
   [x for x in seq if x not in seen and not seen.add(x)]
   

   auf Kosten des Vertrauens auf die hässlicher Hack:

    not seen.add(x)
   

   was darauf beruht, dass set.add ist eine In-Place-Methode, die immer zurückkehrt None Also not None wertet zu True.

Beachten Sie, dass alle der obigen Lösungen sind O(n) (Spart den Anruf unique_everseen auf einem Iterable von nicht hashbaren Elementen, das heißt O(n²)während die anderen sofort mit a fehlschlagen würden TypeError), sodass alle Lösungen leistungsfähig genug sind, wenn sie nicht der heißeste Codepfad sind. Welche Sie verwenden sollten, hängt davon ab, auf welche Versionen der Sprachspezifikation/Interpreter/Drittanbieter-Module Sie sich verlassen können, ob die Leistung kritisch ist oder nicht (nehmen Sie nicht an, dass dies normalerweise nicht der Fall ist) und vor allem die Lesbarkeit (Denn wenn die Person, die diesen Code pflegt, später in einer mörderischen Stimmung endet, hat sich Ihre clevere Mikrooptimierung wahrscheinlich nicht gelohnt).

Um kein totes Pferd zu treten (diese Frage ist sehr alt und hat bereits viele gute Antworten), aber hier ist eine Lösung mit Pandas, die unter vielen Umständen ziemlich schnell und kinderleicht zu verwenden ist.

import pandas as pd

my_list = [0, 1, 2, 3, 4, 1, 2, 3, 5]

>>> pd.Series(my_list).drop_duplicates().tolist()
# Output:
# [0, 1, 2, 3, 4, 5]

Im Python 3.7 und darüber sind Wörterbücher garantiert um sich an ihre Schlüsseleinfügungsreihenfolge zu erinnern. Die Antwort auf diese Frage fasst den aktuellen Stand der Dinge zusammen.

Das OrderedDict Lösung wird damit obsolet und wir können ohne irgendwelche Import-Anweisungen einfach ausgeben:

>>> lst = [1, 2, 1, 3, 3, 2, 4]
>>> list(dict.fromkeys(lst))
[1, 2, 3, 4]

sequence = ['1', '2', '3', '3', '6', '4', '5', '6']
unique = []
[unique.append(item) for item in sequence if item not in unique]

einzigartig → ['1', '2', '3', '6', '4', '5']