Überprüfen, ob alle Elemente in einer Liste eindeutig sind

104

Was ist der beste Weg (am besten wie auf herkömmliche Weise), um zu überprüfen, ob alle Elemente in einer Liste eindeutig sind?

Mein aktueller Ansatz mit a Counterist:

>>> x = [1, 1, 1, 2, 3, 4, 5, 6, 2]
>>> counter = Counter(x)
>>> for values in counter.itervalues():
        if values > 1: 
            # do something

Kann ich es besser machen

user225312
quelle

Antworten:

164

Nicht die effizienteste, aber unkompliziert und prägnant:

if len(x) > len(set(x)):
   pass # do something

Wahrscheinlich wird es für kurze Listen keinen großen Unterschied machen.

Yan
quelle
Das mache ich auch. Wahrscheinlich nicht effizient für große Listen.
Tkerwin
Dies muss nicht unbedingt den Hauptteil der Bedingung ausführen, wenn die Liste sich wiederholende Elemente enthält (im Beispiel "#do etwas").
Yan
2
Fair genug, gute Lösung. Ich bearbeite kaum <500 Elemente, also sollte dies tun, was ich will.
user225312
4
Für diejenigen besorgt über Effizienz mit langen Listen, dies ist effizient für lange Listen , die tatsächlich einzigartig sind (wo alle Elemente müssen überprüft). Early-Exit-Lösungen dauern für tatsächlich eindeutige Listen länger (in meinen Tests ungefähr 2x länger). Wenn Sie also erwarten, dass die meisten Ihrer Listen eindeutig sind, verwenden Sie diese einfache Lösung zur Überprüfung der eingestellten Länge. Wenn Sie erwarten, dass die meisten Ihrer Listen NICHT eindeutig sind, verwenden Sie eine Early-Exit-Lösung. Welche Sie verwenden, hängt von Ihrem Anwendungsfall ab.
Russ
Diese Antwort ist nett. Seien wir hier jedoch vorsichtig: len(x) > len(set(x))Ist wahr, wenn die Elemente in xNICHT eindeutig sind. Unter dieser Titel Frage fragt genau das Gegenteil: „Überprüfen , ob alle Elemente in einer Liste sind einzigartig“
WhyWhat
95

Hier ist ein Zweiliner, der auch vorzeitig aussteigen wird:

>>> def allUnique(x):
...     seen = set()
...     return not any(i in seen or seen.add(i) for i in x)
...
>>> allUnique("ABCDEF")
True
>>> allUnique("ABACDEF")
False

Wenn die Elemente von x nicht hashbar sind, müssen Sie eine Liste verwenden für seen:

>>> def allUnique(x):
...     seen = list()
...     return not any(i in seen or seen.append(i) for i in x)
...
>>> allUnique([list("ABC"), list("DEF")])
True
>>> allUnique([list("ABC"), list("DEF"), list("ABC")])
False
PaulMcG
quelle
5
+1 sauber und durchläuft nicht die gesamte Liste, wenn sie nicht benötigt wird.
Kos
@ paul-mcguire: Möchten Sie dieses Code-Snippet unter einer Apache 2.0-kompatiblen Lizenz (z. B. Apache 2, 2/3-Zeilen-BSD, MIT, X11, zlib) lizenzieren? Ich möchte es in einem Apache 2.0-Projekt verwenden, das ich verwende, und da die Lizenzbedingungen von StackOverflow fubar sind, frage ich Sie als ursprünglichen Autor.
Ryan Parman
Ich habe anderen Code mit MIT-Lizenz ausgegeben, sodass dies für mich für dieses Snippet funktioniert. Was muss ich noch tun?
PaulMcG
21

Eine Early-Exit-Lösung könnte sein

def unique_values(g):
    s = set()
    for x in g:
        if x in s: return False
        s.add(x)
    return True

Für kleine Fälle oder wenn ein vorzeitiges Beenden nicht der übliche Fall ist, würde ich erwarten len(x) != len(set(x)), dass dies die schnellste Methode ist.

6502
quelle
Ich akzeptierte die andere Antwort, da ich nicht besonders nach Optimierung suchte.
user225312
2
Sie können dies verkürzen, indem Sie die folgende Zeile nach s = set()...return not any(s.add(x) if x not in s else True for x in g)
Andrew Clark
Können Sie erklären, warum Sie erwarten würden len(x) != len(set(x)), schneller zu sein, wenn ein vorzeitiges Beenden nicht üblich ist? Sind nicht beide Operationen O (len (x)) ? (Wo xist die ursprüngliche Liste)
Chris Redford
Oh, ich verstehe: Ihre Methode ist nicht O (len (x)), weil Sie if x in sinnerhalb der O (len (x)) for-Schleife prüfen .
Chris Redford
14

für Geschwindigkeit:

import numpy as np
x = [1, 1, 1, 2, 3, 4, 5, 6, 2]
np.unique(x).size == len(x)
locojay
quelle
12

Wie wäre es, wenn Sie alle Einträge zu einem Set hinzufügen und dessen Länge überprüfen?

len(set(x)) == len(x)
Grzegorz Oledzki
quelle
1
Beantwortet eine Sekunde nach Yan, autsch. Kurz und bündig. Gibt es Gründe, diese Lösung nicht zu verwenden?
Jasonleonhard
Nicht alle Sequenzen (insbesondere Generatoren) unterstützen len().
PaulMcG
9

Alternativ zu a setkönnen Sie a verwenden dict.

len({}.fromkeys(x)) == len(x)
Tugrul Ates
quelle
9
Ich sehe absolut keinen Vorteil darin, ein Diktat gegenüber einem Set zu verwenden. Scheint die Dinge unnötig zu komplizieren.
Metasoarous
3

Ein ganz anderer Ansatz, sortiert und gruppiert:

from itertools import groupby
is_unique = lambda seq: all(sum(1 for _ in x[1])==1 for x in groupby(sorted(seq)))

Es erfordert eine Sortierung, wird jedoch beim ersten wiederholten Wert beendet.

PaulMcG
quelle
Hashing ist schneller als Sortieren
IceArdor
Kam hierher, um die gleiche Lösung mit zu posten groupbyund fand diese Antwort. Ich finde das am elegantesten, da dies ein einzelner Ausdruck ist und mit den integrierten Tools funktioniert, ohne dass eine zusätzliche Variable oder Schleifenanweisung erforderlich ist.
Lars Blumberg
1
Wenn Ihre Liste beliebige Objekte enthält, die nicht sortierbar sind, können Sie sie mit der id()Funktion sortieren, da dies eine Voraussetzung für groupby()die Arbeit ist:groupby(sorted(seq), key=id)
Lars Blumberg
3

Hier ist eine rekursive O (N 2 ) -Version zum Spaß:

def is_unique(lst):
    if len(lst) > 1:
        return is_unique(s[1:]) and (s[0] not in s[1:])
    return True
Karol
quelle
2

Hier ist eine rekursive Early-Exit-Funktion:

def distinct(L):
    if len(L) == 2:
        return L[0] != L[1]
    H = L[0]
    T = L[1:]
    if (H in T):
            return False
    else:
            return distinct(T)    

Es ist schnell genug für mich, ohne seltsame (langsame) Konvertierungen zu verwenden, während ich einen funktionalen Ansatz habe.

mhourdakis
quelle
1
H in Tführt eine lineare Suche durch und T = L[1:]kopiert den in Scheiben geschnittenen Teil der Liste, sodass dies viel langsamer ist als die anderen Lösungen, die auf großen Listen vorgeschlagen wurden. Ich denke, es ist O (N ^ 2), während die meisten anderen O (N) (Mengen) oder O (N log N) (sortierungsbasierte Lösungen) sind.
Blckknght
1

Wie wäre es damit

def is_unique(lst):
    if not lst:
        return True
    else:
        return Counter(lst).most_common(1)[0][1]==1
Yilmazhuseyin
quelle
0

Sie können die Yan-Syntax (len (x)> len (set (x))) verwenden, aber anstelle von set (x) eine Funktion definieren:

 def f5(seq, idfun=None): 
    # order preserving
    if idfun is None:
        def idfun(x): return x
    seen = {}
    result = []
    for item in seq:
        marker = idfun(item)
        # in old Python versions:
        # if seen.has_key(marker)
        # but in new ones:
        if marker in seen: continue
        seen[marker] = 1
        result.append(item)
    return result

und mache len (x)> len (f5 (x)). Dies wird schnell gehen und ist auch auftragserhaltend.

Der dortige Code stammt von: http://www.peterbe.com/plog/uniqifiers-benchmark

canisrufus
quelle
Diese f5-Funktion ist langsamer als die Verwendung von set, das besser auf Geschwindigkeit optimiert ist. Dieser Code beginnt zu brechen, wenn die Liste aufgrund der teuren "Anhängen" -Operation sehr groß wird. Bei großen Listen wie x = range(1000000) + range(1000000)ist das Ausführen von set (x) schneller als f5 (x). Reihenfolge ist keine Voraussetzung in der Frage, aber selbst das Ausführen sortiert (Satz (x)) ist immer noch schneller als f5 (x)
OkezieE
0

Verwenden eines ähnlichen Ansatzes in einem Pandas-Datenrahmen, um zu testen, ob der Inhalt einer Spalte eindeutige Werte enthält:

if tempDF['var1'].size == tempDF['var1'].unique().size:
    print("Unique")
else:
    print("Not unique")

Für mich erfolgt dies sofort für eine int-Variable in einem Datumsrahmen, der über eine Million Zeilen enthält.

user1718097
quelle
0

Alle Antworten oben sind gut, aber ich bevorzuge es, ein all_uniqueBeispiel aus 30 Sekunden Python zu verwenden

Sie müssen set()die angegebene Liste verwenden, um Duplikate zu entfernen. Vergleichen Sie deren Länge mit der Länge der Liste.

def all_unique(lst):
  return len(lst) == len(set(lst))

es gibt , Truewenn alle Werte in einer flachen Liste sind unique, Falsesonst

x = [1,2,3,4,5,6]
y = [1,2,2,3,4,5]
all_unique(x) # True
all_unique(y) # False
ArunPratap
quelle
-3

Für Anfänger:

def AllDifferent(s):
    for i in range(len(s)):
        for i2 in range(len(s)):
            if i != i2:
                if s[i] == s[i2]:
                    return False
    return True
DonChriss
quelle
Ich mag diese Antwort, nur weil sie ziemlich gut zeigt, welchen Code Sie nicht schreiben müssen, wenn Sie ein Set verwenden. Ich würde es nicht als "für Anfänger" bezeichnen, da ich glaube, dass Anfänger lernen sollten, es von vornherein richtig zu machen. Aber ich habe einige unerfahrene Entwickler getroffen, die es gewohnt waren, solchen Code in anderen Sprachen zu schreiben.
cessor