Comment vérifier s'il y a des doublons dans une liste plate ?

Question

Par exemple, étant donné la liste ['one', 'two', 'one'] l'algorithme devrait retourner True alors que, étant donné ['one', 'two', 'three'] il devrait retourner False .

Answer 1

J'ai récemment répondu à une question connexe à établir tous les doublons dans une liste, en utilisant un générateur. Il présente l'avantage, s'il est utilisé uniquement pour établir "s'il y a un doublon", de n'avoir à récupérer que le premier élément et d'ignorer le reste, ce qui constitue le raccourci ultime.

Il s'agit d'une approche intéressante basée sur des ensembles que j'ai adaptée directement de moooeeeep :

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 des doublons serait la suivante list(getDupes(etc)) . Pour tester simplement "si" il y a un double, il faut l'emballer comme suit :

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

Cela fonctionne bien et fournit des temps de fonctionnement cohérents où que se trouve le double dans la liste -- j'ai testé avec des listes allant jusqu'à 1m d'entrées. Si vous savez quelque chose à propos des données, en particulier que les doublons sont susceptibles d'apparaître dans la première moitié, ou d'autres choses qui vous permettent de biaiser vos exigences, comme le besoin d'obtenir les doublons réels, alors il y a quelques localisateurs de doublons vraiment alternatifs qui pourraient être plus performants. Les deux que je recommande sont...

Une approche simple basée sur des dictées, 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

Utilisez itertools (essentiellement un ifilter/izip/tee) sur la liste triée, très efficace si vous obtenez tous les doublons mais pas aussi rapide pour obtenir juste 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 plus performants parmi les approches que j'ai essayées pour l'enquête. liste complète des doublons Le premier doublon peut se trouver n'importe où dans une liste de 1 million d'éléments, du début au milieu. Il est surprenant de constater à quel point l'étape de tri est peu coûteuse. Votre kilométrage peut varier, mais voici mes résultats spécifiques chronométrés :

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

Answer 2

Une autre façon de le faire succinctement est avec Compteur .

Pour déterminer simplement s'il y a des doublons dans la liste d'origine :

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 éléments qui ont des doublons :

def get_dupes(l):
    return [k for k, v in Counter(l).items() if v > 1]

Answer 3

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

Answer 4

J'ai trouvé que cet algorithme offrait les meilleures performances car il court-circuite l'opération lorsque le premier doublon est trouvé, alors cet algorithme a une complexité temporelle et spatiale O(n) où n est la longueur de la liste :

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

Answer 5

Si la liste contient des éléments non hachables, vous pouvez utiliser La solution d'Alex Martelli mais avec une liste au lieu d'un ensemble, bien qu'il soit plus lent pour les entrées plus importantes : O(N^2).

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