Wie entfernen Sie Duplikate aus einer Liste, während Sie die Reihenfolge beibehalten?

770

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.

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

Josh Glover
quelle

Antworten:

762

Hier haben Sie einige Alternativen: http://www.peterbe.com/plog/uniqifiers-benchmark

Schnellste:

def f7(seq):
    seen = set()
    seen_add = seen.add
    return [x for x in seq if not (x in seen or seen_add(x))]

Warum zuweisen seen.add, seen_addanstatt nur anzurufen seen.add? Python ist eine dynamische Sprache, und das Auflösen seen.addjeder Iteration ist teurer als das Auflösen einer lokalen Variablen. seen.addkö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 diese Funktion häufig für denselben Datensatz verwenden möchten, ist ein bestellter Satz möglicherweise besser geeignet : http://code.activestate.com/recipes/528878/

O (1) Einfügen, Löschen und Überprüfen der Mitglieder pro Operation.

(Kleiner zusätzlicher Hinweis: seen.add()Gibt immer zurück None, daher gibt es das oroben Genannte nur als Möglichkeit, ein Set-Update zu versuchen, und nicht als integralen Bestandteil des logischen Tests.)

Markus Jarderot
quelle
20
@JesseDhillon seen.addkö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 ansehen dis.dis(f), können Sie sehen, dass er bei jeder Iteration LOAD_ATTRfür das addMitglied ausgeführt wird. ideone.com/tz1Tll
Markus Jarderot
5
Wenn ich dies auf einer Liste von Listen versuche, erhalte ich: TypeError: unhashable type: 'list'
Jens Timmerman
7
Ihre Lösung ist nicht die schnellste. In Python 3 (hat Test 2 nicht getestet) ist dies schneller (Liste mit 300.000 Einträgen - 0,045 Sekunden (Ihre) gegenüber 0,035 Sekunden (diese Liste): found = set (); Geben Sie [x für x in Zeilen zurück, wenn x nicht gesehen wird und nicht see.add (x)]. Ich konnte keinen Geschwindigkeitseffekt der von Ihnen erstellten Linie "found_add" feststellen.
user136036
3
@ user136036 Bitte verlinken Sie zu Ihren Tests. Wie oft haben Sie sie ausgeführt? seen_addist eine Verbesserung, aber das Timing kann zu diesem Zeitpunkt von den Systemressourcen beeinflusst werden. Würde interessiert sein, volle
Zeiten
2
Für jeden, der Python-Code schreibt, sollten Sie wirklich zweimal überlegen, bevor Sie die Lesbarkeit und die allgemein vereinbarten Python-Konventionen opfern, um ein paar Nanosekunden mehr pro Schleife herauszuholen. Testen mit und ohne seen_add = seen.addergibt nur eine Geschwindigkeitssteigerung von 1%. Es ist kaum von Bedeutung.
Sleblanc
343

Bearbeiten Sie 2016

Wie Raymond betonte, ist in Python 3.5+, wo OrderedDictes in C implementiert ist, der Listenverständnisansatz langsamer als OrderedDict(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 also OrderedDict.

Wichtige Bearbeitung 2015

Wie @abarnert bemerkt, enthält die more_itertoolslibrary ( pip install more_itertools) eine unique_everseenFunktion, die dieses Problem ohne unlesbare ( not seen.add) Mutationen im Listenverständnis lösen soll . 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. Dies ergibt sich aus einer Implementierung des itertools-Rezepts, unique_everseendie wie folgt aussieht:

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

In Python wird 2.7+das akzeptierte allgemeine Idiom (das funktioniert, aber nicht auf Geschwindigkeit optimiert ist, würde ich jetzt verwenden unique_everseen) für Folgendes verwendet collections.OrderedDict:

Laufzeit: O (N)

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

Das sieht viel schöner aus als:

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

und nutzt den hässlichen Hack nicht :

not seen.add(x)

Dies beruht auf der Tatsache, dass set.addes sich um eine In-Place-Methode handelt, die immer Noneso not Noneauswertet True.

Beachten Sie jedoch, dass die Hack-Lösung eine höhere Geschwindigkeit aufweist, obwohl sie dieselbe Laufzeitkomplexität O (N) aufweist.

Jamylak
quelle
5
Zu einem benutzerdefinierten Diktat konvertieren, nur um Schlüssel zu nehmen? Nur eine weitere Krücke.
Nakilon
3
@ Nakilon Ich sehe nicht wirklich, wie es eine Krücke ist. Es legt keinen veränderlichen Zustand offen, daher ist es in diesem Sinne sehr sauber. Intern werden Python-Sets mit dict () ( stackoverflow.com/questions/3949310/… ) implementiert , sodass Sie im Grunde nur das tun, was der Interpreter sowieso getan hätte.
Imran
Verwenden [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 eine forSchleife: 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.
ely
@EMS Das bewahrt die Ordnung nicht. Sie könnten es genauso gut tun seen = set(seq).
Flornbeben
1
@CommuSoft Ich stimme zu, obwohl es praktisch fast immer O (n) ist, wegen des super höchst unwahrscheinlichen schlimmsten Falls
Jamylak
110

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']

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.

Raymond Hettinger
quelle
Es ist schneller als jeder andere Ansatz auf meinem Computer (Python 3.5) , solange ich OrderedDictam 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.
max
7
Das einzige Problem ist, dass die iterierbaren "Elemente" hashbar sein müssen - wäre schön, wenn ich das Äquivalent für iterable Elemente mit beliebigen Elementen (als Liste von Listen) hätte
Mr_and_Mrs_D
Die Iteration der Einfügereihenfolge über ein Diktat bietet Funktionen, die mehr Anwendungsfälle als das Entfernen von Duplikaten bedienen. Beispielsweise stützen sich wissenschaftliche Analysen auf reproduzierbare Berechnungen, die von der nicht deterministischen Diktation nicht unterstützt werden. Die Reproduzierbarkeit ist ein wichtiges aktuelles Ziel in der rechnergestützten wissenschaftlichen Modellierung. Daher begrüßen wir diese neue Funktion. Obwohl ich weiß, dass es trivial ist, mit einem deterministischen Diktat zu bauen, würde ein hochleistungsfähiges, deterministisches set()System naiveren Benutzern helfen, reproduzierbare Codes zu entwickeln.
Arthur
41
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']

Dansalmo
quelle
28
Es ist erwähnenswert, dass dies inn^2
Goncalopp
25
Ick. 2 Streiks: Verwenden einer Liste für Mitgliedschaftstests (langsam, O (N)) und Verwenden eines Listenverständnisses für die Nebenwirkungen (Erstellen einer weiteren NoneReferenzliste im Prozess!)
Martijn Pieters
1
Ich stimme @MartijnPieters zu, es gibt absolut keinen Grund für das Listenverständnis mit Nebenwirkungen. Verwenden Sie forstattdessen einfach eine Schleife
Jamylak
31

Ein 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.

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]
Alexander
quelle
27
from itertools import groupby
[ key for key,_ in groupby(sortedList)]

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".

Rafał Dowgird
quelle
1
Aber das bewahrt nicht die Ordnung!
1
Hrm, das ist problematisch, da ich nicht garantieren kann, dass gleiche Werte zusammengefasst werden, ohne die Liste einmal zu durchlaufen. Zu diesem Zeitpunkt hätte ich die Duplikate beschneiden können.
Josh Glover
Ich nahm an, dass "Ordnung bewahren" impliziert, dass die Liste tatsächlich geordnet ist.
Rafał Dowgird
1
Vielleicht ist die Spezifikation der Eingabeliste etwas unklar. Die Werte müssen nicht einmal gruppiert werden: [2, 1, 3, 1]. Welche Werte müssen also beibehalten und welche gelöscht werden?
1
@igorkf Das zweite Element des Paares (der Paare) wird ignoriert.
Rafał Dowgird
24

Ich denke, wenn Sie die Ordnung aufrechterhalten wollen,

Sie können dies versuchen:

list1 = ['b','c','d','b','c','a','a']    
list2 = list(set(list1))    
list2.sort(key=list1.index)    
print list2

ODER ähnlich können Sie dies tun:

list1 = ['b','c','d','b','c','a','a']  
list2 = sorted(set(list1),key=list1.index)  
print list2 

Sie können dies auch tun:

list1 = ['b','c','d','b','c','a','a']    
list2 = []    
for i in list1:    
    if not i in list2:  
        list2.append(i)`    
print list2

Es kann auch so geschrieben werden:

list1 = ['b','c','d','b','c','a','a']    
list2 = []    
[list2.append(i) for i in list1 if not i in list2]    
print list2 
Kleeblatt
quelle
3
Bei Ihren ersten beiden Antworten wird davon ausgegangen, dass die Reihenfolge der Liste mithilfe einer Sortierfunktion wiederhergestellt werden kann. Dies ist jedoch möglicherweise nicht der Fall.
Richard
5
Die meisten Antworten konzentrieren sich auf die Leistung. Für Listen, die nicht groß genug sind, um sich um die Leistung zu sorgen, ist die Sortierung (set (list1), key = list1.index) das Beste, was ich je gesehen habe. Kein zusätzlicher Import, keine zusätzliche Funktion, keine zusätzliche Variable, und es ist ziemlich einfach und lesbar.
Derek Veit
23

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 OrderedDictLösung ist somit veraltet und ohne Importanweisungen können wir einfach Folgendes ausgeben:

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

Für eine weitere sehr späte Antwort auf eine andere sehr alte Frage:

Die itertoolsRezepte haben eine Funktion, die dies unter Verwendung der seeneingestellten Technik tut , aber:

  • Behandelt einen Standard key .
  • Verwendet keine unpassenden Hacks.
  • Optimiert die Schleife durch Vorbindung, seen.addanstatt sie N-mal nachzuschlagen. (f7 tut dies auch, aber einige Versionen nicht.)
  • Optimiert die Schleife mithilfe von ifilterfalse, sodass Sie statt aller nur die eindeutigen Elemente in Python durchlaufen müssen. (Sie iterieren ifilterfalsenatü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, f7verwenden Sie eine Listcomp, und dies ist hier nicht möglich. (Sie können direkt appendanstatt yielding, 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 keyFall haben möchten , können Sie ihn wie folgt vereinfachen:

def unique(iterable):
    seen = set()
    seen_add = seen.add
    for element in itertools.ifilterfalse(seen.__contains__, iterable):
        seen_add(element)
        yield element
abarnert
quelle
Ich habe völlig übersehen, dass more-itertoolsdies eindeutig die beste Antwort ist. Ein einfacher from 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.
Jamylak
12

Nur um ein weiteres (sehr performante) Umsetzung einer solchen Funktionalität von einem externen Modul hinzuzufügen 1 : iteration_utilities.unique_everseen:

>>> from iteration_utilities import unique_everseen
>>> lst = [1,1,1,2,3,2,2,2,1,3,4]

>>> list(unique_everseen(lst))
[1, 2, 3, 4]

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, f7und more_itertools.unique_everseen:

%matplotlib notebook

from iteration_utilities import unique_everseen
from collections import OrderedDict
from more_itertools import unique_everseen as mi_unique_everseen

def f7(seq):
    seen = set()
    seen_add = seen.add
    return [x for x in seq if not (x in seen or seen_add(x))]

def iteration_utilities_unique_everseen(seq):
    return list(unique_everseen(seq))

def more_itertools_unique_everseen(seq):
    return list(mi_unique_everseen(seq))

def odict(seq):
    return list(OrderedDict.fromkeys(seq))

from simple_benchmark import benchmark

b = benchmark([f7, iteration_utilities_unique_everseen, more_itertools_unique_everseen, odict],
              {2**i: list(range(2**i)) for i in range(1, 20)},
              'list size (no duplicates)')
b.plot()

Geben Sie hier die Bildbeschreibung ein

Und nur um sicherzugehen, dass ich auch einen Test mit mehr Duplikaten durchgeführt habe, um zu überprüfen, ob es einen Unterschied macht:

import random

b = benchmark([f7, iteration_utilities_unique_everseen, more_itertools_unique_everseen, odict],
              {2**i: [random.randint(0, 2**(i-1)) for _ in range(2**i)] for i in range(1, 20)},
              'list size (lots of duplicates)')
b.plot()

Geben Sie hier die Bildbeschreibung ein

Und einer, der nur einen Wert enthält:

b = benchmark([f7, iteration_utilities_unique_everseen, more_itertools_unique_everseen, odict],
              {2**i: [1]*(2**i) for i in range(1, 20)},
              'list size (only duplicates)')
b.plot()

Geben Sie hier die Bildbeschreibung ein

In all diesen Fällen ist die iteration_utilities.unique_everseenFunktion am schnellsten (auf meinem Computer).


Diese iteration_utilities.unique_everseenFunktion kann auch nicht verwertbare Werte in der Eingabe verarbeiten (jedoch mit einer O(n*n)Leistung anstelle der O(n)Leistung, wenn die Werte hashbar sind).

>>> lst = [{1}, {1}, {2}, {1}, {3}]

>>> list(unique_everseen(lst))
[{1}, {2}, {3}]

1 Haftungsausschluss: Ich bin der Autor dieses Pakets.

MSeifert
quelle
Ich verstehe die Notwendigkeit für diese Zeile nicht: seen_add = seen.add- Wird dies für die Benchmarks benötigt?
Alex
@Alex Dies ist der in dieser Antwort angegebene Ansatz . Es wäre sinnvoller, es dort zu fragen. Ich habe nur den Ansatz aus dieser Antwort verwendet, um die Timings zu vergleichen.
MSeifert
Können Sie die dict.fromkeys()Methode bitte Ihrem Diagramm hinzufügen ?
Boris
Ich bin mir nicht sicher, ob ich das gleiche habe, um das Timing bald zu erledigen. Glaubst du, es ist viel schneller als das ordereddict.fromkeys?
MSeifert
"Diese Funktion iteration_utilities.unique_everseen kann auch nicht zerlegbare Werte in der Eingabe verarbeiten" - ja, das ist wirklich wichtig. Wenn Sie eine Liste von Diktaten von Diktaten von Diktaten usw. haben, ist dies die einzige Möglichkeit, die Arbeit zu erledigen, selbst in kleinem Maßstab.
Roko Mijic
6

Für keine Hash-Typen (z. B. Liste von Listen), basierend auf MizardX:

def f7_noHash(seq)
    seen = set()
    return [ x for x in seq if str( x ) not in seen and not seen.add( str( x ) )]
zmk
quelle
3

nubDies wäre ein rekursiver Ansatz, wenn man die rekursive Idee übernimmt, die bei der Definition der Haskell- Funktion für Listen verwendet wird:

def unique(lst):
    return [] if lst==[] else [lst[0]] + unique(filter(lambda x: x!= lst[0], lst[1:]))

z.B:

In [118]: unique([1,5,1,1,4,3,4])
Out[118]: [1, 5, 4, 3]

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).

In [122]: %timeit unique(np.random.randint(5, size=(1)))
10000 loops, best of 3: 25.3 us per loop

In [123]: %timeit unique(np.random.randint(5, size=(10)))
10000 loops, best of 3: 42.9 us per loop

In [124]: %timeit unique(np.random.randint(5, size=(100)))
10000 loops, best of 3: 132 us per loop

In [125]: %timeit unique(np.random.randint(5, size=(1000)))
1000 loops, best of 3: 1.05 ms per loop

In [126]: %timeit unique(np.random.randint(5, size=(10000)))
100 loops, best of 3: 11 ms per loop

Ich finde es auch interessant, dass dies durch andere Operationen leicht auf die Einzigartigkeit verallgemeinert werden kann. So was:

import operator
def unique(lst, cmp_op=operator.ne):
    return [] if lst==[] else [lst[0]] + unique(filter(lambda x: cmp_op(x, lst[0]), lst[1:]), cmp_op)

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":

def test_round(x,y):
    return round(x) != round(y)

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.

In [6]: unique([1.2, 5, 1.9, 1.1, 4.2, 3, 4.8], test_round)
Out[6]: [1.2, 5, 1.9, 4.2, 3]
ely
quelle
1
Beachten Sie, dass die Leistung schlecht wird, wenn die Anzahl der eindeutigen Elemente im Verhältnis zur Gesamtzahl der Elemente sehr groß ist, da die Verwendung jedes aufeinanderfolgenden rekursiven Aufrufs filterkaum vom vorherigen Aufruf profitiert. Wenn jedoch die Anzahl der eindeutigen Elemente im Verhältnis zur Arraygröße gering ist, sollte dies ziemlich gut funktionieren.
Ely
3

5 x schneller reduzieren Variante aber anspruchsvoller

>>> l = [5, 6, 6, 1, 1, 2, 2, 3, 4]
>>> 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())
# use 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]
[5, 6, 1, 2, 3, 4]
Sergey M Nikitin
quelle
3

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.

def unique(my_list): 
    return [x for x in my_list if x not in locals()['_[1]']]

Demo:

l1 = [1, 2, 3, 4, 1, 2, 3, 4, 5]
l2 = [x for x in l1 if x not in locals()['_[1]']]
print l2

Ausgabe:

[1, 2, 3, 4, 5]
Zhifeng Hu
quelle
2
Beachten Sie auch, dass dies zu einer O (n ^ 2) -Operation führen würde, bei der das Erstellen eines Satzes / Diktats (mit konstanter Nachschlagezeit) und das Hinzufügen nur zuvor nicht sichtbarer Elemente linear sind.
ely
Dies ist Python 2.6, nur ich glaube. Und ja, es ist O (N ^ 2)
Jamylak
2

Die Antwort von MizardX bietet eine gute Sammlung mehrerer Ansätze.

Das habe ich mir ausgedacht, als ich laut nachgedacht habe:

mylist = [x for i,x in enumerate(mylist) if x not in mylist[i+1:]]
Saurabh Hirani
quelle
Ihre Lösung ist nett, aber es dauert das letzte Erscheinungsbild jedes Elements. Um den ersten Auftritt zu machen, verwenden Sie: [x für i, x in Aufzählung (mylist), wenn x nicht in mylist [: i]]
Rivka
7
Da das Suchen in einer Liste eine O(n)Operation ist und Sie sie für jedes Element ausführen, ergibt sich die Komplexität Ihrer Lösung O(n^2). Dies ist für solch ein triviales Problem einfach nicht akzeptabel.
Nikita Volkov
2

Hier ist eine einfache Möglichkeit, dies zu tun:

list1 = ["hello", " ", "w", "o", "r", "l", "d"]
sorted(set(list1 ), key=lambda x:list1.index(x))

das gibt die Ausgabe:

["hello", " ", "w", "o", "r", "l", "d"]
Ahmed4end
quelle
1

Sie könnten eine Art hässlichen Listenverständnis-Hack machen.

[l[i] for i in range(len(l)) if l.index(l[i]) == i]

quelle
Bevorzugen i,e in enumerate(l)zu l[i] for i in range(len(l)).
Evpok
1

Relativ wirksamer Ansatz mit _sorted_einem numpyArrays:

b = np.array([1,3,3, 8, 12, 12,12])    
numpy.hstack([b[0], [x[0] for x in zip(b[1:], b[:-1]) if x[0]!=x[1]]])

Ausgänge:

array([ 1,  3,  8, 12])
dominecf
quelle
1
l = [1,2,2,3,3,...]
n = []
n.extend(ele for ele in l if ele not in set(n))

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.

kylie.a
quelle
1
Clevere Verwendung extendmit einem Generatorausdruck, der von der zu erweiternden Sache abhängt (also +1), aber set(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 verwenden ele 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.
John Coleman
1

Eine einfache rekursive Lösung:

def uniquefy_list(a):
    return uniquefy_list(a[1:]) if a[0] in a[1:] else [a[0]]+uniquefy_list(a[1:]) if len(a)>1 else [a[0]]
Ilya Prokin
quelle
1

Entfernen Sie die doppelten Werte in einer Sequenz, behalten Sie jedoch die Reihenfolge der verbleibenden Elemente bei. Verwendung der Allzweckgeneratorfunktion.

# for hashable sequence
def remove_duplicates(items):
    seen = set()
    for item in items:
        if item not in seen:
            yield item
            seen.add(item)

a = [1, 5, 2, 1, 9, 1, 5, 10]
list(remove_duplicates(a))
# [1, 5, 2, 9, 10]



# for unhashable sequence
def remove_duplicates(items, key=None):
    seen = set()
    for item in items:
        val = item if key is None else key(item)
        if val not in seen:
            yield item
            seen.add(val)

a = [ {'x': 1, 'y': 2}, {'x': 1, 'y': 3}, {'x': 1, 'y': 2}, {'x': 2, 'y': 4}]
list(remove_duplicates(a, key=lambda d: (d['x'],d['y'])))
# [{'x': 1, 'y': 2}, {'x': 1, 'y': 3}, {'x': 2, 'y': 4}]
Srivastava
quelle
1

Pandas Benutzer sollten auschecken pandas.unique.

>>> import pandas as pd
>>> lst = [1, 2, 1, 3, 3, 2, 4]
>>> pd.unique(lst)
array([1, 2, 3, 4])

Die Funktion gibt ein NumPy-Array zurück. Bei Bedarf können Sie es mit der tolistMethode in eine Liste konvertieren .

timgeb
quelle
1
Schön. Ich würde mir nie vorstellen, Pandas dafür zu verwenden, aber es funktioniert
seralouk vor
0

Wenn Sie einen Liner benötigen, hilft dies möglicherweise:

reduce(lambda x, y: x + y if y[0] not in x else x, map(lambda x: [x],lst))

... sollte funktionieren, aber mich korrigieren, wenn ich falsch liege

Code22
quelle
Es ist ein bedingter Ausdruck, also ist es gut
Code22
0

Wenn Sie routinemäßig verwenden pandasund Ästhetik der Leistung vorgezogen wird, sollten Sie die integrierte Funktion in Betracht ziehen pandas.Series.drop_duplicates:

    import pandas as pd
    import numpy as np

    uniquifier = lambda alist: pd.Series(alist).drop_duplicates().tolist()

    # from the chosen answer 
    def f7(seq):
        seen = set()
        seen_add = seen.add
        return [ x for x in seq if not (x in seen or seen_add(x))]

    alist = np.random.randint(low=0, high=1000, size=10000).tolist()

    print uniquifier(alist) == f7(alist)  # True

Zeitliche Koordinierung:

    In [104]: %timeit f7(alist)
    1000 loops, best of 3: 1.3 ms per loop
    In [110]: %timeit uniquifier(alist)
    100 loops, best of 3: 4.39 ms per loop
Lei
quelle
0

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.

def deduplicate(l):
    count = {}
    (read,write) = (0,0)
    while read < len(l):
        if l[read] in count:
            read += 1
            continue
        count[l[read]] = True
        l[write] = l[read]
        read += 1
        write += 1
    return l[0:write]
Soham Joshi
quelle
0

Eine Lösung ohne importierte Module oder Sets:

text = "ask not what your country can do for you ask what you can do for your country"
sentence = text.split(" ")
noduplicates = [(sentence[i]) for i in range (0,len(sentence)) if sentence[i] not in sentence[:i]]
print(noduplicates)

Gibt Ausgabe:

['ask', 'not', 'what', 'your', 'country', 'can', 'do', 'for', 'you']
Rob Murray
quelle
Dies ist jedes Mal O (N ** 2) Komplexität + Listenaufteilung.
Jean-François Fabre
0

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

for i in range(len(l)-1,0,-1): 
    if l[i] in l[:i]: del l[i] 

Ein einfacher Test der Implementierung

In [91]: from random import randint, seed                                                                                            
In [92]: seed('20080808') ; l = [randint(1,6) for _ in range(12)] # Beijing Olympics                                                                 
In [93]: for i in range(len(l)-1,0,-1): 
    ...:     print(l) 
    ...:     print(i, l[i], l[:i], end='') 
    ...:     if l[i] in l[:i]: 
    ...:          print( ': remove', l[i]) 
    ...:          del l[i] 
    ...:     else: 
    ...:          print() 
    ...: print(l)
[6, 5, 1, 4, 6, 1, 6, 2, 2, 4, 5, 2]
11 2 [6, 5, 1, 4, 6, 1, 6, 2, 2, 4, 5]: remove 2
[6, 5, 1, 4, 6, 1, 6, 2, 2, 4, 5]
10 5 [6, 5, 1, 4, 6, 1, 6, 2, 2, 4]: remove 5
[6, 5, 1, 4, 6, 1, 6, 2, 2, 4]
9 4 [6, 5, 1, 4, 6, 1, 6, 2, 2]: remove 4
[6, 5, 1, 4, 6, 1, 6, 2, 2]
8 2 [6, 5, 1, 4, 6, 1, 6, 2]: remove 2
[6, 5, 1, 4, 6, 1, 6, 2]
7 2 [6, 5, 1, 4, 6, 1, 6]
[6, 5, 1, 4, 6, 1, 6, 2]
6 6 [6, 5, 1, 4, 6, 1]: remove 6
[6, 5, 1, 4, 6, 1, 2]
5 1 [6, 5, 1, 4, 6]: remove 1
[6, 5, 1, 4, 6, 2]
4 6 [6, 5, 1, 4]: remove 6
[6, 5, 1, 4, 2]
3 4 [6, 5, 1]
[6, 5, 1, 4, 2]
2 1 [6, 5]
[6, 5, 1, 4, 2]
1 5 [6]
[6, 5, 1, 4, 2]

In [94]:                                                                                                                             
gboffi
quelle
Vor dem Posten habe ich die Antworten vergeblich nach "Ort" durchsucht. Wenn andere das Problem auf ähnliche Weise gelöst haben, benachrichtigen Sie mich bitte und ich werde meine Antwort so schnell wie möglich entfernen.
Gboffi
Sie könnten nur verwenden, l[:] = <one of the the faster methods>wenn Sie eine In-Place-Operation wünschen, nein?
Timgeb
@timgeb Ja und nein ... Wenn ich das tue, a=[1]; b=a; a[:]=[2]ist der b==[2]Wert Trueund 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.
gboffi
0

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.

def DelDupes(aseq) :
    seen = set()
    return [x for x in aseq if (x.lower() not in seen) and (not seen.add(x.lower()))]

Eng verbundene Funktionen sind:

def HasDupes(aseq) :
    s = set()
    return any(((x.lower() in s) or s.add(x.lower())) for x in aseq)

def GetDupes(aseq) :
    s = set()
    return set(x for x in aseq if ((x.lower() in s) or s.add(x.lower())))
Hewey Dewey
quelle
0

Verständnis einer Einzeilerliste:

values_non_duplicated = [value for index, value in enumerate(values) if value not in values[ : index]]

Fügen Sie einfach eine Bedingung hinzu, um zu überprüfen, ob sich der Wert nicht an einer vorherigen Position befindet

Jože Ws
quelle