Das entfernen von Duplikaten in Listen
Ziemlich viel schreiben brauche ich ein Programm um zu überprüfen, ob eine Liste alle Duplikate und wenn es tut, entfernt Sie und gibt eine neue Liste zurück mit den Elementen, die nicht dupliziert/entfernen. Dies ist, was ich habe, aber um ehrlich zu sein, ich weiß nicht, was zu tun ist.
def remove_duplicates():
t = ['a', 'b', 'c', 'd']
t2 = ['a', 'c', 'd']
for t in t2:
t.append(t.remove())
return t
- Ihre Beschreibung sagt, dass Sie überprüfen eine "Liste" für Duplikate, aber dein code prüft zwei Listen.
InformationsquelleAutor Neemaximo | 2011-11-01
Schreibe einen Kommentar Antworten abbrechen
Du musst angemeldet sein, um einen Kommentar abzugeben.
Den gemeinsamen Ansatz, um eine einzigartige Sammlung von Gegenständen ist die Verwendung eines
set
. Sets sind ungeordnete Sammlungen von verschiedene Objekte. Erstellen Sie einen Satz von jeder durchsuchbar, können Sie einfach übergeben Sie an die integrierteset()
Funktion. Wenn Sie später brauchen eine echte Liste wieder, Sie kann genauso passieren das set derListen()
Funktion.Das folgende Beispiel sollte das abdecken, was Sie zu tun versuchen:
Wie Sie sehen können von der Beispiel-Ergebnis die ursprüngliche Reihenfolge nicht beibehalten wird. Wie oben erwähnt, setzt sich selbst sind ungeordnete Sammlungen, so dass die Ordnung verloren. Beim konvertieren einen Satz zurück, um eine Liste beliebiger Reihenfolge erstellt wird.
Aufrechterhaltung der Ordnung
Wenn die Reihenfolge wichtig ist für Sie, dann müssen Sie einen anderen Mechanismus. Eine sehr häufige Lösung für diese Verlass ist auf
OrderedDict
zu halten, die Reihenfolge der Schlüssel beim einführen:Beginnend mit Python 3.7, das integrierte Wörterbuch ist garantiert zu halten Sie die Einfügemarke, um als gut, so können Sie auch verwenden, dass direkt, wenn Sie sind auf Python 3.7 oder höher (oder CPython 3.6):
Beachten Sie, dass dies den Aufwand der Erstellung eines Lexikons zuerst, und dann eine Liste erstellen von es. Wenn Sie nicht wirklich brauchen, um erhalten den Auftrag, du bist besser dran mit einem Satz. Check-out diese Frage für weitere details und alternative Möglichkeiten zu bewahren, die Reihenfolge beim entfernen der Duplikate.
Schließlich beachten Sie, dass sowohl die
set
sowie dieOrderedDict
/dict
Lösungen erfordern Ihre Artikel werden hashable. Dies bedeutet in der Regel, dass Sie unveränderlich sind. Wenn Sie es zu tun haben mit Sachen, die nicht hashable (z.B. Liste der Objekte), dann haben Sie, um eine langsame Annäherung, in dem Sie im Grunde zu vergleichen, jedes Element mit jedem anderen Element in eine verschachtelte Schleife.In Python 2.7, die neue Art, das entfernen von Duplikaten aus einer iterierbar, während es in der original-Reihenfolge ist:
In Python 3.5, die OrderedDict hat eine C-Implementierung. Meine timings zu zeigen, dass diese jetzt sowohl die Schnellste und kürzeste der verschiedenen Ansätze für Python 3.5.
In Python 3.6, die regelmäßige dict wurde beide bestellt und kompakt. (Diese Funktion gilt für CPython und PyPy kann aber nicht in anderen Implementierungen). Das gibt uns eine neue Schnellste Weg, deduping unter Beibehaltung der Reihenfolge:
In Python 3.7, die regelmäßige dict garantiert beide bestellt in allen Implementierungen. So, die kürzeste und Schnellste Lösung ist:
TypeError: unhashable type: 'dictlist'
unique_everseen
, das funktioniert mit beiden hashable und unhashable Elemente.Es ist ein one-liner:
list(set(source_list))
wird den trick tun.Einen
set
ist etwas, das kann nicht vielleicht haben Sie Duplikate.Update: ein Auftrag-Erhaltung der Ansatz ist zwei Zeilen:
Hier verwenden wir die Tatsache, dass
OrderedDict
erinnert sich an die Einfügung Reihenfolge der Schlüssel, und nicht geändert werden, wenn ein Wert zu einem bestimmten Schlüssel wird aktualisiert. Wir legenTrue
als Werte, aber wir könnten etwas einfügen, Werte werden einfach nicht verwendet. (set
arbeitet viel wie eindict
mit ignoriert Werte, auch.)source_list
ist hashable.frozenset
arbeitet mit nicht-hashable Inhalt. Ich bin noch immer der nicht-hashable Fehler bei der Verwendung vonfrozenset
.Wenn Sie kümmern sich nicht um die Reihenfolge, nur dazu:
Einen
set
ist garantiert nicht auf Duplikate.l
ist hashable.Machen eine neue Liste für die Beibehaltung der Reihenfolge der ersten Elemente Duplikate in
L
newlist=[ii for n,ii in enumerate(L) if ii not in L[:n]]
beispielsweise
if L=[1, 2, 2, 3, 4, 2, 4, 3, 5]
dannnewlist
wird[1,2,3,4,5]
Dieser überprüft jedes neue element, das noch nicht erschienen zuvor in der Liste, bevor Sie es.
Auch muss es nicht importiert.
set
undOrderedDict
haben niedrigere fortgeführten Zeit Komplexität.Einem Kollegen geschickt haben, die akzeptierten Antworten, die als Teil seines Codes, um mich für ein codereview heute.
Während ich sicherlich bewundern Sie die Eleganz der Antwort in Frage, ich bin nicht zufrieden mit der Leistung.
Ich habe versucht, diese Lösung (ich benutze set zu reduzieren-lookup-Zeit)
Vergleichen die Effizienz, die ich verwendet eine zufällige Stichprobe von 100 Integer - 62 waren einzigartig
Hier sind die Ergebnisse der Messungen
Gut, was passiert, wenn der Satz aus der Lösung entfernt?
Das Ergebnis ist nicht so schlecht, wie mit dem OrderedDict, aber immer noch mehr als 3 mal von der ursprünglichen Lösung
Andere Art und Weise tun:
keys()
gibt ein dictionary-Objekt anzeigen, nicht eine Liste.Gibt es auch Lösungen mit Pandas und Numpy. Beide return numpy-array, so verwenden Sie die Funktion
.tolist()
wenn Sie möchten, eine Liste.Pandas Lösung
Mit Pandas Funktion
unique()
:Numpy Lösung
Mithilfe von numpy-Funktion
unique()
.Beachten Sie, dass numpy.einzigartig ( ... ) auch die Werte Sortieren,. Also die Liste
t2
zurückgegeben sortiert. Wenn Sie wollen, um die Reihenfolge beibehalten wie in diese Antwort:Die Lösung ist nicht so elegant im Vergleich zu den anderen, aber im Vergleich zu den pandas.unique(), numpy.unique() kann man auch prüfen, ob geschachtelte arrays sind einzigartig, die entlang einer ausgewählten Achse.
Einfach und leicht:
Ausgabe:
in
ist O(n) - operation und Ihrecleanlist
höchstensn
zahlen => worst-case - ~O(n^2)Hatte ich ein dict in meiner Liste, so konnte ich nicht die oben genannte Ansatz. Ich habe den Fehler:
Also, wenn Sie kümmern sich um um und/oder einige Elemente sind unhashable. Dann könnten Sie diese nützlich finden:
Einige können betrachten Sie die Liste Verständnis mit einem Nebeneffekt zu nicht eine gute Lösung sein. Hier ist eine alternative:
map
mit ein Nebeneffekt ist noch mehr irreführend als listcomp mit einer Nebenwirkung. Auchlambda x: unique_list.append(x)
ist nur eine clunkier und langsamer Weg, um passunique_list.append
.Alle Reihenfolge-Erhaltung-Ansätze, die ich gesehen habe hier bisher entweder naiv-Vergleich (mit O(n^2) Zeit-Komplexität am besten) oder schwere
OrderedDicts
/set
+list
Kombinationen, die begrenzt sind, um hashable-Eingänge. Hier ist ein hash-unabhängige O(nlogn) Lösung:Update Hinzugefügt, die
key
argument, Dokumentation und Python-3-Kompatibilität.tuple()
Listen und hash Sie. | | | | - Allgemein gesagt, wird der hash-Prozess dauert eine Zeit proportional zu der Größe der gesamten Daten, während diese Lösung nimmt eine Zeit von O(nlog(n)), nur abhängig von der Länge der Liste.Versuchen Sie mit Sätzen:
Könnte man dies auch tun:
Dem Grund, dass die oben genannten arbeiten ist, dass
index
- Methode zurückgibt, wird nur der erste index eines Elements. Doppelte Elemente haben höhere Indizes. Finden Sie hier:list.index
ist eine lineare operation, so dass Ihre Lösung die quadratische.Reduzieren Variante mit der Bestellung erhalten:
Davon ausgehen, dass wir-Liste:
Reduzieren Variante (unefficient):
5 x schneller, aber auch anspruchsvoller
Erklärung:
Beste Ansatz für das entfernen von Duplikaten aus einer Liste mit set () - Funktion, erhältlich in python, wieder konvertieren, dass in Liste
Können Sie folgende Funktion verwenden:
Beispiel:
Verwendung:
['dies', 'ist', 'eine', 'Liste', 'mit', 'dupicates', 'in', 'die']
Wenn Sie wollen, um die Erhaltung der Ordnung, und Sie verwenden keine externen Module hier ist eine einfache Möglichkeit, dies zu tun:
Hinweis: bei Dieser Methode bleibt die Reihenfolge der Erscheinung, so dass, wie oben gesehen, neun nach uns kommen werden, weil es war das erste mal erschien. Aber das ist das gleiche Ergebnis als würde man mit dabei
aber es ist viel kürzer und wird schneller ausgeführt.
Dies funktioniert, weil jedes mal, wenn die
fromkeys
- Funktion versucht, einen neuen Schlüssel erstellen, wenn der Wert bereits existiert, wird es einfach überschrieben. Dieser gewohnt auf das Wörterbuch an alle jedoch, alsfromkeys
erzeugt ein dictionary, in dem alle Tasten haben den WertNone
, so effektiv eliminiert alle Duplikate auf diese Weise.Gibt es noch viele andere beantwortet Ihnen verschiedene Möglichkeiten, dies zu tun, aber Sie sind alle batch-Operationen, und einige von Ihnen wegwerfen, die original-Reihenfolge. Das mag OK sein-je nachdem, was Sie brauchen, aber wenn Sie wollen, um die Iteration über die Werte in der Reihenfolge von der ersten Instanz jeder Wert, und Sie möchten, entfernen Sie die Duplikate on-the-fly " gegen alle auf einmal, könnten Sie mit diesem generator:
Dieser liefert ein generator/iterator, so können Sie es überall benutzen, das Sie verwenden können, einen iterator.
Ausgabe:
Wenn Sie möchten, eine
list
Sie dies tun können:Ausgabe:
seen = set(iterable); for item in seen: yield item
ist fast sicher schneller. (Ich habe nicht versucht, diesen speziellen Fall, aber das wäre meine Vermutung.)Ohne Verwendung von Satz
Dieser eine kümmert sich um die Bestellung, ohne zu viel Aufwand (OrderdDict & andere). Wahrscheinlich nicht die meisten Pythonic way, noch der kürzeste Weg, aber der trick funktioniert:
list
); 2. Deine Methode skaliert extrem schlecht: es ist quadratisch in der Anzahl der Elemente inlist
.code unten ist einfach löschen Duplikate in der Liste
gibt es [1,2,3,4]
list(set(..))
(über 1 million Pässe) schlagen wird diese Lösung von etwa 10 ganze Sekunden - in der Erwägung, dass dieser Ansatz dauert etwa 12 Sekunden,list(set(..))
dauert nur etwa 2 Sekunden!Mit set :
Mit einzigartige :
Ein mehr besserer Ansatz könnte sein,
und die Reihenfolge bleibt erhalten.
Hier ist der Schnellste pythonic Lösung comaring anderen aufgeführten Antworten.
Mit details der Implementierung der short-circuit-evaluation erlaubt es zu benutzen, Liste, Verständnis, das ist schnell genug.
visited.add(item)
gibt immerNone
als ein Ergebnis, die ausgewertet werden, wieFalse
, so dass die Rechte Seite deror
würde immer das Ergebnis eines solchen Ausdrucks.Zeit es selbst
Sehr einfache Weise in Python 3:
sorted(list(...))
redundant ist (sorted
bereits implizit konvertiert Ihr argument in eine neuelist
sortiert, dann gibt die neuelist
, also sowohl bedeutet, dass eine unnötige temporärelist
). Verwenden Sie nurlist
wenn das Ergebnis muss nicht sortiert werden, verwenden Sie nursorted
wenn das Ergebnis sortiert werden muss.Hier ist ein Beispiel, Rückgabe-Liste, ohne repetiotions Erhaltung der Ordnung. Benötigt keine externe Einfuhren.
Überprüfen Sie dies, wenn Sie möchten, um Duplikate entfernen (in-place-edit anstelle der Rückgabe neue Liste) ohne mit eingebauten set, dict.Schlüssel, uniqify, counter
enumerate()
um den index schneller:for i, value in enumerate(t): if value in t[i + 1:]: t.remove(value)
[1,1,1]
Ich denke, die Konvertierung zu setzen, ist der einfachste Weg, um entfernen Sie doppelte:
Leider. Die meisten Antworten hier sind entweder nicht erhalten, die Bestellung oder zu lang sind. Hier ist ein einfaches, um die Erhaltung beantworten.
Damit bekommst du x mit Duplikate entfernt, sondern die Erhaltung der Bestellung.
Können Sie
set
Duplikate entfernen:Beachten Sie aber die Ergebnisse werden geordnet. Wenn das ist ein Problem:
Entfernen der Duplikate, machen Sie einen SATZ und dann wieder machen Sie eine LISTE und drucken/verwenden.
Ein set ist garantiert, um einzigartige Elemente. Zum Beispiel :
Wird die Ausgabe wie folgt (geprüft in python 2.7)
Können Sie dies einfach durch die Verwendung von sets.
Schritt1:, um die Verschiedenen Elemente von Listen
Step2 Bekommen Gemeinsame Elemente von Listen
Schritt 3 Kombinieren Sie
Einer Liste comprehesion Duplikate entfernen
Wenn Sie nicht kümmern, über Ordnung und wollen etwas anderes als die pythonic Möglichkeiten, wie oben vorgeschlagen (das heißt, es kann verwendet werden, in interviews), dann :
Zeit-Komplexität : O(n)
Hilfs-Speicherplatz : O(n)
Referenz: http://www.geeksforgeeks.org/remove-duplicates-sorted-array/
Gibt es eine Menge Antworten hier, dass die Verwendung einer
set(..)
(die ist schnell gegeben, die Elemente sind hashable) oder eine Liste (die den Nachteil hat, dass es Ergebnisse in einer O(n2) Algorithmus.Die Funktion, die ich vorschlagen, ist ein hybrid: wir nutzen eine
set(..)
für Elemente, die sind hashable, und einlist(..)
für diejenigen, die nicht sind. Außerdem es ist implementiert als eine generator, so dass wir zum Beispiel Begrenzung der Anzahl der Elemente, oder einige zusätzliche Filterung.Schließlich können wir auch die Verwendung einer
key
- argument, um anzugeben, in welcher Weise die Elemente sollten eindeutig sein. Zum Beispiel können wir benutzen, wenn wir wollen, dass das filtern einer Liste von strings, so dass jeder string in der Ausgabe hat eine andere Länge.Können wir jetzt für Instanz verwenden Sie diese wie:
Es ist somit eine uniqeness filter, die auf jeden durchsuchbar und filtern Unikate, unabhängig davon, ob diese hashable oder nicht.
Er macht eine Annahme: dass, wenn ein Objekt hashable, und ein anderer nicht, die beiden Objekte sind nie gleich. Dies kann genaugenommen passieren, obwohl es wäre sehr ungewöhnlich.
frozenset
ist hashable,set
ist nicht, und wenn Sie die gleichen Werte haben, sind Sie gleich, aber Sie werden behandelt wie nicht-gleich in diesen code.set(..)
dies wird einfach nicht funktionieren, und indem Sie einenlist
werden, ergibt dies lineare lookup-Zeit. So ist es gemeint als "besser" eingestellt, aber mit einigen Tücken.set(..)
auch in seltenen Fällen gibt Objekte, die sind nicht gleich. Zum Beispielmath.nan
ist nicht gleichmath.nan
, aber das Wörterbuch, es zurückzugeben, da es überprüft zunächst, für Referenz-Gleichheit.Eine andere Lösung könnte die folgende sein. Erstellen Sie ein Wörterbuch aus der Liste mit Element als Schlüssel und index als Wert, und drucken Sie dann die dictionary-Schlüssel.
list(set(lst))
erzielen würde, die die gleiche logische Folge.Vollständigkeit halber, und da dies eine sehr beliebte Frage, die toolz Bibliothek bietet eine
einzigartige
Funktion:Es erfordert die Installation einer 3rd-party-Modul, aber das Paket
iteration_utilities
enthält eineunique_everseen
1 - Funktion, können Sie entfernen Sie alle Duplikate, die Sie unter Beibehaltung der Reihenfolge:In Fall, dass Sie wollen, vermeiden Sie den overhead von der Liste neben der operation, die Sie verwenden können,
itertools.Kette
statt:Den
unique_everseen
funktioniert auch, wenn Sie unhashable Objekte (z.B. Listen) in den Listen:Jedoch wird (viel) langsamer als wenn die Elemente hashable.
1 Offenlegung: ich bin der Autor des
iteration_utilities
-Bibliothek.dies ist nur lesbar funtion ,leicht verständlich ,und ich habe das dict-Daten-Struktur,die ich verwendet habe einige eingebaute Funktionen und eine bessere Komplexität von O(n)
disclamer: u möglicherweise eine Einrückung Fehler(wenn kopieren und einfügen) ,verwenden Sie den obigen code, mit der richtigen Einrückung vor dem einfügen
Python gebaut hat-in vielen Funktionen können Sie die Verwendung von set() zum entfernen der Duplikate in der Liste.
Gemäß deinem Beispiel gibt es unten zwei Listen t und t2
Antwort: ['b']
Manchmal müssen Sie entfernen Sie doppelte Elemente in-place, ohne neue Liste. Zum Beispiel, die Liste ist zu groß, oder halten Sie es als eine shadow-Kopie
Wenn deine Liste sortiert ist, können Sie der folgenden Vorgehensweise zur Iteration über Sie überspringen die wiederholten Werte. Dies ist besonders nützlich zum behandeln große Listen mit niedrigen Speicherverbrauch umgehen die Kosten für den Bau eines
dict
oder eineset
:Dann:
Den Ausgang wird sein:
1 3 5 6