Comment 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 donné, ['one', 'two', 'three']il devrait retourner False.

Utilisez set()pour supprimer les doublons si toutes les valeurs sont hachables :

>>> your_list = ['one', 'two', 'one']
>>> len(your_list) != len(set(your_list))
True

Recommandé pour les listes courtes uniquement:

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

Ne pas utiliser sur une longue liste - cela peut prendre un temps proportionnel au carré du nombre d'éléments dans la liste!

Pour des listes plus longues avec des éléments hachables (chaînes, nombres, etc.):

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

Si vos éléments ne sont pas hachables (sous-listes, dictionnaires, etc.), ils deviennent plus poilus, bien qu'il soit toujours possible d'obtenir O (N logN) s'ils sont au moins comparables. Mais vous devez connaître ou tester les caractéristiques des éléments (hachables ou non, comparables ou non) pour obtenir les meilleures performances possibles - O (N) pour les hachables, O (N log N) pour les comparables non hachables, sinon c'est à O (N au carré) et on ne peut rien y faire :-(.

C'est vieux, mais les réponses ici m'ont conduit à une solution légèrement différente. Si vous êtes prêt à abuser de vos compréhensions, vous pouvez vous mettre en court-circuit 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))

Si vous aimez le style de programmation fonctionnelle, voici une fonction utile, un code auto-documenté et testé à l'aide de 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 l'unicité 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 car vous construisez explicitement la décomposition. Mais dans le cadre de l'utilisation de la réduction, vous pouvez arriver à quelque chose d'équivalent (mais légèrement moins efficace) pour répondre 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

J'ai pensé qu'il serait utile de comparer les timings des différentes solutions présentées ici. Pour cela, j'ai utilisé ma propre bibliothèque simple_benchmark:

Donc en effet pour ce cas la solution de Denis Otkidach est la plus rapide.

Certaines des approches présentent également une courbe beaucoup plus raide, ce sont les approches qui échelonnent quadratique avec le nombre d'éléments (première solution d'Alex Martellis, wjandrea et les deux solutions de Xavier Decorets). Il est également important de mentionner que la solution pandas de Keiku a un très grand facteur constant. Mais pour les listes plus grandes, il rattrape presque les autres solutions.

Et au cas où le duplicata serait à la première position. Ceci est utile pour voir quelles solutions sont en court-circuit:

Ici, plusieurs approches ne court-circuitent pas: Kaiku, Frank, Xavier_Decoret (première solution), Turn, Alex Martelli (première solution) et l'approche présentée par Denis Otkidach (qui a été la plus rapide dans le cas sans doublon).

J'ai inclus une fonction de ma propre bibliothèque ici: iteration_utilities.all_distinctqui peut rivaliser avec la solution la plus rapide dans le cas sans doublons et qui fonctionne en temps constant pour le cas de duplication au début (mais pas aussi rapide).

Le code du 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)

Et pour les arguments:

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

J'ai récemment répondu à une question connexe pour établir tous les doublons dans une liste, à l'aide d'un générateur. Il a l'avantage que s'il est utilisé simplement pour établir «s'il y a un doublon», il vous suffit d'obtenir le premier élément et le reste peut être ignoré, ce qui est le raccourci ultime.

C'est 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

En conséquence, une liste complète des dupes serait list(getDupes(etc)). Pour tester simplement "s'il y a" une dupe, il doit être encapsulé comme suit:

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

Cela s'adapte bien et fournit des temps de fonctionnement cohérents où que le dupe se trouve dans la liste - j'ai testé avec des listes allant jusqu'à 1 m d'entrées. Si vous savez quelque chose sur les données, en particulier, que des dupes sont susceptibles d'apparaître dans la première moitié, ou d'autres choses qui vous permettent de biaiser vos exigences, comme avoir besoin d'obtenir les dupes réelles, alors il existe quelques localisateurs de dupes vraiment alternatifs. cela pourrait surpasser. Les deux que je recommande sont ...

Approche simple basée sur les dict, 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

Tirez parti d'itertools (essentiellement un ifilter / izip / tee) sur la liste triée, très efficace si vous obtenez toutes les dupes, mais pas aussi rapidement pour obtenir 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 parmi les approches que j'ai essayées pour la liste complète des dupes , la première dupe se produisant n'importe où dans une liste d'éléments de 1 m du début au milieu. Il était surprenant de constater à quel point l'étape de tri était peu chargée. Votre kilométrage peut varier, mais voici mes résultats chronométrés spécifiques:

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 procéder de manière succincte est d' utiliser Counter .

Pour simplement déterminer 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]

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

J'ai trouvé que cela offrait les meilleures performances car il court-circuitait l'opération lors de la première duplication trouvée, 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

Je ne sais pas vraiment ce que fait le décor dans les coulisses, alors j'aime juste rester simple.

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

Une solution plus simple est la suivante. Vérifiez simplement Vrai / Faux avec la .duplicated()méthode pandas , puis prenez la somme. Veuillez également consulter pandas.Series.duplicated - documentation pandas 0.24.1

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

Si la liste contient des éléments non détachables, vous pouvez utiliser la solution d'Alex Martelli mais avec une liste au lieu d'un ensemble, bien qu'elle soit plus lente 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

J'ai utilisé l'approche de pyrospade, pour sa simplicité, et l'ai légèrement modifiée sur une courte liste faite à partir du registre Windows insensible à la casse.

Si la chaîne de valeur PATH brute est divisée en chemins individuels, tous les chemins `` nuls '' (chaînes vides ou d'espaces uniquement) peuvent être supprimés en utilisant:

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

Le PATH d'origine a à la fois des entrées «nulles» et des doublons à des fins de test:

[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

Les chemins nuls ont été supprimés, mais il y a toujours des doublons, par exemple (1, 3) et (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\

Et enfin, les dupes ont été supprimés:

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

def check_duplicates(my_list):
    seen = {}
    for item in my_list:
        if seen.get(item):
            return True
        seen[item] = True
    return False