¿Cómo verifico si hay duplicados en una lista plana?

Por ejemplo, dada la lista ['one', 'two', 'one'], el algoritmo debería regresar True, mientras que dado ['one', 'two', 'three']que debería regresar False.

Use set()para eliminar duplicados si todos los valores son hashables :

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

Recomendado solo para listas cortas :

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

No lo use en una lista larga: ¡puede llevar un tiempo proporcional al cuadrado del número de elementos en la lista!

Para listas más largas con elementos que se pueden compartir (cadenas, números, etc.):

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

Si sus artículos no son intercambiables (sublistas, dictados, etc.) se vuelve más complicado, aunque aún es posible obtener O (N logN) si son al menos comparables. Pero debe conocer o probar las características de los elementos (hashable o no, comparable o no) para obtener el mejor rendimiento posible: O (N) para hashables, O (N log N) para comparables no hashaable, de lo contrario se reduce a O (N al cuadrado) y no hay nada que se pueda hacer al respecto :-(.

Esto es viejo, pero las respuestas aquí me llevaron a una solución ligeramente diferente. Si está dispuesto a abusar de las comprensiones, puede hacer un cortocircuito de esta manera.

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 eres aficionado al estilo de programación funcional, aquí hay una función útil, código auto documentado y probado usando 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()

Desde allí, puede probar la unicidad comprobando si el segundo elemento del par devuelto está vacío:

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]

Tenga en cuenta que esto no es eficiente ya que está construyendo explícitamente la descomposición. Pero en la línea del uso de reducir, puede llegar a algo equivalente (pero un poco menos eficiente) para responder 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

Pensé que sería útil comparar los tiempos de las diferentes soluciones presentadas aquí. Para esto utilicé mi propia biblioteca simple_benchmark:

De hecho, para este caso, la solución de Denis Otkidach es la más rápida.

Algunos de los enfoques también exhiben una curva mucho más pronunciada, estos son los enfoques que se escalan de forma cuadrática con el número de elementos (la primera solución de Alex Martellis, wjandrea y ambas soluciones de Xavier Decorets). También es importante mencionar que la solución de pandas de Keiku tiene un factor constante muy grande. Pero para listas más grandes casi se pone al día con las otras soluciones.

Y en caso de que el duplicado esté en la primera posición. Esto es útil para ver qué soluciones están en cortocircuito:

Aquí varios enfoques no provocan un cortocircuito: Kaiku, Frank, Xavier_Decoret (primera solución), Turn, Alex Martelli (primera solución) y el enfoque presentado por Denis Otkidach (que fue el más rápido en el caso sin duplicado).

Incluí una función de mi propia biblioteca aquí: iteration_utilities.all_distinctque puede competir con la solución más rápida en el caso de no duplicados y funciona en tiempo constante para el caso de duplicar al comienzo (aunque no tan rápido).

El código para el punto de referencia:

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)

Y por los argumentos:

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

Hace poco respondí una pregunta relacionada para establecer todos los duplicados en una lista, usando un generador. Tiene la ventaja de que si se usa solo para establecer "si hay un duplicado", entonces solo necesita obtener el primer elemento y el resto puede ignorarse, que es el último atajo.

Este es un enfoque interesante basado en conjuntos que adapté directamente 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 consecuencia, una lista completa de engaños sería list(getDupes(etc)). Para probar simplemente "si" hay un engañado, debe envolverse de la siguiente manera:

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

Esto escala bien y proporciona tiempos de operación consistentes donde sea que esté el engañado en la lista: probé con listas de hasta 1 millón de entradas. Si sabe algo sobre los datos, específicamente, que es probable que aparezcan duplicados en la primera mitad u otras cosas que le permitan sesgar sus requisitos, como la necesidad de obtener los duplicados reales, entonces hay un par de localizadores de duplicados realmente alternativos eso podría superar. Los dos que recomiendo son ...

Enfoque simple basado en dict, muy legible:

def getDupes(c):
    d = {}
    for i in c:
        if i in d:
            if d[i]:
                yield i
                d[i] = False
        else:
            d[i] = True

Aproveche las herramientas iterativas (esencialmente un ifilter / izip / tee) en la lista ordenada, muy eficiente si está obteniendo todos los engaños, aunque no tan rápido para obtener solo el primero:

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

Estos fueron los mejores resultados de los enfoques que probé para la lista completa de duplicados , con el primer duplicado en cualquier lugar de una lista de elementos de 1 m desde el principio hasta el medio. Fue sorprendente lo poco que sobrepasó el paso de clasificación. Su millaje puede variar, pero aquí están mis resultados específicos cronometrados:

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

Otra forma de hacerlo de manera sucinta es con Counter .

Para determinar si hay duplicados en la lista original:

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

O para obtener una lista de elementos que tienen duplicados:

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

Encontré que esto hace el mejor rendimiento porque cortocircuita la operación cuando se encuentra el primer duplicado, luego este algoritmo tiene una complejidad de tiempo y espacio O (n) donde n es la longitud de la lista:

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

Realmente no sé qué set hace detrás de escena, así que solo quiero que sea 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

Una solución más simple es la siguiente. Simplemente marque Verdadero / Falso con el .duplicated()método pandas y luego tome la suma. Consulte también pandas.Series.duplicated - documentación de 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 lista contiene elementos no compartibles, puede usar la solución de Alex Martelli pero con una lista en lugar de un conjunto, aunque es más lenta para entradas más grandes: O (N ^ 2).

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

Utilicé el enfoque de pyrospade, por su simplicidad, y lo modifiqué ligeramente en una lista corta hecha del registro de Windows que no distingue entre mayúsculas y minúsculas.

Si la cadena de valor de RUTA sin procesar se divide en rutas individuales, todas las rutas 'nulas' (cadenas vacías o de espacio en blanco) pueden eliminarse utilizando:

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

La RUTA original tiene entradas 'nulas' y duplicadas para fines de prueba:

[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

Se han eliminado las rutas nulas, pero todavía tiene duplicados, por ejemplo, (1, 3) y (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\

Y finalmente, los engañados han sido eliminados:

[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