709 Stimmen

Wie finde ich die Duplikate in einer Liste und erstelle eine weitere Liste mit ihnen?

Wie finde ich die Duplikate in einer Liste mit ganzen Zahlen und erstelle eine weitere Liste mit den Duplikaten?

2 Stimmen

3 Stimmen

Wollen Sie die Duplikate einmalig oder jedes Mal, wenn sie wieder gesehen werden?

0 Stimmen

Ich denke, diese Frage wurde hier bereits sehr viel effizienter beantwortet. stackoverflow.com/a/642919/1748045 Schnittpunkt ist eine eingebaute Methode von set und sollte genau das tun, was erforderlich ist

938voto

georg Punkte 205206

Um Duplikate zu entfernen, verwenden Sie set(a) . Um Duplikate zu drucken, etwas wie:

a = [1,2,3,2,1,5,6,5,5,5]

import collections
print([item for item, count in collections.Counter(a).items() if count > 1])

## [1, 2, 5]

Beachten Sie, dass Counter nicht besonders effizient ist ( Zeitpläne ) und hier wahrscheinlich zu viel des Guten. set wird besser abschneiden. Dieser Code berechnet eine Liste eindeutiger Elemente in der Ausgangsreihenfolge:

seen = set()
uniq = []
for x in a:
    if x not in seen:
        uniq.append(x)
        seen.add(x)

oder, knapper formuliert:

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

Ich empfehle den letzteren Stil nicht, weil es nicht offensichtlich ist, was not seen.add(x) tut (die Menge add() Methode gibt immer zurück None daher die Notwendigkeit von not ).

Um die Liste der doppelten Elemente ohne Bibliotheken zu berechnen:

seen = set()
dupes = []

for x in a:
    if x in seen:
        dupes.append(x)
    else:
        seen.add(x)

oder, knapper formuliert:

seen = set()
dupes = [x for x in a if x in seen or seen.add(x)]    

Wenn Listenelemente nicht hashbar sind, können Sie keine Sets/Dicts verwenden und müssen auf eine Lösung mit quadratischer Zeit zurückgreifen (vergleichen Sie jedes mit jedem). Zum Beispiel:

a = [[1], [2], [3], [1], [5], [3]]

no_dupes = [x for n, x in enumerate(a) if x not in a[:n]]
print no_dupes # [[1], [2], [3], [5]]

dupes = [x for n, x in enumerate(a) if x in a[:n]]
print dupes # [[1], [3]]

0 Stimmen

Ich finde, dass dieser Code nicht mit einer Liste von Listen funktioniert. Die von @ritesh vorgeschlagene Lösung funktioniert mit einer Liste von Listen. Ich verwende Python Version 2.7.6.

1 Stimmen

"Zähler ist nicht besonders effizient (Timings)" in dem von Ihnen angegebenen Link, Counter ist effizienter als set für das Timing...

0 Stimmen

Das sieht interessant aus, können Sie uns mitteilen, wie hoch der Zeitaufwand dafür ist?

463voto

Ritesh Kumar Punkte 4471

Eine sehr einfache Lösung, aber mit der Komplexität O(n*n).

>>> xs = [1,2,3,4,4,5,5,6,1]
>>> set([x for x in xs if xs.count(x) > 1])
set([1, 4, 5])

5 Stimmen

Gibt es einen Grund, warum Sie ein Listenverständnis statt eines Generatorverständnisses verwenden?

120 Stimmen

In der Tat eine einfache Lösung, aber die Komplexität ist quadratisch, weil jedes count() die Liste erneut analysiert, also nicht für große Listen verwenden.

4 Stimmen

@JohnJ, Bubble Sort ist auch einfach und funktioniert. Das heißt aber nicht, dass wir sie verwenden sollten!

105voto

moooeeeep Punkte 29848

Sie brauchen nicht die Anzahl, sondern nur, ob der Gegenstand schon einmal gesehen wurde oder nicht. Angepasst diese Antwort zu diesem Problem:

def list_duplicates(seq):
  seen = set()
  seen_add = seen.add
  # adds all elements it doesn't know yet to seen and all other to seen_twice
  seen_twice = set( x for x in seq if x in seen or seen_add(x) )
  # turn the set into a list (as requested)
  return list( seen_twice )

a = [1,2,3,2,1,5,6,5,5,5]
list_duplicates(a) # yields [1, 2, 5]

Nur für den Fall, dass es auf die Geschwindigkeit ankommt, hier ein paar Zeitangaben:

# file: test.py
import collections

def thg435(l):
    return [x for x, y in collections.Counter(l).items() if y > 1]

def moooeeeep(l):
    seen = set()
    seen_add = seen.add
    # adds all elements it doesn't know yet to seen and all other to seen_twice
    seen_twice = set( x for x in l if x in seen or seen_add(x) )
    # turn the set into a list (as requested)
    return list( seen_twice )

def RiteshKumar(l):
    return list(set([x for x in l if l.count(x) > 1]))

def JohnLaRooy(L):
    seen = set()
    seen2 = set()
    seen_add = seen.add
    seen2_add = seen2.add
    for item in L:
        if item in seen:
            seen2_add(item)
        else:
            seen_add(item)
    return list(seen2)

l = [1,2,3,2,1,5,6,5,5,5]*100

Hier sind die Ergebnisse: (gut gemacht @JohnLaRooy!)

$ python -mtimeit -s 'import test' 'test.JohnLaRooy(test.l)'
10000 loops, best of 3: 74.6 usec per loop
$ python -mtimeit -s 'import test' 'test.moooeeeep(test.l)'
10000 loops, best of 3: 91.3 usec per loop
$ python -mtimeit -s 'import test' 'test.thg435(test.l)'
1000 loops, best of 3: 266 usec per loop
$ python -mtimeit -s 'import test' 'test.RiteshKumar(test.l)'
100 loops, best of 3: 8.35 msec per loop

Interessanterweise ändert sich nicht nur das Timing, sondern auch die Rangfolge leicht, wenn pypy verwendet wird. Interessanterweise profitiert der Counter-basierte Ansatz enorm von den Optimierungen von pypy, während der von mir vorgeschlagene Methoden-Caching-Ansatz fast keine Auswirkungen zu haben scheint.

$ pypy -mtimeit -s 'import test' 'test.JohnLaRooy(test.l)'
100000 loops, best of 3: 17.8 usec per loop
$ pypy -mtimeit -s 'import test' 'test.thg435(test.l)'
10000 loops, best of 3: 23 usec per loop
$ pypy -mtimeit -s 'import test' 'test.moooeeeep(test.l)'
10000 loops, best of 3: 39.3 usec per loop

Offenbar hängt dieser Effekt mit der "Duplizität" der Eingabedaten zusammen. Ich habe eingestellt l = [random.randrange(1000000) for i in xrange(10000)] und erhielt diese Ergebnisse:

$ pypy -mtimeit -s 'import test' 'test.moooeeeep(test.l)'
1000 loops, best of 3: 495 usec per loop
$ pypy -mtimeit -s 'import test' 'test.JohnLaRooy(test.l)'
1000 loops, best of 3: 499 usec per loop
$ pypy -mtimeit -s 'import test' 'test.thg435(test.l)'
1000 loops, best of 3: 1.68 msec per loop

9 Stimmen

Ich bin nur neugierig - was ist der Zweck von seen_add = seen.add hier?

4 Stimmen

@Rob Auf diese Weise rufen Sie einfach die Funktion auf, die Sie schon einmal nachgeschlagen haben. Andernfalls müssten Sie die Mitgliedsfunktion nachschlagen (eine Wörterbuchabfrage) add jedes Mal, wenn eine Einfügung erforderlich wäre.

0 Stimmen

Mit meinen eigenen Daten und Ipythons %timeit überprüft, sieht Ihre Methode im Test am schnellsten aus, ABER: "Der langsamste Durchlauf dauerte 4,34 Mal länger als der schnellste. Dies könnte bedeuten, dass ein Zwischenergebnis zwischengespeichert wird.

88voto

MSeifert Punkte 131411

Sie können verwenden iteration_utilities.duplicates :

>>> from iteration_utilities import duplicates

>>> list(duplicates([1,1,2,1,2,3,4,2]))
[1, 1, 2, 2]

oder, wenn Sie nur ein Duplikat von jedem wünschen, kann dies mit iteration_utilities.unique_everseen :

>>> from iteration_utilities import unique_everseen

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

Es kann auch mit nicht verschlüsselbaren Elementen umgehen (allerdings auf Kosten der Leistung):

>>> list(duplicates([[1], [2], [1], [3], [1]]))
[[1], [1]]

>>> list(unique_everseen(duplicates([[1], [2], [1], [3], [1]])))
[[1]]

Das ist etwas, was nur wenige der anderen Ansätze hier leisten können.

Benchmarks

Ich habe einen schnellen Benchmark durchgeführt, der die meisten (aber nicht alle) der hier genannten Ansätze enthält.

Der erste Benchmark umfasste nur einen kleinen Bereich von Listenlängen, da einige Ansätze O(n**2) Verhalten.

In den Diagrammen stellt die y-Achse die Zeit dar, d. h. ein niedrigerer Wert bedeutet besser. Sie ist auch log-logarithmisch dargestellt, damit die große Bandbreite der Werte besser sichtbar wird:

enter image description here

Das Entfernen der O(n**2) Ich habe einen weiteren Benchmark mit bis zu einer halben Million Elementen in einer Liste durchgeführt:

enter image description here

Wie Sie sehen können, ist die iteration_utilities.duplicates Ansatz ist schneller als alle anderen Ansätze und sogar die Verkettung von unique_everseen(duplicates(...)) schneller oder gleich schnell war als die anderen Ansätze.

Interessant ist auch, dass die Pandas bei kleinen Listen sehr langsam sind, bei längeren Listen aber problemlos mithalten können.

Wie diese Benchmarks jedoch zeigen, schneiden die meisten Ansätze in etwa gleich gut ab, so dass es keine große Rolle spielt, welcher Ansatz verwendet wird (mit Ausnahme der 3 Ansätze, bei denen O(n**2) Laufzeit).

from iteration_utilities import duplicates, unique_everseen
from collections import Counter
import pandas as pd
import itertools

def georg_counter(it):
    return [item for item, count in Counter(it).items() if count > 1]

def georg_set(it):
    seen = set()
    uniq = []
    for x in it:
        if x not in seen:
            uniq.append(x)
            seen.add(x)

def georg_set2(it):
    seen = set()
    return [x for x in it if x not in seen and not seen.add(x)]   

def georg_set3(it):
    seen = {}
    dupes = []

    for x in it:
        if x not in seen:
            seen[x] = 1
        else:
            if seen[x] == 1:
                dupes.append(x)
            seen[x] += 1

def RiteshKumar_count(l):
    return set([x for x in l if l.count(x) > 1])

def moooeeeep(seq):
    seen = set()
    seen_add = seen.add
    # adds all elements it doesn't know yet to seen and all other to seen_twice
    seen_twice = set( x for x in seq if x in seen or seen_add(x) )
    # turn the set into a list (as requested)
    return list( seen_twice )

def F1Rumors_implementation(c):
    a, b = itertools.tee(sorted(c))
    next(b, None)
    r = None
    for k, g in zip(a, b):
        if k != g: continue
        if k != r:
            yield k
            r = k

def F1Rumors(c):
    return list(F1Rumors_implementation(c))

def Edward(a):
    d = {}
    for elem in a:
        if elem in d:
            d[elem] += 1
        else:
            d[elem] = 1
    return [x for x, y in d.items() if y > 1]

def wordsmith(a):
    return pd.Series(a)[pd.Series(a).duplicated()].values

def NikhilPrabhu(li):
    li = li.copy()
    for x in set(li):
        li.remove(x)

    return list(set(li))

def firelynx(a):
    vc = pd.Series(a).value_counts()
    return vc[vc > 1].index.tolist()

def HenryDev(myList):
    newList = set()

    for i in myList:
        if myList.count(i) >= 2:
            newList.add(i)

    return list(newList)

def yota(number_lst):
    seen_set = set()
    duplicate_set = set(x for x in number_lst if x in seen_set or seen_set.add(x))
    return seen_set - duplicate_set

def IgorVishnevskiy(l):
    s=set(l)
    d=[]
    for x in l:
        if x in s:
            s.remove(x)
        else:
            d.append(x)
    return d

def it_duplicates(l):
    return list(duplicates(l))

def it_unique_duplicates(l):
    return list(unique_everseen(duplicates(l)))

Zielvorgabe 1

from simple_benchmark import benchmark
import random

funcs = [
    georg_counter, georg_set, georg_set2, georg_set3, RiteshKumar_count, moooeeeep, 
    F1Rumors, Edward, wordsmith, NikhilPrabhu, firelynx,
    HenryDev, yota, IgorVishnevskiy, it_duplicates, it_unique_duplicates
]

args = {2**i: [random.randint(0, 2**(i-1)) for _ in range(2**i)] for i in range(2, 12)}

b = benchmark(funcs, args, 'list size')

b.plot()

Benchmark 2

funcs = [
    georg_counter, georg_set, georg_set2, georg_set3, moooeeeep, 
    F1Rumors, Edward, wordsmith, firelynx,
    yota, IgorVishnevskiy, it_duplicates, it_unique_duplicates
]

args = {2**i: [random.randint(0, 2**(i-1)) for _ in range(2**i)] for i in range(2, 20)}

b = benchmark(funcs, args, 'list size')
b.plot()

Haftungsausschluss

1 Dies stammt aus einer Bibliothek eines Drittanbieters, die ich geschrieben habe: iteration_utilities .

4 Stimmen

Ich werde mich hier aus dem Fenster lehnen und vorschlagen, eine maßgeschneiderte Bibliothek zu schreiben, um die Arbeit in C statt in Python zu erledigen, ist wahrscheinlich nicht der Geist der Antwort, nach der gesucht wurde - aber das ist ein legitimer Ansatz! Mir gefällt die Breite der Antwort und die grafische Darstellung der Ergebnisse - sehr schön zu sehen, dass sie konvergieren, ich frage mich, ob sie sich jemals kreuzen, wenn die Eingaben weiter steigen! Frage: Wie ist das Ergebnis bei überwiegend sortierten Listen im Gegensatz zu völlig zufälligen Listen?

0 Stimmen

Danke für das Benchmarking, ich habe es in meine Antwort jetzt. Vorschlag für solche überfüllten Plotbilder: Verwenden Sie eine höhere Auflösung (ich habe meine mit plt.savefig('duplicates.png', dpi=300) ) und den größten Teil des weißen Raums um die eigentliche Handlung herum entfernen. Dann ist das Bild größer und klarer, sowohl in der eingebetteten Ansicht als auch in der eigenständigen Ansicht (wenn Sie auf das Bild klicken). Die höhere Auflösung erhöht die Dateigröße, aber Sie können dem entgegenwirken, indem Sie die Farbtiefe verringern.

37voto

F1Rumors Punkte 881

Ich bin auf diese Frage gestoßen, als ich nach etwas Ähnlichem gesucht habe - und frage mich, warum niemand eine Lösung auf Generatorbasis angeboten hat? Die Lösung dieses Problems wäre:

>>> print list(getDupes_9([1,2,3,2,1,5,6,5,5,5]))
[1, 2, 5]

Ich war besorgt über die Skalierbarkeit und habe daher mehrere Ansätze getestet, darunter auch naive Elemente, die bei kleinen Listen gut funktionieren, aber bei größeren Listen furchtbar skalieren (Anmerkung: Es wäre besser gewesen, timeit zu verwenden, aber das ist nur ein Beispiel).

Ich habe @moooeeeep zum Vergleich einbezogen (es ist beeindruckend schnell: am schnellsten, wenn die Eingabeliste völlig zufällig ist) und einen itertools-Ansatz, der für meist sortierte Listen sogar noch schneller ist... Enthält jetzt den Pandas-Ansatz von @firelynx - langsam, aber nicht schrecklich, und einfach. Anmerkung - der sort/tee/zip Ansatz ist auf meiner Maschine für große, meist geordnete Listen durchweg am schnellsten, moooeeeep ist am schnellsten für gemischte Listen, aber das kann variieren.

Vorteile

  • sehr schnell und einfach auf "beliebige" Duplikate zu testen, indem man denselben Code verwendet

Annahmen

  • Duplikate sollten nur einmal gemeldet werden
  • Eine doppelte Bestellung muss nicht beibehalten werden
  • Das Duplikat kann sich an beliebiger Stelle in der Liste befinden

Schnellste Lösung, 1m Einträge:

def getDupes(c):
        '''sort/tee/izip'''
        a, b = itertools.tee(sorted(c))
        next(b, None)
        r = None
        for k, g in itertools.izip(a, b):
            if k != g: continue
            if k != r:
                yield k
                r = k

Getestete Ansätze

import itertools
import time
import random

def getDupes_1(c):
    '''naive'''
    for i in xrange(0, len(c)):
        if c[i] in c[:i]:
            yield c[i]

def getDupes_2(c):
    '''set len change'''
    s = set()
    for i in c:
        l = len(s)
        s.add(i)
        if len(s) == l:
            yield i

def getDupes_3(c):
    '''in dict'''
    d = {}
    for i in c:
        if i in d:
            if d[i]:
                yield i
                d[i] = False
        else:
            d[i] = True

def getDupes_4(c):
    '''in set'''
    s,r = set(),set()
    for i in c:
        if i not in s:
            s.add(i)
        elif i not in r:
            r.add(i)
            yield i

def getDupes_5(c):
    '''sort/adjacent'''
    c = sorted(c)
    r = None
    for i in xrange(1, len(c)):
        if c[i] == c[i - 1]:
            if c[i] != r:
                yield c[i]
                r = c[i]

def getDupes_6(c):
    '''sort/groupby'''
    def multiple(x):
        try:
            x.next()
            x.next()
            return True
        except:
            return False
    for k, g in itertools.ifilter(lambda x: multiple(x[1]), itertools.groupby(sorted(c))):
        yield k

def getDupes_7(c):
    '''sort/zip'''
    c = sorted(c)
    r = None
    for k, g in zip(c[:-1],c[1:]):
        if k == g:
            if k != r:
                yield k
                r = k

def getDupes_8(c):
    '''sort/izip'''
    c = sorted(c)
    r = None
    for k, g in itertools.izip(c[:-1],c[1:]):
        if k == g:
            if k != r:
                yield k
                r = k

def getDupes_9(c):
    '''sort/tee/izip'''
    a, b = itertools.tee(sorted(c))
    next(b, None)
    r = None
    for k, g in itertools.izip(a, b):
        if k != g: continue
        if k != r:
            yield k
            r = k

def getDupes_a(l):
    '''moooeeeep'''
    seen = set()
    seen_add = seen.add
    # adds all elements it doesn't know yet to seen and all other to seen_twice
    for x in l:
        if x in seen or seen_add(x):
            yield x

def getDupes_b(x):
    '''iter*/sorted'''
    x = sorted(x)
    def _matches():
        for k,g in itertools.izip(x[:-1],x[1:]):
            if k == g:
                yield k
    for k, n in itertools.groupby(_matches()):
        yield k

def getDupes_c(a):
    '''pandas'''
    import pandas as pd
    vc = pd.Series(a).value_counts()
    i = vc[vc > 1].index
    for _ in i:
        yield _

def hasDupes(fn,c):
    try:
        if fn(c).next(): return True    # Found a dupe
    except StopIteration:
        pass
    return False

def getDupes(fn,c):
    return list(fn(c))

STABLE = True
if STABLE:
    print 'Finding FIRST then ALL duplicates, single dupe of "nth" placed element in 1m element array'
else:
    print 'Finding FIRST then ALL duplicates, single dupe of "n" included in randomised 1m element array'
for location in (50,250000,500000,750000,999999):
    for test in (getDupes_2, getDupes_3, getDupes_4, getDupes_5, getDupes_6,
                 getDupes_8, getDupes_9, getDupes_a, getDupes_b, getDupes_c):
        print 'Test %-15s:%10d - '%(test.__doc__ or test.__name__,location),
        deltas = []
        for FIRST in (True,False):
            for i in xrange(0, 5):
                c = range(0,1000000)
                if STABLE:
                    c[0] = location
                else:
                    c.append(location)
                    random.shuffle(c)
                start = time.time()
                if FIRST:
                    print '.' if location == test(c).next() else '!',
                else:
                    print '.' if [location] == list(test(c)) else '!',
                deltas.append(time.time()-start)
            print ' -- %0.3f  '%(sum(deltas)/len(deltas)),
        print
    print

Die Ergebnisse für den Test "alle Duplikate" waren konsistent und fanden "erstes" Duplikat und dann "alle" Duplikate in diesem Feld:

Finding FIRST then ALL duplicates, single dupe of "nth" placed element in 1m element array
Test set len change :    500000 -  . . . . .  -- 0.264   . . . . .  -- 0.402  
Test in dict        :    500000 -  . . . . .  -- 0.163   . . . . .  -- 0.250  
Test in set         :    500000 -  . . . . .  -- 0.163   . . . . .  -- 0.249  
Test sort/adjacent  :    500000 -  . . . . .  -- 0.159   . . . . .  -- 0.229  
Test sort/groupby   :    500000 -  . . . . .  -- 0.860   . . . . .  -- 1.286  
Test sort/izip      :    500000 -  . . . . .  -- 0.165   . . . . .  -- 0.229  
Test sort/tee/izip  :    500000 -  . . . . .  -- 0.145   . . . . .  -- 0.206  *
Test moooeeeep      :    500000 -  . . . . .  -- 0.149   . . . . .  -- 0.232  
Test iter*/sorted   :    500000 -  . . . . .  -- 0.160   . . . . .  -- 0.221  
Test pandas         :    500000 -  . . . . .  -- 0.493   . . . . .  -- 0.499  

Wenn die Listen zuerst gemischt werden, wird der Preis der Sortierung offensichtlich - die Effizienz sinkt merklich und der @moooeeeep-Ansatz dominiert, wobei die Ansätze set und dict ähnlich, aber weniger leistungsfähig sind:

Finding FIRST then ALL duplicates, single dupe of "n" included in randomised 1m element array
Test set len change :    500000 -  . . . . .  -- 0.321   . . . . .  -- 0.473  
Test in dict        :    500000 -  . . . . .  -- 0.285   . . . . .  -- 0.360  
Test in set         :    500000 -  . . . . .  -- 0.309   . . . . .  -- 0.365  
Test sort/adjacent  :    500000 -  . . . . .  -- 0.756   . . . . .  -- 0.823  
Test sort/groupby   :    500000 -  . . . . .  -- 1.459   . . . . .  -- 1.896  
Test sort/izip      :    500000 -  . . . . .  -- 0.786   . . . . .  -- 0.845  
Test sort/tee/izip  :    500000 -  . . . . .  -- 0.743   . . . . .  -- 0.804  
Test moooeeeep      :    500000 -  . . . . .  -- 0.234   . . . . .  -- 0.311  *
Test iter*/sorted   :    500000 -  . . . . .  -- 0.776   . . . . .  -- 0.840  
Test pandas         :    500000 -  . . . . .  -- 0.539   . . . . .  -- 0.540

0 Stimmen

@moooeeeep - es würde mich interessieren, was Sie über den ifilter/izip/tee-Ansatz denken.

2 Stimmen

Ich verstehe nicht, dass es nicht mehr Punkte für die Erklärungen und Tests gab, die sehr nützlich für diejenigen sind, die sie brauchen.

1 Stimmen

Python's sort ist O(n), wenn nur ein Element nicht in Ordnung ist. Sie sollten random.shuffle(c) um dem Rechnung zu tragen. Außerdem kann ich Ihre Ergebnisse nicht replizieren, wenn ich das unveränderte Skript ausführe (völlig andere Reihenfolge), also ist es vielleicht auch von der CPU abhängig.

CodeJaeger.com

CodeJaeger ist eine Gemeinschaft für Programmierer, die täglich Hilfe erhalten..
Wir haben viele Inhalte, und Sie können auch Ihre eigenen Fragen stellen oder die Fragen anderer Leute lösen.

Powered by:

X