Comment puis-je vérifier s'il y a des doublons dans une liste plate?
par exemple, étant donné la liste ['one', 'two', 'one'] , l'algorithme devrait retourner True , alors que ['one', 'two', 'three'] devrait retourner False .
7 réponses
utiliser set() pour supprimer les doublons si toutes les valeurs sont hachable :
>>> your_list = ['one', 'two', 'one']
>>> len(your_list) != len(set(your_list))
True
recommandé pour court listes seulement:
any(thelist.count(x) > 1 for x in thelist)
Faire pas une utilisation sur une longue liste, elle peut prendre le temps proportionnel à la carré le nombre d'éléments dans la liste!
pour les listes plus longues avec des éléments hachurés (chaînes, nombres, &c):
def anydup(thelist):
seen = set()
for x in thelist:
if x in seen: return True
seen.add(x)
return False
si vos articles ne sont pas hachables (sous-listes, dicts, etc) il obtient hairier, bien qu'il puisse encore être possible d'obtenir O (N logN) si elles sont au moins comparables. Mais vous devez connaître ou tester les caractéristiques des articles (hachables ou non, comparables ou non) pour obtenir la meilleure performance que vous pouvez -- O(N) pour les hachables, O(N log n) pour les non-hachables comparables, sinon c'est O(N au carré) et il n'y a rien qu'on puisse faire à ce sujet:-(.
si vous aimez le style de programmation fonctionnel, voici une fonction utile, auto-documentée et testée en utilisant 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()
de là, vous pouvez tester unicity en vérifiant si le deuxième élément de la paire retournée est vide:
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]
notez que ce n'est pas efficace puisque vous construisez explicitement la décomposition. Mais le long de la ligne d'utilisation de réduire, Vous pouvez venir à quelque chose d'équivalent (mais un peu moins efficace) à la réponse 5:
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
c'est vieux, mais les réponses ici m'ont amené à une solution légèrement différente. Si vous êtes prêt à abuser des compréhensions, vous pouvez obtenir court-circuiter de cette façon.
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))
j'ai récemment répondu à une question connexe à établir tous les doublons dans une liste, en utilisant un générateur. Il a l'avantage que si elle est utilisée juste pour établir s'il est un doublon", alors vous avez juste besoin d'obtenir le premier élément et le reste peut être ignoré, qui est le raccourci ultime.
il s'agit d'une approche basée sur un ensemble intéressant que j'ai adapté directement de mooeeeep :
def getDupes(l):
seen = set()
seen_add = seen.add
for x in l:
if x in seen or seen_add(x):
yield x
Par conséquent, une liste complète de dupeurs serait list(getDupes(etc)) . Pour tester simplement "s'il y a" un dupe, il faut l'envelopper comme suit:
def hasDupes(l):
try:
if getDupes(c).next(): return True # Found a dupe
except StopIteration:
pass
return False
cela se balance bien et fournit des temps de fonctionnement cohérents partout où le dupe est dans la liste -- j'ai testé avec des listes d'entrées jusqu'à 1m. Si vous savez quelque chose sur les données, en particulier, que les dupes sont susceptibles d'apparaître dans la première moitié, ou d'autres choses qui vous permettent de fausser vos exigences, comme le besoin d'obtenir le réel dupes, puis il y a un couple de localisateurs dupe vraiment alternatifs qui pourraient dépasser les performances. Les deux que je recommande sont...
Simple dict approche, très lisible:
def getDupes(c):
d = {}
for i in c:
if i in d:
if d[i]:
yield i
d[i] = False
else:
d[i] = True
Leverage itertools (essentiellement un ifilter/izip/tee) sur la liste triée, très efficace si vous obtenez tous les dupes mais pas aussi rapide pour obtenir seulement le premier:
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
ce sont les meilleurs dans les approches que j'ai essayé pour la full dupe list , avec le premier dupe n'importe où dans une liste d'éléments de 1m du début au milieu. Il était surprenant de voir à quel point l'étape de tri avait été ajoutée. Votre kilométrage peut varier, mais voici mon chronométré résultats:
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
une autre façon de faire cela succinctement est avec Counter .
pour déterminer s'il y a des doublons dans la liste originale:
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
ou pour obtenir une liste des articles qui ont des doublons:
def get_dupes(l):
return [k for k, v in Counter(l).items() if v > 1]
j'ai trouvé ceci pour faire la meilleure performance parce qu'il court-circuit l'opération quand le premier dupliqué il a trouvé, alors cet algorithme a le temps et la complexité de l'espace O (n) où n est la longueur de la liste:
def has_duplicated_elements(self, 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