Wie überprüfe ich, ob eine flache Liste Duplikate enthält?

184

In Anbetracht der Liste ['one', 'two', 'one']sollte der Algorithmus beispielsweise zurückkehren True, während er in der gegebenen Liste zurückkehren ['one', 'two', 'three']sollte False.

teggy
quelle

Antworten:

397

Verwenden Sie set()diese Option , um Duplikate zu entfernen, wenn alle Werte hashbar sind :

>>> your_list = ['one', 'two', 'one']
>>> len(your_list) != len(set(your_list))
True
Denis Otkidach
quelle
17
Bevor ich dies gelesen habe, habe ich your_list! = List (set (your_list)) ausprobiert, was nicht funktioniert, da sich die Reihenfolge der Elemente ändert. Die Verwendung von len ist ein guter Weg, um dieses Problem zu lösen
Igniteflow
1
funktioniert oft nicht für Arrays von Gleitkommawerten. Siehe stackoverflow.com/questions/60914705
Manas Dogra
54

Empfohlen für kurze Listen nur:

any(thelist.count(x) > 1 for x in thelist)

Sie nicht verwenden , um auf einer langen Liste - es ist Zeit proportional zum nehmen Quadrat der Anzahl der Elemente in der Liste!

Für längere Listen mit hashbaren Elementen (Zeichenfolgen, Zahlen usw.):

def anydup(thelist):
  seen = set()
  for x in thelist:
    if x in seen: return True
    seen.add(x)
  return False

Wenn Ihre Artikel nicht hashbar sind (Unterlisten, Diktate usw.), wird es haariger, obwohl es möglicherweise immer noch möglich ist, O (N logN) zu erhalten, wenn sie zumindest vergleichbar sind. Sie müssen jedoch die Eigenschaften der Elemente kennen oder testen (hashbar oder nicht, vergleichbar oder nicht), um die bestmögliche Leistung zu erzielen - O (N) für Hashables, O (N log N) für nicht hashable Vergleiche, andernfalls es liegt an O (N im Quadrat) und man kann nichts dagegen tun :-(.

Alex Martelli
quelle
21
Denis Otkidach bot eine Lösung an, bei der Sie einfach ein neues Set aus der Liste erstellen und dann dessen Länge überprüfen. Sein Vorteil ist, dass der C-Code in Python das schwere Heben übernimmt. Ihre Lösung führt eine Schleife im Python-Code durch, hat jedoch den Vorteil eines Kurzschlusses, wenn eine einzelne Übereinstimmung gefunden wurde. Wenn die Wahrscheinlichkeit besteht, dass die Liste wahrscheinlich keine Duplikate enthält, gefällt mir die Version von Denis Otkidach, aber wenn die Wahrscheinlichkeit besteht, dass es zu Beginn der Liste möglicherweise ein Duplikat gibt, ist diese Lösung besser.
Steveha
1
Es lohnt sich für das Detail, obwohl ich denke, Denis hatte die sauberere Lösung.
Steve314
@steveha - vorzeitige Optimierung?
Steve314
@ Steve314, welche vorzeitige Optimierung? Ich hätte es so geschrieben, wie Denis Otkidach es geschrieben hat, also habe ich versucht zu verstehen, warum Alex Martelli (berühmt für Python Cookbook) es anders geschrieben hat. Nachdem ich ein wenig darüber nachgedacht hatte, stellte ich fest, dass Alex 'Version kurzgeschlossen wurde, und ich schrieb ein paar Gedanken zu den Unterschieden. Wie geht man von einer Diskussion über Unterschiede zu einer vorzeitigen Optimierung, der Wurzel allen Übels?
Steveha
3
Wenn die Elemente hashbar sind, ist eine festgelegte Lösung direkter und, wie ich es ausdrückte, schneller (wird beendet, sobald die Antwort bekannt ist - "Kurzschlüsse", wie Steve es ausdrückte). Das Erstellen des von Ihnen vorgeschlagenen Diktats (am schnellsten als Sammlung. allZähler ) ist natürlich viel langsamer (benötigt eine Anzahl, bei der alle 1 sind). Ein Diktat mit allen Werten Wahr, das Sie auch erwähnen, ist eine lächerliche, nutzlos aufgeblähte Nachahmung von a set, ohne jeglichen Mehrwert. Big-O ist nicht alles in der Programmierung.
Alex Martelli
12

Das ist alt, aber die Antworten hier haben mich zu einer etwas anderen Lösung geführt. Wenn Sie bereit sind, Verständnis zu missbrauchen, können Sie auf diese Weise einen Kurzschluss bekommen.

xs = [1, 2, 1]
s = set()
any(x in s or s.add(x) for x in xs)
# You can use a similar approach to actually retrieve the duplicates.
s = set()
duplicates = set(x for x in xs if x in s or s.add(x))
Pyrospade
quelle
9

Wenn Sie den funktionalen Programmierstil mögen , finden Sie hier eine nützliche Funktion, selbstdokumentierten und getesteten Code mit doctest .

def decompose(a_list):
    """Turns a list into a set of all elements and a set of duplicated elements.

    Returns a pair of sets. The first one contains elements
    that are found at least once in the list. The second one
    contains elements that appear more than once.

    >>> decompose([1,2,3,5,3,2,6])
    (set([1, 2, 3, 5, 6]), set([2, 3]))
    """
    return reduce(
        lambda (u, d), o : (u.union([o]), d.union(u.intersection([o]))),
        a_list,
        (set(), set()))

if __name__ == "__main__":
    import doctest
    doctest.testmod()

Von dort aus können Sie die Einheitlichkeit testen, indem Sie prüfen, ob das zweite Element des zurückgegebenen Paares leer ist:

def is_set(l):
    """Test if there is no duplicate element in l.

    >>> is_set([1,2,3])
    True
    >>> is_set([1,2,1])
    False
    >>> is_set([])
    True
    """
    return not decompose(l)[1]

Beachten Sie, dass dies nicht effizient ist, da Sie die Zerlegung explizit erstellen. Bei der Verwendung von Reduzieren können Sie jedoch zu einem äquivalenten (aber etwas weniger effizienten) Ergebnis kommen, um 5 zu beantworten:

def is_set(l):
    try:
        def func(s, o):
            if o in s:
                raise Exception
            return s.union([o])
        reduce(func, l, set())
        return True
    except:
        return False
Xavier Decoret
quelle
Sollte zuerst verwandte Fragen gelesen haben. Dies ist in stackoverflow.com/questions/1723072/…
Xavier Decoret
1
Es wirft mir einen "ungültigen Syntax"
-Fehler
Dies liegt daran, dass das Entpacken in Lambda-Argumentlisten in Python 3.x entfernt wurde.
MSeifert
5

Ich dachte, es wäre nützlich, die Zeitabläufe der verschiedenen hier vorgestellten Lösungen zu vergleichen. Dafür habe ich meine eigene Bibliothek benutzt simple_benchmark:

Geben Sie hier die Bildbeschreibung ein

In diesem Fall ist die Lösung von Denis Otkidach also am schnellsten.

Einige der Ansätze weisen auch eine viel steilere Kurve auf. Dies sind die Ansätze, die quadratisch mit der Anzahl der Elemente skalieren (Alex Martellis erste Lösung, wjandrea und beide Xavier Decorets-Lösungen). Ebenfalls wichtig zu erwähnen ist, dass die Pandas-Lösung von Keiku einen sehr großen konstanten Faktor hat. Bei größeren Listen holt es jedoch fast die anderen Lösungen ein.

Und falls sich das Duplikat an erster Stelle befindet. Dies ist nützlich, um festzustellen, welche Lösungen kurzschließen:

Geben Sie hier die Bildbeschreibung ein

Hier schließen einige Ansätze nicht kurz: Kaiku, Frank, Xavier_Decoret (erste Lösung), Turn, Alex Martelli (erste Lösung) und der von Denis Otkidach vorgestellte Ansatz (der im Fall ohne Duplikate am schnellsten war).

Ich habe hier eine Funktion aus meiner eigenen Bibliothek eingefügt: iteration_utilities.all_distinctDiese kann mit der schnellsten Lösung im Fall ohne Duplikate konkurrieren und wird in konstanter Zeit für den Fall mit Duplikaten am Anfang ausgeführt (obwohl nicht so schnell).

Der Code für den Benchmark:

from collections import Counter
from functools import reduce

import pandas as pd
from simple_benchmark import BenchmarkBuilder
from iteration_utilities import all_distinct

b = BenchmarkBuilder()

@b.add_function()
def Keiku(l):
    return pd.Series(l).duplicated().sum() > 0

@b.add_function()
def Frank(num_list):
    unique = []
    dupes = []
    for i in num_list:
        if i not in unique:
            unique.append(i)
        else:
            dupes.append(i)
    if len(dupes) != 0:
        return False
    else:
        return True

@b.add_function()
def wjandrea(iterable):
    seen = []
    for x in iterable:
        if x in seen:
            return True
        seen.append(x)
    return False

@b.add_function()
def user(iterable):
    clean_elements_set = set()
    clean_elements_set_add = clean_elements_set.add

    for possible_duplicate_element in iterable:

        if possible_duplicate_element in clean_elements_set:
            return True

        else:
            clean_elements_set_add( possible_duplicate_element )

    return False

@b.add_function()
def Turn(l):
    return Counter(l).most_common()[0][1] > 1

def getDupes(l):
    seen = set()
    seen_add = seen.add
    for x in l:
        if x in seen or seen_add(x):
            yield x

@b.add_function()          
def F1Rumors(l):
    try:
        if next(getDupes(l)): return True    # Found a dupe
    except StopIteration:
        pass
    return False

def decompose(a_list):
    return reduce(
        lambda u, o : (u[0].union([o]), u[1].union(u[0].intersection([o]))),
        a_list,
        (set(), set()))

@b.add_function()
def Xavier_Decoret_1(l):
    return not decompose(l)[1]

@b.add_function()
def Xavier_Decoret_2(l):
    try:
        def func(s, o):
            if o in s:
                raise Exception
            return s.union([o])
        reduce(func, l, set())
        return True
    except:
        return False

@b.add_function()
def pyrospade(xs):
    s = set()
    return any(x in s or s.add(x) for x in xs)

@b.add_function()
def Alex_Martelli_1(thelist):
    return any(thelist.count(x) > 1 for x in thelist)

@b.add_function()
def Alex_Martelli_2(thelist):
    seen = set()
    for x in thelist:
        if x in seen: return True
        seen.add(x)
    return False

@b.add_function()
def Denis_Otkidach(your_list):
    return len(your_list) != len(set(your_list))

@b.add_function()
def MSeifert04(l):
    return not all_distinct(l)

Und für die Argumente:


# No duplicate run
@b.add_arguments('list size')
def arguments():
    for exp in range(2, 14):
        size = 2**exp
        yield size, list(range(size))

# Duplicate at beginning run
@b.add_arguments('list size')
def arguments():
    for exp in range(2, 14):
        size = 2**exp
        yield size, [0, *list(range(size)]

# Running and plotting
r = b.run()
r.plot()
MSeifert
quelle
Als Referenz: Die Funktion all_distinct ist in C geschrieben .
Benutzer
5

Ich habe kürzlich eine verwandte Frage beantwortet , um mithilfe eines Generators alle Duplikate in einer Liste zu ermitteln. Es hat den Vorteil, dass Sie nur das erste Element abrufen müssen, wenn Sie nur feststellen möchten, ob ein Duplikat vorhanden ist, und der Rest kann ignoriert werden. Dies ist die ultimative Verknüpfung.

Dies ist ein interessanter satzbasierter Ansatz, den ich direkt von moooeeeep angepasst habe :

def getDupes(l):
    seen = set()
    seen_add = seen.add
    for x in l:
        if x in seen or seen_add(x):
            yield x

Dementsprechend wäre eine vollständige Liste der Dupes list(getDupes(etc)). Um einfach zu testen, ob ein Betrüger vorhanden ist, sollte dieser wie folgt verpackt werden:

def hasDupes(l):
    try:
        if getDupes(l).next(): return True    # Found a dupe
    except StopIteration:
        pass
    return False

Dies lässt sich gut skalieren und bietet konsistente Betriebszeiten, wo immer sich der Betrüger in der Liste befindet - ich habe mit Listen mit bis zu 1 Mio. Einträgen getestet. Wenn Sie etwas über die Daten wissen, insbesondere darüber, dass Dupes wahrscheinlich in der ersten Hälfte auftauchen, oder über andere Dinge, mit denen Sie Ihre Anforderungen verzerren können, z. B. die Notwendigkeit, die tatsächlichen Dupes zu erhalten, gibt es einige wirklich alternative Dupe-Locators das könnte übertreffen. Die beiden, die ich empfehle, sind ...

Einfacher diktbasierter Ansatz, sehr gut lesbar:

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

Nutzen Sie itertools (im Wesentlichen ein ifilter / izip / tee) auf der sortierten Liste, sehr effizient, wenn Sie alle Dupes erhalten, obwohl es nicht so schnell ist, nur das erste zu erhalten:

def getDupes(c):
    a, b = itertools.tee(sorted(c))
    next(b, None)
    r = None
    for k, g in itertools.ifilter(lambda x: x[0]==x[1], itertools.izip(a, b)):
        if k != r:
            yield k
            r = k

Dies waren die Top-Performer der Ansätze, die ich für die vollständige Dupe-Liste ausprobiert habe , wobei der erste Dupe von Anfang bis Mitte irgendwo in einer 1-Meter-Elementliste vorkam. Es war überraschend, wie wenig Overhead der Sortierschritt hinzufügte. Ihr Kilometerstand kann variieren, aber hier sind meine spezifischen zeitgesteuerten Ergebnisse:

Finding FIRST duplicate, single dupe places "n" elements in to 1m element array

Test set len change :        50 -  . . . . .  -- 0.002
Test in dict        :        50 -  . . . . .  -- 0.002
Test in set         :        50 -  . . . . .  -- 0.002
Test sort/adjacent  :        50 -  . . . . .  -- 0.023
Test sort/groupby   :        50 -  . . . . .  -- 0.026
Test sort/zip       :        50 -  . . . . .  -- 1.102
Test sort/izip      :        50 -  . . . . .  -- 0.035
Test sort/tee/izip  :        50 -  . . . . .  -- 0.024
Test moooeeeep      :        50 -  . . . . .  -- 0.001 *
Test iter*/sorted   :        50 -  . . . . .  -- 0.027

Test set len change :      5000 -  . . . . .  -- 0.017
Test in dict        :      5000 -  . . . . .  -- 0.003 *
Test in set         :      5000 -  . . . . .  -- 0.004
Test sort/adjacent  :      5000 -  . . . . .  -- 0.031
Test sort/groupby   :      5000 -  . . . . .  -- 0.035
Test sort/zip       :      5000 -  . . . . .  -- 1.080
Test sort/izip      :      5000 -  . . . . .  -- 0.043
Test sort/tee/izip  :      5000 -  . . . . .  -- 0.031
Test moooeeeep      :      5000 -  . . . . .  -- 0.003 *
Test iter*/sorted   :      5000 -  . . . . .  -- 0.031

Test set len change :     50000 -  . . . . .  -- 0.035
Test in dict        :     50000 -  . . . . .  -- 0.023
Test in set         :     50000 -  . . . . .  -- 0.023
Test sort/adjacent  :     50000 -  . . . . .  -- 0.036
Test sort/groupby   :     50000 -  . . . . .  -- 0.134
Test sort/zip       :     50000 -  . . . . .  -- 1.121
Test sort/izip      :     50000 -  . . . . .  -- 0.054
Test sort/tee/izip  :     50000 -  . . . . .  -- 0.045
Test moooeeeep      :     50000 -  . . . . .  -- 0.019 *
Test iter*/sorted   :     50000 -  . . . . .  -- 0.055

Test set len change :    500000 -  . . . . .  -- 0.249
Test in dict        :    500000 -  . . . . .  -- 0.145
Test in set         :    500000 -  . . . . .  -- 0.165
Test sort/adjacent  :    500000 -  . . . . .  -- 0.139
Test sort/groupby   :    500000 -  . . . . .  -- 1.138
Test sort/zip       :    500000 -  . . . . .  -- 1.159
Test sort/izip      :    500000 -  . . . . .  -- 0.126
Test sort/tee/izip  :    500000 -  . . . . .  -- 0.120 *
Test moooeeeep      :    500000 -  . . . . .  -- 0.131
Test iter*/sorted   :    500000 -  . . . . .  -- 0.157
F1Rumor
quelle
Der .next()Aufruf in Ihrem zweiten Codeblock funktioniert unter Python 3.x nicht. Ich denke, next(getDupes(l))sollte über Python-Versionen funktionieren, daher kann es sinnvoll sein, dies zu ändern.
MSeifert
Auch ifilterund ìzipkann einfach durch das eingebaute filterund zipin Python 3.x ersetzt werden.
MSeifert
@MSeifert die Lösung funktioniert für Python 2.x wie geschrieben, und ja, für py3 können Sie Filter und Map direkt verwenden ... aber jemand, der die py3-Lösung in py2-Codebasis verwendet, würde die Vorteile nicht erhalten, da sie nicht als Generator. Explizit ist in diesem Fall besser als implizit;)
F1Rumors
3

Eine andere Möglichkeit, dies kurz und bündig zu tun, ist Counter .

So stellen Sie fest, ob die ursprüngliche Liste Duplikate enthält:

from collections import Counter

def has_dupes(l):
    # second element of the tuple has number of repetitions
    return Counter(l).most_common()[0][1] > 1

Oder um eine Liste von Elementen mit Duplikaten zu erhalten:

def get_dupes(l):
    return [k for k, v in Counter(l).items() if v > 1]
Wende
quelle
2
my_list = ['one', 'two', 'one']

duplicates = []

for value in my_list:
  if my_list.count(value) > 1:
    if value not in duplicates:
      duplicates.append(value)

print(duplicates) //["one"]
Jay Desai
quelle
1

Ich fand, dass dies die beste Leistung erbringt, da es die Operation kurzschließt, wenn das erste Duplikat gefunden wird. Dann hat dieser Algorithmus Zeit- und Raumkomplexität O (n), wobei n die Länge der Liste ist:

def has_duplicated_elements(iterable):
    """ Given an `iterable`, return True if there are duplicated entries. """
    clean_elements_set = set()
    clean_elements_set_add = clean_elements_set.add

    for possible_duplicate_element in iterable:

        if possible_duplicate_element in clean_elements_set:
            return True

        else:
            clean_elements_set_add( possible_duplicate_element )

    return False
Benutzer
quelle
0

Ich weiß nicht wirklich, was das Set hinter den Kulissen macht, deshalb halte ich es einfach gerne einfach.

def dupes(num_list):
    unique = []
    dupes = []
    for i in num_list:
        if i not in unique:
            unique.append(i)
        else:
            dupes.append(i)
    if len(dupes) != 0:
        return False
    else:
        return True
Frank
quelle
0

Eine einfachere Lösung ist wie folgt. Überprüfen Sie einfach True / False mit der Pandas- .duplicated()Methode und nehmen Sie dann die Summe. Siehe auch pandas.Series.duplicated - pandas 0.24.1 Dokumentation

import pandas as pd

def has_duplicated(l):
    return pd.Series(l).duplicated().sum() > 0

print(has_duplicated(['one', 'two', 'one']))
# True
print(has_duplicated(['one', 'two', 'three']))
# False
Keiku
quelle
0

Wenn die Liste nicht zerlegbare Elemente enthält, können Sie die Lösung von Alex Martelli verwenden, jedoch mit einer Liste anstelle eines Satzes, obwohl sie für größere Eingaben langsamer ist: O (N ^ 2).

def has_duplicates(iterable):
    seen = []
    for x in iterable:
        if x in seen:
            return True
        seen.append(x)
    return False
wjandrea
quelle
0

Ich habe den Ansatz von pyrospade der Einfachheit halber verwendet und diesen in einer kurzen Liste aus der Windows-Registrierung ohne Berücksichtigung der Groß- und Kleinschreibung geringfügig geändert.

Wenn die unformatierte PATH-Wertzeichenfolge in einzelne Pfade aufgeteilt ist, können alle 'Null'-Pfade (leere oder nur Leerzeichen) entfernt werden, indem Folgendes verwendet wird:

PATH_nonulls = [s for s in PATH if s.strip()]

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

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

Der ursprüngliche Pfad enthält zu Testzwecken sowohl Nulleinträge als auch Duplikate:

[list]  Root paths in HKLM\SYSTEM\CurrentControlSet\Control\Session Manager\Environment:PATH[list]  Root paths in HKLM\SYSTEM\CurrentControlSet\Control\Session Manager\Environment
  1  C:\Python37\
  2
  3
  4  C:\Python37\Scripts\
  5  c:\python37\
  6  C:\Program Files\ImageMagick-7.0.8-Q8
  7  C:\Program Files (x86)\poppler\bin
  8  D:\DATA\Sounds
  9  C:\Program Files (x86)\GnuWin32\bin
 10  C:\Program Files (x86)\Intel\iCLS Client\
 11  C:\Program Files\Intel\iCLS Client\
 12  D:\DATA\CCMD\FF
 13  D:\DATA\CCMD
 14  D:\DATA\UTIL
 15  C:\
 16  D:\DATA\UHELP
 17  %SystemRoot%\system32
 18
 19
 20  D:\DATA\CCMD\FF%SystemRoot%
 21  D:\DATA\Sounds
 22  %SystemRoot%\System32\Wbem
 23  D:\DATA\CCMD\FF
 24
 25
 26  c:\
 27  %SYSTEMROOT%\System32\WindowsPowerShell\v1.0\
 28

Nullpfade wurden entfernt, haben aber immer noch Duplikate, z. B. (1, 3) und (13, 20):

    [list]  Null paths removed from HKLM\SYSTEM\CurrentControlSet\Control\Session Manager\Environment:PATH
  1  C:\Python37\
  2  C:\Python37\Scripts\
  3  c:\python37\
  4  C:\Program Files\ImageMagick-7.0.8-Q8
  5  C:\Program Files (x86)\poppler\bin
  6  D:\DATA\Sounds
  7  C:\Program Files (x86)\GnuWin32\bin
  8  C:\Program Files (x86)\Intel\iCLS Client\
  9  C:\Program Files\Intel\iCLS Client\
 10  D:\DATA\CCMD\FF
 11  D:\DATA\CCMD
 12  D:\DATA\UTIL
 13  C:\
 14  D:\DATA\UHELP
 15  %SystemRoot%\system32
 16  D:\DATA\CCMD\FF%SystemRoot%
 17  D:\DATA\Sounds
 18  %SystemRoot%\System32\Wbem
 19  D:\DATA\CCMD\FF
 20  c:\
 21  %SYSTEMROOT%\System32\WindowsPowerShell\v1.0\

Und schließlich wurden die Dupes entfernt:

[list]  Massaged path list from in HKLM\SYSTEM\CurrentControlSet\Control\Session Manager\Environment:PATH
  1  C:\Python37\
  2  C:\Python37\Scripts\
  3  C:\Program Files\ImageMagick-7.0.8-Q8
  4  C:\Program Files (x86)\poppler\bin
  5  D:\DATA\Sounds
  6  C:\Program Files (x86)\GnuWin32\bin
  7  C:\Program Files (x86)\Intel\iCLS Client\
  8  C:\Program Files\Intel\iCLS Client\
  9  D:\DATA\CCMD\FF
 10  D:\DATA\CCMD
 11  D:\DATA\UTIL
 12  C:\
 13  D:\DATA\UHELP
 14  %SystemRoot%\system32
 15  D:\DATA\CCMD\FF%SystemRoot%
 16  %SystemRoot%\System32\Wbem
 17  %SYSTEMROOT%\System32\WindowsPowerShell\v1.0\
Hewey Dewey
quelle
0
def check_duplicates(my_list):
    seen = {}
    for item in my_list:
        if seen.get(item):
            return True
        seen[item] = True
    return False
ahmed meraj
quelle
Wie funktioniert die Funktion? Ich bin gespannt, wie das Wörterbuch "gesehen" gefüllt ist.
Travis Hammond