Vérifier si tous les éléments d'une liste sont uniques

104

Quelle est la meilleure façon (la meilleure comme de manière conventionnelle) de vérifier si tous les éléments d'une liste sont uniques?

Mon approche actuelle utilisant a Counterest:

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

Puis-je faire mieux?

user225312
la source

Réponses:

164

Pas le plus efficace, mais simple et concis:

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

Cela ne fera probablement aucune différence pour les listes courtes.

yan
la source
C'est ce que je fais aussi. Probablement pas efficace pour les grandes listes.
tkerwin
Pas nécessairement, cela exécutera le corps du conditionnel si la liste a des éléments répétitifs (le "#faire quelque chose" dans l'exemple).
yan
2
Assez juste, bonne solution. Je gère à peine moins de 500 éléments, donc cela devrait faire ce que je veux.
user225312
4
Pour ceux qui s'inquiètent de l'efficacité avec de longues listes, c'est efficace pour les longues listes qui sont en fait uniques (où tous les éléments doivent être vérifiés). Les solutions de sortie anticipée prennent plus de temps (environ 2 fois plus longtemps dans mes tests) pour des listes réellement uniques. Donc ... si vous vous attendez à ce que la plupart de vos listes soient uniques, utilisez cette solution simple de vérification de la longueur définie. Si vous vous attendez à ce que la plupart de vos listes ne soient PAS uniques, utilisez une solution de sortie anticipée. Lequel utiliser dépend de votre cas d'utilisation.
Russ
Cette réponse est sympa. Cependant, soyons prudents ici: len(x) > len(set(x))est True lorsque les éléments de ne xsont PAS uniques. Le titre de cette question demande exactement le contraire: "Vérifier si tous les éléments d'une liste sont uniques"
WhyWhat
96

Voici un deux lignes qui fera également une sortie anticipée:

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

Si les éléments de x ne sont pas hachables, vous devrez alors recourir à une liste pour 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
la source
5
+1 nettoie et n'itère pas dans toute la liste si ce n'est pas nécessaire.
Kos
@ paul-mcguire: Seriez-vous prêt à octroyer une licence à cet extrait de code sous une licence compatible Apache 2.0 (par exemple, Apache 2, BSD 2/3 lignes, MIT, X11, zlib). Je voudrais l'utiliser dans un projet Apache 2.0 que j'utilise, et comme les termes de licence de StackOverflow sont fubar , je vous le demande en tant qu'auteur d'origine.
Ryan Parman
J'ai publié un autre code en utilisant la licence MIT, donc cela fonctionne pour moi pour cet extrait de code. Y a-t-il quelque chose de spécial à faire?
PaulMcG
21

Une solution de sortie anticipée pourrait être

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

cependant, pour les petits cas ou si la sortie anticipée n'est pas le cas courant, je m'attends à len(x) != len(set(x))être la méthode la plus rapide.

6502
la source
J'ai accepté l'autre réponse car je ne recherchais pas particulièrement l'optimisation.
user225312
2
Vous pouvez raccourcir cela en mettant la ligne suivante après s = set()...return not any(s.add(x) if x not in s else True for x in g)
Andrew Clark
Pourriez-vous expliquer pourquoi vous vous attendriez len(x) != len(set(x))à être plus rapide que cela si la sortie prématurée n'est pas courante? Les deux opérations ne sont-elles pas O (len (x)) ? (où xest la liste d'origine)
Chris Redford
Oh, je vois: votre méthode n'est pas O (len (x)) parce que vous vérifiez à l' if x in sintérieur de la boucle O (len (x)) for.
Chris Redford
15

pour la vitesse:

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

Que diriez-vous d'ajouter toutes les entrées à un ensemble et de vérifier sa longueur?

len(set(x)) == len(x)
Grzegorz Oledzki
la source
1
Répondu une seconde après yan, aïe. Court et doux. Des raisons de ne pas utiliser cette solution?
jasonleonhard
Toutes les séquences (générateurs en particulier) ne sont pas prises en charge len().
PaulMcG
9

Alternative à a set, vous pouvez utiliser un dict.

len({}.fromkeys(x)) == len(x)
Tugrul Ates
la source
9
Je ne vois absolument aucun avantage à utiliser un dict sur un ensemble. Semble compliquer inutilement les choses.
metasoarous le
3

Une autre approche entièrement, utilisant trié et groupby:

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

Il nécessite un tri, mais se termine sur la première valeur répétée.

PaulMcG
la source
le hachage est plus rapide que le tri
IceArdor
Je suis venu ici pour publier la même solution en utilisant groupbyet j'ai trouvé cette réponse. Je trouve cela très élégant, car il s'agit d'une expression unique et fonctionne avec les outils intégrés sans nécessiter de variable supplémentaire ou d'instruction de boucle.
Lars Blumberg
1
Si votre liste contient des objets arbitraires qui ne sont pas triables, vous pouvez utiliser la id()fonction pour les trier car c'est un prérequis pour groupby()fonctionner:groupby(sorted(seq), key=id)
Lars Blumberg
3

Voici une version récursive O (N 2 ) pour le plaisir:

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

Voici une fonction de sortie anticipée récursive:

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)    

C'est assez rapide pour moi sans utiliser de conversions étranges (lentes) tout en ayant une approche de style fonctionnel.

mhourdakis
la source
1
H in Teffectue une recherche linéaire et T = L[1:]copie la partie découpée de la liste, ce sera donc beaucoup plus lent que les autres solutions qui ont été suggérées sur les grandes listes. C'est O (N ^ 2) je pense, alors que la plupart des autres sont O (N) (ensembles) ou O (N log N) (solutions basées sur le tri).
Blckknght
1

Que dis-tu de ça

def is_unique(lst):
    if not lst:
        return True
    else:
        return Counter(lst).most_common(1)[0][1]==1
yilmazhuseyin
la source
0

Vous pouvez utiliser la syntaxe de Yan (len (x)> len (set (x))), mais au lieu de set (x), définissez une fonction:

 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

et faites len (x)> len (f5 (x)). Ce sera rapide et préservera également l'ordre.

Le code est tiré de: http://www.peterbe.com/plog/uniqifiers-benchmark

canisrufus
la source
cette fonction f5 sera plus lente que l'utilisation de set qui est mieux optimisé pour la vitesse. Ce code commence à se briser lorsque la liste devient vraiment volumineuse en raison de l'opération coûteuse "ajouter". avec de grandes listes comme x = range(1000000) + range(1000000), l'exécution de set (x) est plus rapide que f5 (x). L'ordre n'est pas une exigence dans la question, mais même l'exécution triée (set (x)) est toujours plus rapide que f5 (x)
OkezieE
0

En utilisant une approche similaire dans un dataframe Pandas pour tester si le contenu d'une colonne contient des valeurs uniques:

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

Pour moi, c'est instantané sur une variable int dans une dateframe contenant plus d'un million de lignes.

user1718097
la source
0

toutes les réponses ci-dessus sont bonnes mais je préfère utiliser l' all_uniqueexemple de 30 secondes de python

vous devez utiliser set()sur la liste donnée pour supprimer les doublons, comparez sa longueur à la longueur de la liste.

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

il renvoie Truesi toutes les valeurs d'une liste plate sont unique, Falsesinon

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

Pour les débutants:

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
la source
J'aime cette réponse, simplement parce qu'elle montre assez bien quel code vous n'avez pas à écrire lorsque vous utilisez un ensemble. Je ne l'appellerais pas «pour les débutants», car je crois que les débutants devraient apprendre à le faire correctement à l'avance; mais j'ai rencontré des développeurs inexpérimentés qui avaient l'habitude d'écrire un tel code dans d'autres langues.
cessor le