Como verifico se há duplicatas em uma lista simples?

Por exemplo, dada a lista ['one', 'two', 'one'], o algoritmo deve retornar True, enquanto que, dado ['one', 'two', 'three']que deve retornar False.

Use set()para remover duplicatas se todos os valores forem hashable :

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

Recomendado apenas para listas curtas :

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

Você não usar em uma longa lista - pode levar tempo proporcional ao quadrado do número de itens na lista!

Para listas mais longas com itens que podem ser lavados (cadeias, números etc.):

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

Se seus itens não forem laváveis ​​(sublistas, dictos, etc.), eles ficarão mais peludos, embora ainda seja possível obter O (N logN) se forem pelo menos comparáveis. Mas você precisa conhecer ou testar as características dos itens (lavável ou não, comparável ou não) para obter o melhor desempenho possível - O (N) para hashables, O (N log N) para comparáveis ​​não laváveis, caso contrário é O (N ao quadrado) e não há nada que se possa fazer sobre isso :-(.

Isso é antigo, mas as respostas aqui me levaram a uma solução ligeiramente diferente. Se você está disposto a abusar das compreensões, pode entrar em curto-circuito dessa maneira.

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

Se você gosta do estilo de programação funcional, aqui está uma função útil, código auto-documentado e testado 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()

A partir daí, você pode testar a unicidade verificando se o segundo elemento do par retornado está vazio:

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]

Observe que isso não é eficiente, pois você está construindo explicitamente a decomposição. Mas, na linha do uso de reduzir, você pode chegar a algo equivalente (mas um pouco 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

Eu pensei que seria útil comparar os horários das diferentes soluções apresentadas aqui. Para isso, usei minha própria biblioteca simple_benchmark:

Portanto, neste caso, a solução de Denis Otkidach é a mais rápida.

Algumas das abordagens também exibem uma curva muito mais íngreme; essas são abordagens quadráticas com o número de elementos (primeira solução de Alex Martellis, wjandrea e ambas as soluções de Xavier Decorets). Também é importante mencionar que a solução de pandas do Keiku tem um fator constante muito grande. Mas para listas maiores, quase alcança as outras soluções.

E caso a duplicata esteja na primeira posição. Isso é útil para ver quais soluções estão em curto-circuito:

Aqui, várias abordagens não causam um curto-circuito: Kaiku, Frank, Xavier_Decoret (primeira solução), Turn, Alex Martelli (primeira solução) e a abordagem apresentada por Denis Otkidach (que foi o mais rápido no caso sem duplicação).

Eu incluí uma função da minha própria biblioteca aqui: iteration_utilities.all_distinct que pode competir com a solução mais rápida no caso sem duplicatas e executa em tempo constante no caso de duplicação no início (embora não seja tão rápido).

O código para o 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)

E para os 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()

Recentemente, respondi a uma pergunta relacionada para estabelecer todas as duplicatas em uma lista, usando um gerador. Tem a vantagem de que, se usado apenas para estabelecer 'se houver uma duplicata', você precisará obter o primeiro item e o restante poderá ser ignorado, que é o atalho definitivo.

Esta é uma abordagem interessante baseada em conjuntos que adaptei diretamente do moooeeeep :

def getDupes(l):
    seen = set()
    seen_add = seen.add
    for x in l:
        if x in seen or seen_add(x):
            yield x

Assim, uma lista completa de bobagens seria list(getDupes(etc)). Para simplesmente testar "se" há um dupe, ele deve ser empacotado da seguinte maneira:

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

Isso se adapta bem e fornece tempos de operação consistentes onde quer que o dupe esteja na lista - testei com listas de entradas de até 1 milhão. Se você sabe algo sobre os dados, especificamente, que os dupes provavelmente aparecerão no primeiro semestre, ou outras coisas que permitem distorcer seus requisitos, como a necessidade de obter os dupes reais, existem alguns localizadores de dupe realmente alternativos que pode ter um desempenho superior. Os dois que eu recomendo são ...

Abordagem simples baseada em dict, muito legível:

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

Aproveite as ferramentas (essencialmente um ifilter / izip / tee) na lista classificada, muito eficiente se você estiver obtendo todos os truques, embora não seja tão rápido para obter apenas o primeiro:

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

Esses foram os melhores desempenhos das abordagens que tentei para a lista completa de enganados , com o primeiro ocorrendo em qualquer lugar de uma lista de elementos de 1 metro do começo ao meio. Foi surpreendente o quão pouco sobrecarga a etapa de classificação acrescentou. Sua milhagem pode variar, mas aqui estão meus 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

Outra maneira de fazer isso de forma sucinta é com o Counter .

Para determinar apenas se há duplicatas na 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

Ou, para obter uma lista de itens com duplicatas:

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

Descobri que esse desempenho era o melhor desempenho porque ele provoca um curto-circuito na operação quando foi duplicada, e esse algoritmo possui complexidade de tempo e espaço O (n) em que n é o comprimento da 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

Eu realmente não sei o que o set faz nos bastidores, então eu só gosto de manter as coisas simples.

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

Uma solução mais simples é a seguinte. Apenas marque True / False com o .duplicated()método pandas e depois faça a soma. Consulte também pandas.Series.duplicated - documentação do 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

Se a lista contiver itens laváveis, você pode usar a solução de Alex Martelli, mas com uma lista em vez de um conjunto, embora seja mais lento para entradas maiores: O (N ^ 2).

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

Eu usei a abordagem do pyrospade, por sua simplicidade, e modifiquei isso levemente em uma pequena lista feita a partir do registro do Windows que não diferencia maiúsculas de minúsculas.

Se a cadeia de valor PATH não processada for dividida em caminhos individuais, todos os caminhos 'nulos' (cadeias vazias ou somente espaços em branco) poderão ser removidos usando:

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

O PATH original possui entradas 'nulas' e duplicatas para fins de teste:

[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

Os caminhos nulos foram removidos, mas ainda possuem duplicatas, por exemplo, (1, 3) e (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\

E, finalmente, os burros foram removidos:

[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