Duplikate in Listen entfernen

995

Ich muss so ziemlich ein Programm schreiben, um zu überprüfen, ob eine Liste Duplikate enthält, und wenn dies der Fall ist, werden diese entfernt und eine neue Liste mit den Elementen zurückgegeben, die nicht dupliziert / entfernt wurden. Das habe ich, aber um ehrlich zu sein, weiß ich nicht, was ich tun soll.

def remove_duplicates():
    t = ['a', 'b', 'c', 'd']
    t2 = ['a', 'c', 'd']
    for t in t2:
        t.append(t.remove())
    return t
Neemaximo
quelle
22
Ihre Beschreibung besagt, dass Sie "eine Liste" auf Duplikate prüfen, Ihr Code jedoch zwei Listen.
Brendan Long
* using set: list (set (ELEMENTS_LIST)) * using dictionary: list (dict.fromkeys (ELEMENTS_LIST))
Shayan Amani

Antworten:

1641

Der übliche Ansatz, um eine eindeutige Sammlung von Elementen zu erhalten, ist die Verwendung von a set. Sets sind ungeordnete Sammlungen unterschiedlicher Objekte. Um einen Satz aus einem beliebigen Iterable zu erstellen, können Sie ihn einfach an die integrierte set()Funktion übergeben. Wenn Sie später wieder eine echte Liste benötigen, können Sie den Satz ebenfalls an die list()Funktion übergeben.

Das folgende Beispiel sollte alles abdecken, was Sie versuchen:

>>> t = [1, 2, 3, 1, 2, 5, 6, 7, 8]
>>> t
[1, 2, 3, 1, 2, 5, 6, 7, 8]
>>> list(set(t))
[1, 2, 3, 5, 6, 7, 8]
>>> s = [1, 2, 3]
>>> list(set(t) - set(s))
[8, 5, 6, 7]

Wie Sie dem Beispielergebnis entnehmen können, wird die ursprüngliche Reihenfolge nicht beibehalten . Wie oben erwähnt, sind Sets selbst ungeordnete Sammlungen, sodass die Reihenfolge verloren geht. Beim Konvertieren eines Satzes in eine Liste wird eine beliebige Reihenfolge erstellt.

Ordnung aufrechterhalten

Wenn Ihnen die Reihenfolge wichtig ist, müssen Sie einen anderen Mechanismus verwenden. Eine sehr häufige Lösung hierfür besteht darin OrderedDict, die Reihenfolge der Schlüssel beim Einfügen beizubehalten:

>>> from collections import OrderedDict
>>> list(OrderedDict.fromkeys(t))
[1, 2, 3, 5, 6, 7, 8]

Ab Python 3.7 behält das integrierte Wörterbuch garantiert auch die Einfügereihenfolge bei. Sie können diese also auch direkt verwenden, wenn Sie Python 3.7 oder höher (oder CPython 3.6) verwenden:

>>> list(dict.fromkeys(t))
[1, 2, 3, 5, 6, 7, 8]

Beachten Sie, dass dies möglicherweise einen gewissen Aufwand bedeutet, zuerst ein Wörterbuch und dann eine Liste daraus zu erstellen. Wenn Sie die Reihenfolge nicht wirklich beibehalten müssen, ist es oft besser, ein Set zu verwenden, insbesondere weil Sie dadurch viel mehr Operationen ausführen können. In dieser Frage finden Sie weitere Details und alternative Möglichkeiten, um die Reihenfolge beim Entfernen von Duplikaten beizubehalten.


Beachten Sie schließlich, dass sowohl die setals auch die OrderedDict/ dict-Lösungen erfordern, dass Ihre Artikel hashbar sind . Dies bedeutet normalerweise, dass sie unveränderlich sein müssen. Wenn Sie sich mit Elementen befassen müssen, die nicht hashbar sind (z. B. Listenobjekte), müssen Sie einen langsamen Ansatz verwenden, bei dem Sie grundsätzlich jedes Element mit jedem anderen Element in einer verschachtelten Schleife vergleichen müssen.

Sack
quelle
4
Dies funktioniert nicht für nicht zerlegbare Listenelemente (z. B. eine Liste von Listen)
KNejad
3
@KNejad Das steht im letzten Absatz.
Poke
Oh oops. Hätte das Ganze lesen sollen. Am Ende habe ich Tupel anstelle von Listen verwendet, damit dieser Ansatz immer noch funktioniert.
KNejad
Fügen Sie dies zum Beispiel hinzu, t = [3, 2, 1, 1, 2, 5, 6, 7, 8], zeigt den Unterschied deutlich!
Sailfish009
"... Aufwand für die Erstellung eines Wörterbuchs zuerst ... Wenn Sie die Reihenfolge nicht beibehalten müssen, ist es besser, ein Set zu verwenden." - Ich habe dies profiliert, weil ich neugierig war, ob es tatsächlich wahr ist. Meine Timings zeigen, dass der Satz tatsächlich etwas schneller ist: 1,12 µs pro Schleife (Satz) gegenüber 1,53 µs pro Schleife (Diktat) über 1 Million Schleifen mit einer absoluten Zeitdifferenz von etwa 4 Sekunden über 1 Million Iterationen. Wenn Sie dies also in einer engen inneren Schleife tun, ist es Ihnen vielleicht wichtig, sonst wahrscheinlich nicht.
Millerdev
414

In Python 2.7 ist die neue Methode zum Entfernen von Duplikaten aus einer iterierbaren Datei, während die ursprüngliche Reihenfolge beibehalten wird:

>>> from collections import OrderedDict
>>> list(OrderedDict.fromkeys('abracadabra'))
['a', 'b', 'r', 'c', 'd']

In Python 3.5 verfügt OrderedDict über eine C-Implementierung. Mein Timing zeigt, dass dies jetzt sowohl der schnellste als auch der kürzeste der verschiedenen Ansätze für Python 3.5 ist.

In Python 3.6 wurde das reguläre Diktat sowohl geordnet als auch kompakt. (Diese Funktion gilt für CPython und PyPy, ist jedoch in anderen Implementierungen möglicherweise nicht vorhanden.) Das gibt uns eine neue schnellste Möglichkeit zum Dedupieren unter Beibehaltung der Ordnung:

>>> list(dict.fromkeys('abracadabra'))
['a', 'b', 'r', 'c', 'd']

In Python 3.7 wird garantiert, dass das reguläre Diktat in allen Implementierungen geordnet ist. Die kürzeste und schnellste Lösung ist also:

>>> list(dict.fromkeys('abracadabra'))
['a', 'b', 'r', 'c', 'd']
Raymond Hettinger
quelle
10
Ich denke, dies ist der einzige Weg, um die Artikel in Ordnung zu halten.
Herberth Amaral
19
@HerberthAmaral: Das ist alles andere als wahr. Siehe Wie entferne ich Duplikate aus einer Liste in Python, während die Reihenfolge erhalten
Martijn Pieters
5
@MartijnPieters Korrektur: Ich denke, dies ist die einzige einfache Möglichkeit, Artikel in Ordnung zu halten.
Herberth Amaral
12
Auch dafür muss der Inhalt der ursprünglichen Liste hashbar sein
Davide
Wie bei @Davide erwähnt, muss die ursprüngliche Liste hashbar sein. Dies bedeutet, dass dies für eine Liste von Wörterbüchern nicht funktioniert. TypeError: unhashable type: 'dictlist'
CraZ
187

Es ist ein Einzeiler: list(set(source_list))wird den Trick machen.

A setist etwas, das unmöglich Duplikate haben kann.

Update: Ein auftragserhaltender Ansatz besteht aus zwei Zeilen:

from collections import OrderedDict
OrderedDict((x, True) for x in source_list).keys()

Hier verwenden wir die Tatsache, dass OrderedDictdie Einfügereihenfolge von Schlüsseln gespeichert und nicht geändert wird, wenn ein Wert an einem bestimmten Schlüssel aktualisiert wird. Wir fügen Trueals Werte ein, aber wir können alles einfügen, Werte werden einfach nicht verwendet. (Funktioniert setsehr ähnlich wie a dictmit ignorierten Werten.)

9000
quelle
5
Dies funktioniert nur, wenn source_listes hashbar ist.
Adrian Keister
@AdrianKeister: Das ist wahr. Es gibt Objekte mit angemessener Gleichheitssemantik, die jedoch nicht hashbar sind, z. B. Listen. OTOH Wenn wir keine Verknüpfung wie eine hastable haben können, erhalten wir einen quadratischen Algorithmus, bei dem jedes Element mit allen derzeit bekannten eindeutigen Elementen verglichen wird. Dies kann für kurze Eingaben völlig in Ordnung sein, insbesondere bei vielen Duplikaten.
9000
Genau. Ich denke, Ihre Antwort wäre von höherer Qualität, wenn Sie diesen sehr häufigen Anwendungsfall berücksichtigen würden.
Adrian Keister
94
>>> t = [1, 2, 3, 1, 2, 5, 6, 7, 8]
>>> t
[1, 2, 3, 1, 2, 5, 6, 7, 8]
>>> s = []
>>> for i in t:
       if i not in s:
          s.append(i)
>>> s
[1, 2, 3, 5, 6, 7, 8]
Neeraj
quelle
33
Beachten Sie, dass diese Methode in O (n ^ 2) -Zeit funktioniert und daher bei großen Listen sehr langsam ist.
Dotancohen
@Chris_Rands: Nicht sicher, ob frozensetmit nicht hashbaren Inhalten funktioniert. Ich erhalte immer noch den nicht hashbaren Fehler bei der Verwendung frozenset.
Adrian Keister
85

Wenn Sie sich nicht für die Bestellung interessieren, gehen Sie einfach so vor:

def remove_duplicates(l):
    return list(set(l))

A sethat garantiert keine Duplikate.

Brendan Long
quelle
3
Funktioniert nur, wenn les hashbar ist.
Adrian Keister
41

Erstellen einer neuen Liste unter Beibehaltung der Reihenfolge der ersten Elemente von Duplikaten in L

newlist=[ii for n,ii in enumerate(L) if ii not in L[:n]]

zum Beispiel wird if L=[1, 2, 2, 3, 4, 2, 4, 3, 5]dann newlistsein[1,2,3,4,5]

Dadurch wird überprüft, ob jedes neue Element zuvor nicht in der Liste angezeigt wurde, bevor es hinzugefügt wird. Auch braucht es keine Importe.

Richard Fredlund
quelle
3
Dies hat eine zeitliche Komplexität von O (n ^ 2) . Die Antworten mit setund haben OrderedDictmöglicherweise eine geringere Komplexität der amortisierten Zeit.
Blubberdiblub
Ich habe in meinem Code diese Lösung verwendet und großartig gearbeitet, aber ich denke, es ist zeitaufwändig
Gerasimos Ragavanis
@blubberdiblub Können Sie erklären, welcher Code-effizientere Mechanismus in set und OrderedDict vorhanden ist, der sie weniger zeitaufwendig machen könnte? (ohne den Aufwand für das Laden)
ilias iliadis
@iliasiliadis Die üblichen Implementierungen von Set und Dikt verwenden Hashes oder (irgendeine Form von ausgeglichenen) Bäumen. Sie müssen in Betracht ziehen, die Menge oder das Diktat zu erstellen und darin zu suchen (mehrmals), aber ihre amortisierte Komplexität ist normalerweise immer noch niedriger als O (n ^ 2) . "Amortisiert" bedeutet in einfachen Worten durchschnittlich (sie können Worst-Cases mit höherer Komplexität als der durchschnittliche Fall haben). Dies ist nur relevant, wenn Sie eine große Anzahl von Elementen haben.
Blubberdiblub
25

Ein Kollege hat mir heute die akzeptierte Antwort als Teil seines Codes zur Codereview geschickt. Obwohl ich die Eleganz der fraglichen Antwort sicherlich bewundere, bin ich mit der Aufführung nicht zufrieden. Ich habe diese Lösung ausprobiert (ich verwende set , um die Suchzeit zu verkürzen).

def ordered_set(in_list):
    out_list = []
    added = set()
    for val in in_list:
        if not val in added:
            out_list.append(val)
            added.add(val)
    return out_list

Um die Effizienz zu vergleichen, habe ich eine Zufallsstichprobe von 100 Ganzzahlen verwendet - 62 waren eindeutig

from random import randint
x = [randint(0,100) for _ in xrange(100)]

In [131]: len(set(x))
Out[131]: 62

Hier sind die Ergebnisse der Messungen

In [129]: %timeit list(OrderedDict.fromkeys(x))
10000 loops, best of 3: 86.4 us per loop

In [130]: %timeit ordered_set(x)
100000 loops, best of 3: 15.1 us per loop

Was passiert, wenn set aus der Lösung entfernt wird?

def ordered_set(inlist):
    out_list = []
    for val in inlist:
        if not val in out_list:
            out_list.append(val)
    return out_list

Das Ergebnis ist nicht so schlecht wie beim OrderedDict , aber immer noch mehr als dreimal so hoch wie bei der ursprünglichen Lösung

In [136]: %timeit ordered_set(x)
10000 loops, best of 3: 52.6 us per loop
Vulkan
quelle
Nizza mit Set Quick Lookup, um den Loop-Vergleich zu beschleunigen. Wenn die Reihenfolge keine Rolle spielt, ist die Liste (Set (x)) immer noch 6x schneller als diese
Joop
@Joop, das war meine erste Frage an meinen Kollegen - die Reihenfolge ist wichtig; Andernfalls wäre es ein triviales Problem gewesen
Vulkan
optimierte Version des bestellten Sets für alle Interessierten : def unique(iterable):; seen = set();; seen_add = seen.add;; return [item for item in iterable if not item in seen and not seen_add(item)]
DrD
25

Es gibt auch Lösungen mit Pandas und Numpy. Beide geben ein numpy-Array zurück, sodass Sie die Funktion verwenden müssen, .tolist()wenn Sie eine Liste wünschen.

t=['a','a','b','b','b','c','c','c']
t2= ['c','c','b','b','b','a','a','a']

Pandas Lösung

Verwenden der Pandas-Funktion unique():

import pandas as pd
pd.unique(t).tolist()
>>>['a','b','c']
pd.unique(t2).tolist()
>>>['c','b','a']

Numpy Lösung

Verwenden der Numpy-Funktion unique().

import numpy as np
np.unique(t).tolist()
>>>['a','b','c']
np.unique(t2).tolist()
>>>['a','b','c']

Beachten Sie, dass numpy.unique () auch die Werte sortiert . Die Liste t2wird also sortiert zurückgegeben. Wenn Sie die Reihenfolge beibehalten möchten, verwenden Sie wie in dieser Antwort :

_, idx = np.unique(t2, return_index=True)
t2[np.sort(idx)].tolist()
>>>['c','b','a']

Die Lösung ist im Vergleich zu den anderen nicht so elegant. Im Vergleich zu pandas.unique () können Sie mit numpy.unique () auch überprüfen, ob verschachtelte Arrays entlang einer ausgewählten Achse eindeutig sind.

GM
quelle
Dadurch wird die Liste in ein numpy-Array konvertiert, was ein Chaos ist und für Zeichenfolgen nicht funktioniert.
user227666
1
@ user227666 danke für Ihre Bewertung, aber das ist nicht wahr, es funktioniert sogar mit Zeichenfolge und Sie können .tolist hinzufügen, wenn Sie eine Liste erhalten möchten ...
GM
1
Ich denke, das ist ein bisschen wie der Versuch, eine Biene mit einem Vorschlaghammer zu töten. Funktioniert sicher! Aber das Importieren einer Bibliothek für genau diesen Zweck könnte ein wenig übertrieben sein, oder?
Debosmit Ray
@DebosmitRay Es kann nützlich sein, wenn Sie in Data Science arbeiten, wo Sie normalerweise mit Numpy arbeiten und oft mit Numpy-Array arbeiten müssen.
GM
Die beste Antwort im Jahr 2020 @DebosmitRay Ich hoffe, Sie ändern Ihre Meinung und verwenden jedes Mal Numpy / Pandas, wenn Sie können
Egos
21

Eine andere Möglichkeit:

>>> seq = [1,2,3,'a', 'a', 1,2]
>> dict.fromkeys(seq).keys()
['a', 1, 2, 3]
James Sapam
quelle
1
Beachten Sie, dass in modernen Python-Versionen (2.7+, glaube ich, aber ich erinnere mich nicht sicher) keys()ein Wörterbuchansichtsobjekt zurückgegeben wird, keine Liste.
Dustin Wyatt
16

Simpel und einfach:

myList = [1, 2, 3, 1, 2, 5, 6, 7, 8]
cleanlist = []
[cleanlist.append(x) for x in myList if x not in cleanlist]

Ausgabe:

>>> cleanlist 
[1, 2, 3, 5, 6, 7, 8]
Nima Soroush
quelle
5
quadratische Komplexität trotzdem - inist O (n) Operation und Ihr cleanlistWille hat höchstens nZahlen => Worst-Case ~ O (n ^ 2)
jermenkoo
6
Listenverständnis sollte nicht für Nebenwirkungen verwendet werden.
Jean-François Fabre
13

In dieser Antwort werden zwei Abschnitte aufgeführt: Zwei einzigartige Lösungen und ein Diagramm der Geschwindigkeit für bestimmte Lösungen.

Doppelte Elemente entfernen

Die meisten dieser Antworten entfernen nur doppelte Elemente, die hashbar sind. Diese Frage bedeutet jedoch nicht, dass nicht nur hashbare Elemente benötigt werden. Dies bedeutet, dass ich einige Lösungen anbieten werde, für die keine hashbaren Elemente erforderlich sind.

Sammlungen.Counter ist ein leistungsfähiges Werkzeug in der Standardbibliothek, das dafür perfekt sein könnte. Es gibt nur eine andere Lösung, die sogar Counter enthält. Diese Lösung ist jedoch auch auf Hash- Schlüssel beschränkt.

Um nicht zerlegbare Schlüssel in Counter zuzulassen, habe ich eine Container-Klasse erstellt, die versucht, die Standard-Hash-Funktion des Objekts abzurufen. Wenn dies jedoch fehlschlägt, wird die Identitätsfunktion ausprobiert. Es definiert auch eine Gleichung und eine Hash- Methode. Dies sollte ausreichen, um nicht zerlegbare Elemente in unserer Lösung zuzulassen . Nicht hashbare Objekte werden so behandelt, als wären sie hashbar. Diese Hash-Funktion verwendet jedoch die Identität für nicht verwertbare Objekte, was bedeutet, dass zwei gleiche Objekte, die beide nicht verwertbar sind, nicht funktionieren. Ich schlage vor, dass Sie dies überschreiben und ändern, um den Hash eines äquivalenten veränderlichen Typs zu verwenden (wie hash(tuple(my_list))wenn Sie if my_listals Liste verwenden).

Ich habe auch zwei Lösungen gemacht. Eine andere Lösung, die die Reihenfolge der Elemente beibehält und eine Unterklasse von OrderedDict und Counter mit dem Namen 'OrderedCounter' verwendet. Hier sind die Funktionen:

from collections import OrderedDict, Counter

class Container:
    def __init__(self, obj):
        self.obj = obj
    def __eq__(self, obj):
        return self.obj == obj
    def __hash__(self):
        try:
            return hash(self.obj)
        except:
            return id(self.obj)

class OrderedCounter(Counter, OrderedDict):
     'Counter that remembers the order elements are first encountered'

     def __repr__(self):
         return '%s(%r)' % (self.__class__.__name__, OrderedDict(self))

     def __reduce__(self):
         return self.__class__, (OrderedDict(self),)

def remd(sequence):
    cnt = Counter()
    for x in sequence:
        cnt[Container(x)] += 1
    return [item.obj for item in cnt]

def oremd(sequence):
    cnt = OrderedCounter()
    for x in sequence:
        cnt[Container(x)] += 1
    return [item.obj for item in cnt]

remd ist eine nicht geordnete Sortierung, oremd ist eine geordnete Sortierung. Sie können klar erkennen, welches schneller ist, aber ich werde es trotzdem erklären. Die nicht geordnete Sortierung ist etwas schneller. Es speichert weniger Daten, da keine Bestellung erforderlich ist.

Jetzt wollte ich auch die Geschwindigkeitsvergleiche jeder Antwort zeigen. Also mache ich das jetzt.

Welche Funktion ist die schnellste?

Zum Entfernen von Duplikaten habe ich aus einigen Antworten 10 Funktionen zusammengestellt. Ich habe die Geschwindigkeit jeder Funktion berechnet und sie mit matplotlib.pyplot in ein Diagramm eingefügt .

Ich habe dies in drei Grafikrunden unterteilt. Ein Hashable ist ein Objekt, das gehasht werden kann, ein Nicht-Hashable ist ein Objekt, das nicht gehasht werden kann. Eine geordnete Sequenz ist eine Sequenz, die die Ordnung beibehält, eine ungeordnete Sequenz bewahrt die Ordnung nicht. Hier noch ein paar Begriffe:

Ungeordnetes Hashable war für jede Methode geeignet, bei der Duplikate entfernt wurden, ohne dass die Reihenfolge eingehalten werden musste. Es musste nicht für Unashashables funktionieren, aber es konnte.

Bestelltes Hashable war für jede Methode geeignet, bei der die Reihenfolge der Elemente in der Liste beibehalten wurde, aber es musste nicht für nicht zerlegbare Elemente funktionieren, aber es konnte.

Ordered Unhashable war eine Methode, die die Reihenfolge der Elemente in der Liste beibehielt und für Unhashables funktionierte.

Auf der y-Achse ist die Anzahl der Sekunden angegeben.

Auf der x-Achse befindet sich die Nummer, auf die die Funktion angewendet wurde.

Wir haben Sequenzen für ungeordnete Hashables und geordnete Hashables mit folgendem Verständnis generiert: [list(range(x)) + list(range(x)) for x in range(0, 1000, 10)]

Für bestellte nicht zerlegbare Gegenstände: [[list(range(y)) + list(range(y)) for y in range(x)] for x in range(0, 1000, 10)]

Beachten Sie, dass es einen "Schritt" im Bereich gibt, da dies ohne ihn 10x so lange gedauert hätte. Auch weil ich meiner persönlichen Meinung nach dachte, es hätte ein bisschen leichter zu lesen ausgesehen.

Beachten Sie auch, dass die Tasten in der Legende das sind, was ich als die wichtigsten Teile der Funktion erraten wollte. Welche Funktion hat das Schlimmste oder Beste? Die Grafik spricht für sich.

Nachdem dies erledigt ist, sind hier die Grafiken.

Ungeordnete Hashables

Geben Sie hier die Bildbeschreibung ein (Vergrößert) Geben Sie hier die Bildbeschreibung ein

Bestellte Hashables

Geben Sie hier die Bildbeschreibung ein (Vergrößert) Geben Sie hier die Bildbeschreibung ein

Bestellte Unhashables

Geben Sie hier die Bildbeschreibung ein (Vergrößert) Geben Sie hier die Bildbeschreibung ein

Corman
quelle
11

Ich hatte ein Diktat in meiner Liste, daher konnte ich den obigen Ansatz nicht verwenden. Ich habe den Fehler bekommen:

TypeError: unhashable type:

Wenn Sie sich also für die Bestellung interessieren und / oder einige Artikel nicht zerlegbar sind . Dann finden Sie dies vielleicht nützlich:

def make_unique(original_list):
    unique_list = []
    [unique_list.append(obj) for obj in original_list if obj not in unique_list]
    return unique_list

Einige halten Listenverständnis mit Nebeneffekten möglicherweise für keine gute Lösung. Hier ist eine Alternative:

def make_unique(original_list):
    unique_list = []
    map(lambda x: unique_list.append(x) if (x not in unique_list) else False, original_list)
    return unique_list
cchristelis
quelle
6
mapmit einem Nebeneffekt ist noch irreführender als ein Listcomp mit einem Nebeneffekt. Auch lambda x: unique_list.append(x)ist nur eine klobigere und langsamere Art zu passieren unique_list.append.
Abarnert
Sehr nützliche Möglichkeit, Elemente in nur einer Zeile anzuhängen, danke!
ZLNK
2
@ZLNK bitte, benutze das nie. Abgesehen davon, dass es konzeptionell hässlich ist, ist es auch äußerst ineffizient, da Sie tatsächlich eine potenziell große Liste erstellen und sie wegwerfen, nur um eine grundlegende Iteration durchzuführen.
Eli Korvigo
10

Alle Ordnungserhaltungsansätze, die ich bisher hier gesehen habe, verwenden entweder einen naiven Vergleich (bestenfalls mit O (n ^ 2) Zeitkomplexität) oder schwere OrderedDicts/ set+ list-Kombinationen, die auf hashbare Eingaben beschränkt sind. Hier ist eine Hash-unabhängige O (nlogn) -Lösung:

Update fügte das keyArgument, die Dokumentation und die Python 3-Kompatibilität hinzu.

# from functools import reduce <-- add this import on Python 3

def uniq(iterable, key=lambda x: x):
    """
    Remove duplicates from an iterable. Preserves order. 
    :type iterable: Iterable[Ord => A]
    :param iterable: an iterable of objects of any orderable type
    :type key: Callable[A] -> (Ord => B)
    :param key: optional argument; by default an item (A) is discarded 
    if another item (B), such that A == B, has already been encountered and taken. 
    If you provide a key, this condition changes to key(A) == key(B); the callable 
    must return orderable objects.
    """
    # Enumerate the list to restore order lately; reduce the sorted list; restore order
    def append_unique(acc, item):
        return acc if key(acc[-1][1]) == key(item[1]) else acc.append(item) or acc 
    srt_enum = sorted(enumerate(iterable), key=lambda item: key(item[1]))
    return [item[1] for item in sorted(reduce(append_unique, srt_enum, [srt_enum[0]]))] 
Eli Korvigo
quelle
Diese Lösung erfordert jedoch bestellbare Elemente. Ich werde es verwenden, um meine Liste von Listen zu vereinfachen: Es ist ein Schmerz, tuple()Listen zu erstellen und sie zu hashen . | | | | - Im Allgemeinen dauert der Hash-Prozess eine Zeit, die proportional zur Größe der gesamten Daten ist, während diese Lösung eine Zeit O (nlog (n)) benötigt, die nur von der Länge der Liste abhängt.
Loxaxs
Ich denke, dass der satzbasierte Ansatz genauso billig (O (n log n)) oder billiger ist als das Sortieren + Erkennen von Unikaten. (Dieser Ansatz würde jedoch viel besser parallelisieren.) Außerdem wird die ursprüngliche Reihenfolge nicht genau beibehalten, es wird jedoch eine vorhersehbare Reihenfolge angegeben.
9000
@ 9000 Das stimmt. Ich habe nie die zeitliche Komplexität eines auf Hash-Tabellen basierenden Ansatzes erwähnt, der offensichtlich O (n) ist. Hier finden Sie viele Antworten mit Hash-Tabellen. Sie sind jedoch nicht universell, da Objekte hashbar sein müssen. Darüber hinaus sind sie viel speicherintensiver.
Eli Korvigo
Es braucht Zeit, um diese Antwort zu lesen und zu verstehen. Gibt es einen Grund für die Aufzählung, wenn Sie die Indizes nicht verwenden? The reduce() arbeitet bereits an einer sortierten Sammlung srt_enum. Warum haben Sie sich sortederneut beworben ?
Brayoni
@Brayoni Die erste Sortierung dient dazu, gleiche Werte zu gruppieren, die zweite Sortierung dient dazu, die ursprüngliche Reihenfolge wiederherzustellen. Die Aufzählung wird benötigt, um die ursprüngliche relative Reihenfolge zu verfolgen.
Eli Korvigo
9

Wenn Sie die Reihenfolge beibehalten und keine externen Module verwenden möchten, ist dies eine einfache Möglichkeit:

>>> t = [1, 9, 2, 3, 4, 5, 3, 6, 7, 5, 8, 9]
>>> list(dict.fromkeys(t))
[1, 9, 2, 3, 4, 5, 6, 7, 8]

Hinweis: Bei dieser Methode wird die Reihenfolge des Erscheinungsbilds beibehalten. Wie oben dargestellt, werden neun nach dem anderen angezeigt, da es das erste Mal war, dass es angezeigt wurde. Dies ist jedoch das gleiche Ergebnis wie bei diesem Vorgang

from collections import OrderedDict
ulist=list(OrderedDict.fromkeys(l))

aber es ist viel kürzer und läuft schneller.

Dies funktioniert, weil die fromkeysFunktion jedes Mal , wenn sie versucht, einen neuen Schlüssel zu erstellen, diesen einfach überschreibt, wenn er bereits vorhanden ist. Dies wirkt sich jedoch überhaupt nicht auf das Wörterbuch aus, da fromkeysein Wörterbuch erstellt wird, in dem alle Schlüssel den Wert haben None, sodass alle Duplikate auf diese Weise effektiv entfernt werden.

HEEL_caT666
quelle
Probieren Sie
8

Sie können dies auch tun:

>>> t = [1, 2, 3, 3, 2, 4, 5, 6]
>>> s = [x for i, x in enumerate(t) if i == t.index(x)]
>>> s
[1, 2, 3, 4, 5, 6]

Der Grund, warum dies funktioniert, ist, dass die indexMethode nur den ersten Index eines Elements zurückgibt. Doppelte Elemente haben höhere Indizes. Siehe hier :

list.index (x [, start [, end]]) Gibt einen auf
Null basierenden Index in der Liste des ersten Elements zurück, dessen Wert x ist. Löst einen ValueError aus, wenn kein solches Element vorhanden ist.

Atonal
quelle
Das ist schrecklich ineffizient. list.indexist eine Operation mit linearer Zeit, die Ihre Lösung quadratisch macht.
Eli Korvigo
Du hast recht. Aber ich glaube auch, dass es ziemlich offensichtlich ist, dass die Lösung ein Einzeiler sein soll, der die Ordnung beibehält. Alles andere ist schon hier.
Atonal
7

Versuchen Sie es mit Sets:

import sets
t = sets.Set(['a', 'b', 'c', 'd'])
t1 = sets.Set(['a', 'b', 'c'])

print t | t1
print t - t1
Charlie Martin
quelle
7

Variante mit Bestellkonservierung reduzieren:

Angenommen, wir haben eine Liste:

l = [5, 6, 6, 1, 1, 2, 2, 3, 4]

Variante reduzieren (ineffizient):

>>> reduce(lambda r, v: v in r and r or r + [v], l, [])
[5, 6, 1, 2, 3, 4]

5 x schneller, aber anspruchsvoller

>>> reduce(lambda r, v: v in r[1] and r or (r[0].append(v) or r[1].add(v)) or r, l, ([], set()))[0]
[5, 6, 1, 2, 3, 4]

Erläuterung:

default = (list(), set())
# user list to keep order
# use set to make lookup faster

def reducer(result, item):
    if item not in result[1]:
        result[0].append(item)
        result[1].add(item)
    return result

reduce(reducer, l, default)[0]
Sergey M Nikitin
quelle
7

Der beste Ansatz zum Entfernen von Duplikaten aus einer Liste ist die Verwendung der in Python verfügbaren Funktion set () , mit der diese Menge erneut in eine Liste konvertiert wird

In [2]: some_list = ['a','a','v','v','v','c','c','d']
In [3]: list(set(some_list))
Out[3]: ['a', 'c', 'd', 'v']
Anurag Misra
quelle
@ MeZZaveri froh.!
Anurag Misra
Das Instanziieren neuer Listen und Sets ist nicht kostenlos. Was passiert, wenn wir dies viele Male schnell hintereinander tun (dh in einer sehr engen Schleife) und die Listen sehr klein sind?
Z4-Tier
6

Sie können die folgende Funktion verwenden:

def rem_dupes(dup_list): 
    yooneeks = [] 
    for elem in dup_list: 
        if elem not in yooneeks: 
            yooneeks.append(elem) 
    return yooneeks

Beispiel :

my_list = ['this','is','a','list','with','dupicates','in', 'the', 'list']

Verwendungszweck:

rem_dupes(my_list)

['this', 'is', 'a', 'list', 'with', 'dupicates', 'in', 'the']

Kybernetisch
quelle
5

Es gibt viele andere Antworten, die verschiedene Möglichkeiten vorschlagen, dies zu tun, aber alle sind Stapeloperationen, und einige von ihnen werfen die ursprüngliche Reihenfolge weg. Das mag je nach Bedarf in Ordnung sein, aber wenn Sie die Werte in der Reihenfolge der ersten Instanz jedes Werts durchlaufen möchten und die Duplikate im laufenden Betrieb im Vergleich zu allen auf einmal entfernen möchten, können Sie sie verwenden dieser Generator:

def uniqify(iterable):
    seen = set()
    for item in iterable:
        if item not in seen:
            seen.add(item)
            yield item

Dies gibt einen Generator / Iterator zurück, sodass Sie ihn überall dort verwenden können, wo Sie einen Iterator verwenden können.

for unique_item in uniqify([1, 2, 3, 4, 3, 2, 4, 5, 6, 7, 6, 8, 8]):
    print(unique_item, end=' ')

print()

Ausgabe:

1 2 3 4 5 6 7 8

Wenn Sie eine möchten list, können Sie dies tun:

unique_list = list(uniqify([1, 2, 3, 4, 3, 2, 4, 5, 6, 7, 6, 8, 8]))

print(unique_list)

Ausgabe:

[1, 2, 3, 4, 5, 6, 7, 8]
Cyphase
quelle
seen = set(iterable); for item in seen: yield itemist mit ziemlicher Sicherheit schneller. (Ich habe diesen speziellen Fall nicht ausprobiert, aber das wäre meine Vermutung.)
dylnmc
2
@dylnmc, das ist eine Stapeloperation, und es verliert auch die Bestellung. Meine Antwort sollte speziell im laufenden Betrieb und in der Reihenfolge des ersten Auftretens erfolgen. :)
Cyphase
5

Ohne Set zu verwenden

data=[1, 2, 3, 1, 2, 5, 6, 7, 8]
uni_data=[]
for dat in data:
    if dat not in uni_data:
        uni_data.append(dat)

print(uni_data) 
Suresh Gupta
quelle
5

Sie können setDuplikate entfernen:

mylist = list(set(mylist))

Beachten Sie jedoch, dass die Ergebnisse ungeordnet sind. Wenn das ein Problem ist:

mylist.sort()
Flavio Wuensche
quelle
1
Sie können einfach tun: mylist = sortiert (Liste (set (mylist)))
Erik Campobadal
5

Ein weiterer besserer Ansatz könnte sein:

import pandas as pd

myList = [1, 2, 3, 1, 2, 5, 6, 7, 8]
cleanList = pd.Series(myList).drop_duplicates().tolist()
print(cleanList)

#> [1, 2, 3, 5, 6, 7, 8]

und die Ordnung bleibt erhalten.

Akarsh Jain
quelle
Obwohl dies gut funktionieren könnte, scheint die Verwendung einer schweren Bibliothek wie Pandas für diesen Zweck ein Overkill zu sein.
Glutexo
4

Dieser kümmert sich um die Bestellung ohne allzu großen Aufwand (OrderdDict & andere). Wahrscheinlich nicht der pythonischste oder kürzeste Weg, aber der Trick:

def remove_duplicates(list):
    ''' Removes duplicate items from a list '''
    singles_list = []
    for element in list:
        if element not in singles_list:
            singles_list.append(element)
    return singles_list
cgf
quelle
1. Sie sollten niemals eingebaute Namen beschatten (zumindest so wichtig wie list). 2. Ihre Methode skaliert extrem schlecht: Sie ist quadratisch in der Anzahl der Elemente in list.
Eli Korvigo
1. Richtig, aber dies war ein Beispiel; 2. Richtig, und genau aus diesem Grund habe ich es angeboten. Alle hier veröffentlichten Lösungen haben Vor- und Nachteile. Einige opfern Einfachheit oder Ordnung, meine opfern Skalierbarkeit.
cgf
Dies ist ein "Shlemiel der Maler" -Algorithmus ...
Z4-Tier
4

Der folgende Code ist einfach zum Entfernen von Duplikaten in der Liste

def remove_duplicates(x):
    a = []
    for i in x:
        if i not in a:
            a.append(i)
    return a

print remove_duplicates([1,2,2,3,3,4])

es gibt zurück [1,2,3,4]

vinay hegde
quelle
2
Wenn Sie sich nicht für die Bestellung interessieren, dauert dies erheblich länger. list(set(..))(über 1 Million Durchgänge) schlägt diese Lösung um ungefähr 10 ganze Sekunden - während dieser Ansatz ungefähr 12 Sekunden list(set(..))dauert , dauert er nur ungefähr 2 Sekunden!
dylnmc
@dylnmc Dies ist auch ein Duplikat einer deutlich älteren Antwort
Eli Korvigo
4

Hier ist die schnellste pythonische Lösung im Vergleich zu anderen in den Antworten aufgeführten.

Durch die Verwendung von Implementierungsdetails der Kurzschlussbewertung kann das Listenverständnis verwendet werden, das schnell genug ist. visited.add(item)Gibt immer Noneals Ergebnis zurück, das als ausgewertet wird False, sodass die rechte Seite von orimmer das Ergebnis eines solchen Ausdrucks ist.

Zeit es selbst

def deduplicate(sequence):
    visited = set()
    adder = visited.add  # get rid of qualification overhead
    out = [adder(item) or item for item in sequence if item not in visited]
    return out
thodnev
quelle
4

Mit set :

a = [0,1,2,3,4,3,3,4]
a = list(set(a))
print a

Verwenden von unique :

import numpy as np
a = [0,1,2,3,4,3,3,4]
a = np.unique(a).tolist()
print a
Nurul Akter Towhid
quelle
4

Unglücklicherweise. Die meisten Antworten hier behalten entweder die Reihenfolge nicht bei oder sind zu lang. Hier ist eine einfache, auftragserhaltende Antwort.

s = [1,2,3,4,5,2,5,6,7,1,3,9,3,5]
x=[]

[x.append(i) for i in s if i not in x]
print(x)

Dadurch erhalten Sie x mit entfernten Duplikaten, wobei die Reihenfolge beibehalten wird.

ste_kwr
quelle
3

Sehr einfacher Weg in Python 3:

>>> n = [1, 2, 3, 4, 1, 1]
>>> n
[1, 2, 3, 4, 1, 1]
>>> m = sorted(list(set(n)))
>>> m
[1, 2, 3, 4]
Wariored
quelle
2
sorted(list(...))ist redundant ( sortedkonvertiert sein Argument bereits implizit in ein neues list, sortiert es und gibt das neue zurück list, sodass beide Mittel verwendet werden, um ein unnötiges temporäres Argument zu erstellen list). Nur verwenden, listwenn das Ergebnis nicht sortiert werden muss. Nur verwenden, sortedwenn das Ergebnis sortiert werden muss.
ShadowRanger
3

Die Magie von Python Eingebauter Typ

In Python ist es sehr einfach, die komplizierten Fälle wie diese zu verarbeiten, und zwar nur nach dem in Python integrierten Typ.

Lassen Sie mich Ihnen zeigen, wie es geht!

Methode 1: Allgemeiner Fall

Die Möglichkeit ( 1 Zeilencode ), doppelte Elemente in der Liste zu entfernen und dennoch die Sortierreihenfolge beizubehalten

line = [1, 2, 3, 1, 2, 5, 6, 7, 8]
new_line = sorted(set(line), key=line.index) # remove duplicated element
print(new_line)

Sie erhalten das Ergebnis

[1, 2, 3, 5, 6, 7, 8]

Methode 2: Sonderfall

TypeError: unhashable type: 'list'

Der Sonderfall zur Verarbeitung nicht verwertbar ( 3 Zeilencodes )

line=[['16.4966155686595', '-27.59776154691', '52.3786295521147']
,['16.4966155686595', '-27.59776154691', '52.3786295521147']
,['17.6508629295574', '-27.143305738671', '47.534955022564']
,['17.6508629295574', '-27.143305738671', '47.534955022564']
,['18.8051102904552', '-26.688849930432', '42.6912804930134']
,['18.8051102904552', '-26.688849930432', '42.6912804930134']
,['19.5504702331098', '-26.205884452727', '37.7709192714727']
,['19.5504702331098', '-26.205884452727', '37.7709192714727']
,['20.2929416861422', '-25.722717575124', '32.8500163147157']
,['20.2929416861422', '-25.722717575124', '32.8500163147157']]

tuple_line = [tuple(pt) for pt in line] # convert list of list into list of tuple
tuple_new_line = sorted(set(tuple_line),key=tuple_line.index) # remove duplicated element
new_line = [list(t) for t in tuple_new_line] # convert list of tuple into list of list

print (new_line)

Sie erhalten das Ergebnis:

[
  ['16.4966155686595', '-27.59776154691', '52.3786295521147'], 
  ['17.6508629295574', '-27.143305738671', '47.534955022564'], 
  ['18.8051102904552', '-26.688849930432', '42.6912804930134'], 
  ['19.5504702331098', '-26.205884452727', '37.7709192714727'], 
  ['20.2929416861422', '-25.722717575124', '32.8500163147157']
]

Weil Tupel hashbar ist und Sie Daten einfach zwischen Liste und Tupel konvertieren können

Milo Chen
quelle