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

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

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

Answer 2

Recommandé pour court uniquement des listes :

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

Faites no utilisation sur une longue liste -- cela peut prendre un temps proportionnel à la cuadrado du nombre d'éléments de la liste !

Pour les listes plus longues avec des éléments hachables (chaînes de caractères, 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, dicts, etc), cela devient plus difficile, 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 éléments hachables, O(N log N) pour les éléments comparables non hachables, sinon c'est O(N au carré) et on ne peut rien y faire :-(.

Answer 3

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 le plus rapide.

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

Et au cas où le doublon se trouve en première position. Ceci est utile pour voir quelles sont les solutions qui court-circuitent :

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 était la plus rapide dans le cas sans doublon).

J'ai inclus une fonction de ma propre bibliothèque ici : iteration_utilities.all_distinct qui peut rivaliser avec la solution la plus rapide dans le cas de l'absence de doublons et fonctionne en temps constant pour le cas des doublons au début (bien qu'il ne soit pas le plus rapide).

Le code pour le 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()

Answer 4

Ce sujet est ancien, mais les réponses données ici m'ont conduit à une solution légèrement différente. Si vous êtes prêt à abuser des compréhensions, vous pouvez obtenir un 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))

Answer 5

Si vous aimez le style de programmation fonctionnelle, voici une fonction utile, un code auto-documenté et testé 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()

À partir 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 cela n'est pas efficace puisque vous construisez explicitement la décomposition. Mais dans la lignée de l'utilisation de reduce, vous pouvez arriver à quelque chose d'équivalent (mais légèrement 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