Wie entfernen Sie Duplikate aus einer Liste, während um die Erhaltung?

https://stackoverflow.com/questions/480214

20-08-2019
|

Frage

Gibt es eine eingebaute in den Duplikate aus der Liste in Python entfernt, während um die Erhaltung? Ich weiß, dass ich eine Menge Duplikate entfernen kann, aber das zerstört die ursprüngliche Reihenfolge. Ich weiß auch, dass ich meine eigenen wie diese rollen kann:

def uniq(input):
  output = []
  for x in input:
    if x not in output:
      output.append(x)
  return output

(Dank für das Entspannen Codebeispiel .)

Aber ich mag mich von einem eingebauten in Anspruch zu nehmen oder ein Pythonic Idiom, wenn möglich.

Lösung

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

Fasten ein:

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 assign seen.add seen_add statt seen.add nur anrufen? Python ist eine dynamische Sprache, und jede Iteration seen.add Lösung ist teurer als eine lokale Variable zu lösen. seen.add könnte zwischen Iterationen geändert, und die Laufzeit ist nicht intelligent genug, dass auszuschließen. Um sicher, es hat die Aufgabe, jedes Mal zu überprüfen.

Wenn Sie mit dieser Funktion eine Menge auf dem gleichen Datenbestand planen, vielleicht würden Sie mit einem geordneten Satz besser dran: http://code.activestate.com/recipes/528878/

O (1) Insertion, Deletion und Mitglied Prüfung pro Operation.

(Small zusätzliche Anmerkung:. seen.add() immer None zurückkehrt, so dass die or oben gibt es nur als eine Möglichkeit, eine Reihe Update, um zu versuchen, und nicht als integralen Bestandteil des logischen Tests)

Andere Tipps

Bearbeiten 2016

Wie Raymond wies darauf hin, in Python 3.5 und höher, wo OrderedDict in C implementiert ist, wird die Liste Verständnis Ansatz langsamer als OrderedDict (es sei denn, Sie tatsächlich die Liste am Ende müssen - und auch dann nur, wenn der Eingang ist sehr kurz). So ist die beste Lösung für 3.5+ ist OrderedDict.

Wichtig Bearbeiten 2015

Wie @abarnert Notizen, die more_itertools Bibliothek (pip install more_itertools) enthält eine unique_everseen das 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 2.7+ den ~~akzeptiert gemeinsames Idiom~~ (das funktioniert, ist aber nicht auf Geschwindigkeit optimiert, würde ich jetzt unique_everseen ) für diese 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 als:

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

und nicht verwenden, um den hässlichen Hack :

not seen.add(x)

, die auf der Tatsache beruht, dass set.add ist ein In-Place-Verfahren, das immer wieder None so not None True auswertet.

Beachten Sie jedoch, dass die Hack-Lösung ist in roher Geschwindigkeit schneller, obwohl es die gleiche Laufzeitkomplexität O (N) hat.

In Python 2.7 , die neuen Duplikate aus einer abzählbaren zu entfernen, während es in der ursprünglichen Reihenfolge zu halten ist:

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

In Python 3.5 , hat die OrderedDict eine C-Implementierung. Meine Timings zeigen, dass dies nun sowohl die schnellste und kürzeste der verschiedenen Ansätze für Python 3.5.

In Python 3.6 , wurde die regelmäßige dict bestellen und kompakt. (Diese Funktion ist gilt für CPython und PyPy kann aber nicht in anderen Implementierungen). Das gibt uns einen neuen schnellsten Weg von deduping während Ordnung halten:

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

In Python 3.7 ist die regelmäßige dict sowohl über alle Implementierungen bestellt garantiert. So ist die kürzeste und schnellste Lösung ist:

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

Antwort auf @Max: Sobald Sie auf 3.6 oder 3.7 verwenden, regelmäßige dict statt bewegen OrderedDict , kann man nicht wirklich die Leistung auf andere Weise verloren. Das Wörterbuch ist dicht und wandelt leicht in eine Liste mit fast keinem Aufwand. Die Zielliste ist pre-Größe zu len (d), die alle Größenänderungen speichert, die in einer Liste Verständnis auftreten. Da auch die interne Schlüsselliste ist dicht, die Zeiger zu kopieren ist über fast schnell als Liste kopieren.

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

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

from itertools import groupby
[ key for key,_ in groupby(sortedList)]

Die Liste nicht einmal sein muß sortieren ist die hinreichende Bedingung, dass gleiche Werte gruppiert werden.

Edit: Ich nahm an, dass „die Erhaltung Ordnung“ bedeutet, dass die Liste tatsächlich bestellt wird. Ist dies nicht der Fall ist, dann wird die Lösung von MizardX ist die richtige.

Community bearbeiten: Dies ist jedoch die eleganteste Art und Weise zu „komprimieren doppelte aufeinanderfolgende Elemente in einem einzigen Element“

Nicht ein totes Pferd zu treten (diese Frage ist sehr alt und hat schon viele gute Antworten), aber hier ist eine Lösung Pandas verwenden, die in vielen Fällen recht schnell und ist tot einfach zu bedienen.

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]

Ich denke, wenn Sie den Auftrag will halten,

Sie können versuchen, diese:

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

oder auf ähnliche Weise 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 als dies 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

Just fügen Sie eine weitere (sehr performant) Umsetzung einer solchen Funktionalität von einem externen Modul ¹: 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, darunter OrderedDict.fromkeys, f7 und 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()

Und nur, um sicherzustellen, ich habe auch einen Test mit mehr Duplikaten nur 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()

Und man nur einen Wert enthalten:

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

In all diesen Fällen sind die iteration_utilities.unique_everseen Funktion ist die schnellste (auf meinem Computer).

Diese iteration_utilities.unique_everseen Funktion kann auch unhashable Werte im Eingabe-Griff (jedoch mit einer O(n*n) Leistung anstelle der O(n) Leistung, wenn die Werte hashable).

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

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

¹ Disclaimer:. Ich bin der Autor dieses Pakets

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

Die itertools Rezepte eine Funktion haben, das dies tut, die seen Set-Technik , aber:

Verarbeitet Standard key Funktion.
Benutzt keine ungebührlichen Hacks.
Optimiert die Schleife durch Pre-Bindung seen.add statt suchen sie auf N-mal. (f7 auch tut dies, aber einige Versionen nicht.)
Optimiert die Schleife durch ifilterfalse verwenden, so dass Sie nur eine Schleife über die einzigartigen Elemente in Python haben, statt sie alle. (Sie noch laufen alle von ihnen in ifilterfalse, natürlich, aber das ist in C, und viel schneller.)

Ist es tatsächlich schneller als f7? Es hängt von Ihren Daten, so dass Sie es nicht getestet zu werden und sehen. Wenn Sie eine Liste am Ende wollen, verwendet f7 eine listcomp, und es gibt keine Möglichkeit, das hier zu tun. (Sie können direkt statt appending yield, oder Sie können den Generator in die list Funktion füttern, aber keiner kann so schnell wie der LIST_APPEND in einem listcomp sein.) Auf jeden Fall in der Regel ein paar Mikrosekunden Auspressen wird nicht zu ebenso wichtig wie eine leicht verständliche, wiederverwendbar, bereits geschriebene Funktion, die DSU nicht erforderlich, wenn Sie dekorieren mögen.

Wie bei allen Rezepten, es ist auch in more-iterools .

Wenn Sie nur die nicht-key Fall wollen, können Sie vereinfachen es, wie:

def unique(iterable):
    seen = set()
    seen_add = seen.add
    for element in itertools.ifilterfalse(seen.__contains__, iterable):
        seen_add(element)
        yield element

In Python 3.7 und oben, Wörterbücher sind garantiert ihren Schlüsselauftrag zu erinnern. Die Antwort auf diese Frage fasst den aktuellen Stand der Dinge.

Die OrderedDict Lösung wird somit überflüssig und ohne Import-Anweisungen können wir einfach Ausgabe:

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

Für keine hashable Typen (zum Beispiel Liste von Listen), basierend auf MizardX suchen:

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

die rekursive Idee in definining für Listen nub Funktion des Haskell verwendet Leihen, wäre dies ein rekursive Ansatz sein:

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

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

Ich habe versucht, es für wachsende Datengrößen und sah sublinear Zeitkomplexität (nicht endgültig, sondern schlage vor, dies sollte für normale Daten in Ordnung sein).

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 denke auch interessant es ist, dass diese leicht zu Einzigartigkeit von anderen Operationen verallgemeinert werden könnte. Wie folgt aus:

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)

Zum Beispiel könnten Sie in eine Funktion übergeben, die den Begriff verwendet, der auf die gleiche ganze Zahl gerundet, als ob es „Gleichheit“ war für Einzigartigkeit Zwecke, wie folgt aus:

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

dann eindeutig (some_list, test_round) würden die einzigartigen Elemente der Liste zur Verfügung stellen, wo Einzigartigkeit nicht mehr traditionelle Gleichheit gemeint (die unter Verwendung jeder Art von Set-basierten oder dict-Key-basierten Ansatz für dieses Problem angedeutet wird), sondern bedeutete, nur das erste Element zu nehmen, die für jede mögliche ganze Zahl K auf K rundet, dass die Elemente könnten Runde, zum Beispiel:

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]

5 x schneller reduzieren Variante aber anspruchsvollere

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

Erklärung:

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]

MizardX Antwort gibt eine gute Sammlung von mehreren Ansätzen.

Das ist, was ich kam mit, während laut denken:

mylist = [x for i,x in enumerate(mylist) if x not in mylist[i+1:]]

Sie können eine Liste Verständnis verweisen, wie sie durch das Symbol gebaut wird ‚_ [1]‘.
Zum Beispiel die folgende Funktion unique-ifies eine Liste von Elementen, ohne die Reihenfolge zu ändern, indem die Liste Verständnis verweist.

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]

Sie könnten eine Art hässlich Liste Verständnis Hack tun.

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

Relativ wirksamer Ansatz mit _sorted_ einem numpy Arrays:

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

l = [1,2,2,3,3,...]
n = []
n.extend(ele for ele in l if ele not in set(n))

Ein Generator, der den Ausdruck O (1) aus einem Satz suchen verwendet, um zu bestimmen, ob ein Element in der neuen Liste enthalten.

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

Wenn Sie einen Liner benötigen dann vielleicht würde dies helfen:

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

... soll mich arbeiten, aber korrigieren, wenn ich falsch bin

Wenn Sie regelmäßig pandas und Ästhetik über die Leistung bevorzugt, betrachten Sie die eingebaute Funktion 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

Timing:

    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

das wird, um bewahren und in O (n) Zeit. im Grunde ist die Idee, ein Loch zu schaffen, wo immer es ein Duplikat gefunden ist und sinken sie auf den Boden hinunter. macht einen Zeiger Verwendung lesen und schreiben. immer dann, wenn ein Duplikat gefunden wird nur die Zeiger Fortschritte Lese- und Schreibzeiger auf dem doppelten Eintrag bleibt es überschrieben werden sollen.

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]

Eine Lösung ohne importierte Module oder Baugruppen mit:

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

['ask', 'not', 'what', 'your', 'country', 'can', 'do', 'for', 'you']

Ein In-Place-Verfahren

Diese Methode ist quadratisch, weil wir eine lineare Lookup in die Liste für jedes Element der Liste haben (zu, dass wir wegen der del s die Kosten für die Neuanordnung der Liste hinzuzufügen haben).

Das heißt, es möglich ist, an Ort und Stelle zu arbeiten, wenn wir vom Ende der Liste beginnen und gehen Sie zum Ursprung jedes Glied zu entfernen, die in der Unterliste an seinem linken

vorhanden ist

Diese Idee in 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]:

Die Beseitigung der doppelten Werte in einer Folge, aber die Reihenfolge der verbleibenden Elemente bewahren. Die Verwendung von Allzweck-Generatorfunktion.

# 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}]

ZMK Ansatz verwendet Liste Verständnis, die sehr schnell ist, hält noch die Reihenfolge natürlich. Für die Anwendung der empfindliche Saite Fall kann es leicht modifiziert werden. Dies schont auch den ursprünglichen Fall.

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

Eng damit 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())))

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow