Gibt es eine integrierte Funktion, die Duplikate aus der Liste in Python entfernt und gleichzeitig die Reihenfolge beibehält? Ich weiß, dass ich ein Set verwenden kann, um Duplikate zu entfernen, aber das zerstört die ursprüngliche Reihenfolge. Ich weiß auch, dass ich meine eigenen so rollen kann:
def uniq(input):
output = []
for x in input:
if x not in output:
output.append(x)
return output
(Vielen Dank an Unwind für dieses Codebeispiel .)
Aber ich würde gerne, wenn möglich, eine eingebaute oder eine pythonischere Sprache verwenden.
quelle
seen.add
könnte sich zwischen den Iterationen geändert haben, und die Laufzeit ist nicht intelligent genug, um dies auszuschließen. Um auf Nummer sicher zu gehen, muss das Objekt jedes Mal überprüft werden. - Wenn Sie sich den Bytecode mit ansehendis.dis(f)
, können Sie sehen, dass er bei jeder IterationLOAD_ATTR
für dasadd
Mitglied ausgeführt wird. ideone.com/tz1Tllseen_add
ist eine Verbesserung, aber das Timing kann zu diesem Zeitpunkt von den Systemressourcen beeinflusst werden. Würde interessiert sein, volleseen_add = seen.add
ergibt nur eine Geschwindigkeitssteigerung von 1%. Es ist kaum von Bedeutung.Bearbeiten Sie 2016
Wie Raymond betonte, ist in Python 3.5+, wo
OrderedDict
es in C implementiert ist, der Listenverständnisansatz langsamer alsOrderedDict
(es sei denn, Sie benötigen die Liste am Ende tatsächlich - und selbst dann nur, wenn die Eingabe sehr kurz ist). Die beste Lösung für 3.5+ ist alsoOrderedDict
.Wichtige Bearbeitung 2015
Wie @abarnert bemerkt, enthält die
more_itertools
library (pip install more_itertools
) eineunique_everseen
Funktion, die dieses Problem ohne unlesbare (not seen.add
) Mutationen im Listenverständnis lösen soll . Dies ist auch die schnellste Lösung:Nur ein einfacher Bibliotheksimport und keine Hacks. Dies ergibt sich aus einer Implementierung des itertools-Rezepts,
unique_everseen
die wie folgt aussieht:In Python wird
2.7+
dasakzeptierte allgemeine Idiom(das funktioniert, aber nicht auf Geschwindigkeit optimiert ist, würde ich jetzt verwendenunique_everseen
) für Folgendes verwendetcollections.OrderedDict
:Laufzeit: O (N)
Das sieht viel schöner aus als:
und nutzt den hässlichen Hack nicht :
Dies beruht auf der Tatsache, dass
set.add
es sich um eine In-Place-Methode handelt, die immerNone
sonot None
auswertetTrue
.Beachten Sie jedoch, dass die Hack-Lösung eine höhere Geschwindigkeit aufweist, obwohl sie dieselbe Laufzeitkomplexität O (N) aufweist.
quelle
[seen.add(x) for x in seq if x not in seen]
Sie einfach Nebenwirkungen und tun Sie dies , oder wenn Sie das Verständnis von Nebenwirkungen nicht mögen, verwenden Sie einfach einefor
Schleife:for x in seq: seen.add(x) if x not in seen else None
(immer noch ein Einzeiler, obwohl ich in diesem Fall denke, dass Einzeiler eine dumme Eigenschaft ist, die Sie in einem versuchen sollten Lösung.seen = set(seq)
.In Python 2.7 ist die neue Methode zum Entfernen von Duplikaten aus einer iterierbaren Datei, während die ursprüngliche Reihenfolge beibehalten wird:
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:
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:
Antwort auf @max: Wenn Sie zu 3.6 oder 3.7 wechseln und anstelle von OrderedDict das reguläre Diktat verwenden , können Sie die Leistung auf keine andere Weise übertreffen. Das Wörterbuch ist dicht und kann ohne großen Aufwand problemlos in eine Liste konvertiert werden. Die Zielliste ist auf len (d) vorab dimensioniert, wodurch alle Größenänderungen gespeichert werden, die in einem Listenverständnis auftreten. Da die interne Schlüsselliste dicht ist, ist das Kopieren der Zeiger als Listenkopie fast schnell.
quelle
OrderedDict
am Ende nicht in eine Liste konvertiere . Wenn ich es in eine Liste konvertieren muss, ist der Listenverständnisansatz für kleine Eingaben immer noch bis zu 1,5-mal schneller. Trotzdem ist diese Lösung viel sauberer.set()
System naiveren Benutzern helfen, reproduzierbare Codes zu entwickeln.einzigartig →
['1', '2', '3', '6', '4', '5']
quelle
n^2
None
Referenzliste im Prozess!)for
stattdessen einfach eine SchleifeEin totes Pferd nicht 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 recht schnell und absolut einfach zu bedienen ist.
quelle
Die Liste muss nicht einmal sortiert werden , die ausreichende Bedingung ist, dass gleiche Werte zusammengefasst werden.
Bearbeiten: Ich habe angenommen, dass "Reihenfolge beibehalten" impliziert, dass die Liste tatsächlich sortiert ist. Ist dies nicht der Fall, ist die Lösung von MizardX die richtige.
Community-Bearbeitung: Dies ist jedoch die eleganteste Methode, um "doppelte aufeinanderfolgende Elemente zu einem einzigen Element zu komprimieren".
quelle
Ich denke, wenn Sie die Ordnung aufrechterhalten wollen,
Sie können dies versuchen:
ODER ähnlich können Sie dies tun:
Sie können dies auch tun:
Es kann auch so geschrieben werden:
quelle
In Python 3.7 und höher merken sich Wörterbücher garantiert ihre Reihenfolge beim Einfügen von Schlüsseln. Die Antwort auf diese Frage fasst den aktuellen Stand der Dinge zusammen.
Die
OrderedDict
Lösung ist somit veraltet und ohne Importanweisungen können wir einfach Folgendes ausgeben:quelle
Für eine weitere sehr späte Antwort auf eine andere sehr alte Frage:
Die
itertools
Rezepte haben eine Funktion, die dies unter Verwendung derseen
eingestellten Technik tut , aber:key
.seen.add
anstatt sie N-mal nachzuschlagen. (f7
tut dies auch, aber einige Versionen nicht.)ifilterfalse
, sodass Sie statt aller nur die eindeutigen Elemente in Python durchlaufen müssen. (Sie iterierenifilterfalse
natürlich immer noch über alle darin , aber das ist in C und viel schneller.)Ist es tatsächlich schneller als
f7
? Es hängt von Ihren Daten ab, also müssen Sie sie testen und sehen. Wenn Sie am Ende eine Liste möchten,f7
verwenden Sie eine Listcomp, und dies ist hier nicht möglich. (Sie können direktappend
anstattyield
ing, oder Sie können den Generator in die einspeisenlist
Funktion einspeisen, aber keiner kann so schnell sein wie LIST_APPEND in einem Listencomputer.) In jedem Fall wird es normalerweise nicht so sein, ein paar Mikrosekunden herauszudrücken Wichtig ist eine leicht verständliche, wiederverwendbare, bereits geschriebene Funktion, für die beim Dekorieren keine DSU erforderlich ist.Wie bei allen Rezepten ist es auch in erhältlich
more-iterools
.Wenn Sie nur den
key
Fall haben möchten , können Sie ihn wie folgt vereinfachen:quelle
more-itertools
dies eindeutig die beste Antwort ist. Ein einfacherfrom more_itertools import unique_everseen
list(unique_everseen(items))
Ansatz viel schneller als meiner und viel besser als die akzeptierte Antwort. Ich denke, der Download der Bibliothek lohnt sich. Ich gehe zu Community Wiki meine Antwort und füge diese hinzu.Nur um ein weiteres (sehr performante) Umsetzung einer solchen Funktionalität von einem externen Modul hinzuzufügen 1 :
iteration_utilities.unique_everseen
:Timings
Ich habe einige Timings (Python 3.6) und diese zeigen , dass es schneller als alle anderen Alternativen , die ich getestet wurden, einschließlich
OrderedDict.fromkeys
,f7
undmore_itertools.unique_everseen
:Und nur um sicherzugehen, dass ich auch einen Test mit mehr Duplikaten durchgeführt habe, um zu überprüfen, ob es einen Unterschied macht:
Und einer, der nur einen Wert enthält:
In all diesen Fällen ist die
iteration_utilities.unique_everseen
Funktion am schnellsten (auf meinem Computer).Diese
iteration_utilities.unique_everseen
Funktion kann auch nicht verwertbare Werte in der Eingabe verarbeiten (jedoch mit einerO(n*n)
Leistung anstelle derO(n)
Leistung, wenn die Werte hashbar sind).1 Haftungsausschluss: Ich bin der Autor dieses Pakets.
quelle
seen_add = seen.add
- Wird dies für die Benchmarks benötigt?dict.fromkeys()
Methode bitte Ihrem Diagramm hinzufügen ?ordereddict.fromkeys
?Für keine Hash-Typen (z. B. Liste von Listen), basierend auf MizardX:
quelle
nub
Dies wäre ein rekursiver Ansatz, wenn man die rekursive Idee übernimmt, die bei der Definition der Haskell- Funktion für Listen verwendet wird:z.B:
Ich habe es versucht, um die Datengröße zu erhöhen, und habe eine sublineare Zeitkomplexität festgestellt (nicht endgültig, schlägt aber vor, dass dies für normale Daten in Ordnung sein sollte).
Ich finde es auch interessant, dass dies durch andere Operationen leicht auf die Einzigartigkeit verallgemeinert werden kann. So was:
Sie könnten beispielsweise eine Funktion übergeben, die den Begriff der Rundung auf dieselbe Ganzzahl verwendet, als wäre sie aus Gründen der Eindeutigkeit "Gleichheit":
Dann würde unique (some_list, test_round) die eindeutigen Elemente der Liste bereitstellen, bei denen Eindeutigkeit nicht mehr die traditionelle Gleichheit bedeutet (was durch die Verwendung eines satzbasierten oder diktschlüsselbasierten Ansatzes für dieses Problem impliziert wird), sondern stattdessen beabsichtigt ist nur das erste Element, das für jede mögliche ganze Zahl K, auf die die Elemente runden könnten, auf K gerundet wird, z.
quelle
filter
kaum vom vorherigen Aufruf profitiert. Wenn jedoch die Anzahl der eindeutigen Elemente im Verhältnis zur Arraygröße gering ist, sollte dies ziemlich gut funktionieren.5 x schneller reduzieren Variante aber anspruchsvoller
Erläuterung:
quelle
Sie können auf ein Listenverständnis verweisen, während es mit dem Symbol '_ [1]' erstellt wird.
Mit der folgenden Funktion wird beispielsweise eine Liste von Elementen eindeutig, ohne ihre Reihenfolge zu ändern, indem auf das Listenverständnis verwiesen wird.
Demo:
Ausgabe:
quelle
Die Antwort von MizardX bietet eine gute Sammlung mehrerer Ansätze.
Das habe ich mir ausgedacht, als ich laut nachgedacht habe:
quelle
O(n)
Operation ist und Sie sie für jedes Element ausführen, ergibt sich die Komplexität Ihrer LösungO(n^2)
. Dies ist für solch ein triviales Problem einfach nicht akzeptabel.Hier ist eine einfache Möglichkeit, dies zu tun:
das gibt die Ausgabe:
quelle
Sie könnten eine Art hässlichen Listenverständnis-Hack machen.
quelle
i,e in enumerate(l)
zul[i] for i in range(len(l))
.Relativ wirksamer Ansatz mit
_sorted_
einemnumpy
Arrays:Ausgänge:
quelle
Ein Generatorausdruck, der die O (1) -Suche einer Menge verwendet, um zu bestimmen, ob ein Element in die neue Liste aufgenommen werden soll oder nicht.
quelle
extend
mit einem Generatorausdruck, der von der zu erweiternden Sache abhängt (also +1), aberset(n)
in jeder Phase (die linear ist) neu berechnet wird, und dies stößt den Gesamtansatz an, quadratisch zu sein. In der Tat ist dies mit ziemlicher Sicherheit schlimmer als nur zu verwendenele in n
. Das Erstellen eines Sets für einen einzelnen Mitgliedschaftstest ist die Kosten für die Set-Erstellung nicht wert. Trotzdem - es ist ein interessanter Ansatz.Eine einfache rekursive Lösung:
quelle
Entfernen Sie die doppelten Werte in einer Sequenz, behalten Sie jedoch die Reihenfolge der verbleibenden Elemente bei. Verwendung der Allzweckgeneratorfunktion.
quelle
Pandas Benutzer sollten auschecken
pandas.unique
.Die Funktion gibt ein NumPy-Array zurück. Bei Bedarf können Sie es mit der
tolist
Methode in eine Liste konvertieren .quelle
Wenn Sie einen Liner benötigen, hilft dies möglicherweise:
... sollte funktionieren, aber mich korrigieren, wenn ich falsch liege
quelle
Wenn Sie routinemäßig verwenden
pandas
und Ästhetik der Leistung vorgezogen wird, sollten Sie die integrierte Funktion in Betracht ziehenpandas.Series.drop_duplicates
:Zeitliche Koordinierung:
quelle
Dadurch bleibt die Reihenfolge erhalten und es wird in O (n) Zeit ausgeführt. Grundsätzlich besteht die Idee darin, überall dort, wo ein Duplikat gefunden wird, ein Loch zu erstellen und es auf den Boden zu senken. verwendet einen Lese- und Schreibzeiger. Wenn ein Duplikat gefunden wird, rückt nur der Lesezeiger vor und der Schreibzeiger bleibt auf dem Duplikateintrag, um es zu überschreiben.
quelle
Eine Lösung ohne importierte Module oder Sets:
Gibt Ausgabe:
quelle
Eine In-Place-Methode
Diese Methode ist quadratisch, da wir für jedes Element der Liste eine lineare Suche in der Liste haben (dazu müssen wir die Kosten für die Neuanordnung der Liste aufgrund der hinzufügen
del
s ).Das heißt, es ist möglich, an Ort und Stelle zu arbeiten, wenn wir am Ende der Liste beginnen und zum Ursprung gehen und jeden Begriff entfernen, der in der Unterliste links davon vorhanden ist
Diese Idee im Code ist einfach
Ein einfacher Test der Implementierung
quelle
l[:] = <one of the the faster methods>
wenn Sie eine In-Place-Operation wünschen, nein?a=[1]; b=a; a[:]=[2]
ist derb==[2]
WertTrue
und wir können sagen, dass wir es an Ort und Stelle tun. Sie schlagen jedoch vor, neuen Speicherplatz für eine neue Liste zu verwenden, die alten Daten durch die neuen Daten zu ersetzen und die zu markieren alte Daten für die Speicherbereinigung, weil von nichts mehr referenziert wird. Wenn Sie also sagen, dass sie an Ort und Stelle funktionieren, wird das Konzept ein wenig erweitert, was ich gezeigt habe, dass es möglich ist ... ist es ineffizient? ja, aber das habe ich vorher gesagt.Der Ansatz von zmk verwendet ein Listenverständnis, das sehr schnell ist und dennoch die Reihenfolge auf natürliche Weise beibehält. Zum Anwenden auf Zeichenfolgen mit Groß- und Kleinschreibung kann es leicht geändert werden. Dadurch bleibt auch der ursprüngliche Fall erhalten.
Eng verbundene Funktionen sind:
quelle
Verständnis einer Einzeilerliste:
Fügen Sie einfach eine Bedingung hinzu, um zu überprüfen, ob sich der Wert nicht an einer vorherigen Position befindet
quelle