python - saber - ¿Cómo puedo verificar si hay duplicados en una lista plana?

saber si un elemento esta en una lista python

Question

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

Answer 1

Esto es viejo, pero las respuestas aquí me llevaron a una solución ligeramente diferente. Si está dispuesto a abusar de las comprensiones, puede sufrir 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))

Answer 2

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 se puede ignorar, que es el atajo definitivo.

Este es un enfoque basado en un conjunto interesante que moooeeeep 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 incautos sería una list(getDupes(etc)) . Para simplemente probar "si" hay un duplicado, debe ser envuelto de la siguiente manera:

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

Esto se escala bien y proporciona tiempos de operación consistentes dondequiera que el dupe esté en la lista - Probé con listas de hasta 1m de entradas. Si sabes algo sobre los datos, específicamente, que los engañados probablemente aparezcan en la primera mitad, u otras cosas que te permitan desvirtuar tus necesidades, como la necesidad de obtener los verdaderos engañadores, entonces hay un par de localizadores de engaños realmente alternativos. eso podría superar. Los dos que recomiendo son ...

Enfoque basado en dict simple, 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 los itertools (esencialmente un ifilter / izip / tee) en la lista ordenada, muy eficiente si obtiene todos los dupes aunque no tan rápido como para obtener 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 ejecutores de los enfoques que probé para la lista completa , con el primer engaño en cualquier lugar en una lista de elementos de 1 m desde el principio hasta el centro. Era sorprendente lo poco que sobrecargaba el paso de clasificación. Su kilometraje puede variar, pero aquí están mis resultados cronometrados específicos:

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 3

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):
    return Counter(l).most_common()[0][0] > 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]

Answer 4

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 de la cantidad de elementos en la lista.

Para listas más largas con elementos hashable (cadenas, números, & c):

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 lavables (sublistas, dicts, etc.) se vuelve más peludo, aunque aún es posible obtener O (N logN) si son al menos comparables. Pero necesita saber o probar las características de los artículos (hashable o no, comparables o no) para obtener el mejor rendimiento que pueda: O (N) para los hashables, O (N log N) para los elementos comparables que no se pueden procesar, de lo contrario se trata de O (N al cuadrado) y no hay nada que uno pueda hacer al respecto :-(.

Answer 5

Si le gusta el 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 unicity 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 a lo largo de la línea de usar 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

Answer 6

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

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