Como encontro as duplicatas em uma lista e crio outra lista com elas?

437

Como posso encontrar as duplicatas em uma lista Python e criar outra lista das duplicatas? A lista contém apenas números inteiros.

MFB
fonte
1
você quer as duplicatas uma vez ou toda vez que são vistas novamente?
moooeeeep
Acho que isso foi respondido com muita eficiência aqui. stackoverflow.com/a/642919/1748045 intersecção é construído em um método de conjunto e deve fazer exatamente o que é necessário
Tom Smith

Respostas:

544

Para remover duplicatas, use set(a). Para imprimir duplicatas, algo como:

a = [1,2,3,2,1,5,6,5,5,5]

import collections
print([item for item, count in collections.Counter(a).items() if count > 1])

## [1, 2, 5]

Observe que Counternão é particularmente eficiente ( tempos ) e provavelmente é um exagero aqui. setterá um desempenho melhor. Este código calcula uma lista de elementos exclusivos na ordem de origem:

seen = set()
uniq = []
for x in a:
    if x not in seen:
        uniq.append(x)
        seen.add(x)

ou, mais concisamente:

seen = set()
uniq = [x for x in a if x not in seen and not seen.add(x)]    

Eu não recomendo o último estilo, porque não é óbvio o que not seen.add(x)está fazendo (o add()método set sempre retorna None, daí a necessidade not).

Para calcular a lista de elementos duplicados sem bibliotecas:

seen = {}
dupes = []

for x in a:
    if x not in seen:
        seen[x] = 1
    else:
        if seen[x] == 1:
            dupes.append(x)
        seen[x] += 1

Se os elementos da lista não forem hasháveis, você não poderá usar sets / dicts e precisará recorrer a uma solução de tempo quadrático (compare cada um com cada um). Por exemplo:

a = [[1], [2], [3], [1], [5], [3]]

no_dupes = [x for n, x in enumerate(a) if x not in a[:n]]
print no_dupes # [[1], [2], [3], [5]]

dupes = [x for n, x in enumerate(a) if x in a[:n]]
print dupes # [[1], [3]]
georg
fonte
2
@eric: Eu acho que é O(n), porque apenas itera a lista uma vez e as pesquisas definidas são O(1).
Georg
3
@ Hugo, para ver a lista de duplicatas, precisamos apenas criar uma nova lista chamada dup e adicionar uma instrução else. Por exemplo:dup = [] else: dup.append(x)
Chris Nielsen
4
@oxeimon: você provavelmente conseguiu isso, mas você imprime é chamado entre parênteses em python 3print()
Moberg 28/16
4
convertendo sua resposta para set () para obter apenas duplicatas. seen = set()entãodupe = set(x for x in a if x in seen or seen.add(x))
Ta946 07/04/19
2
Para Python 3.x: print ([item para o item, contam na collections.Counter (a) .items () se count> 1])
kibitzforu
327
>>> l = [1,2,3,4,4,5,5,6,1]
>>> set([x for x in l if l.count(x) > 1])
set([1, 4, 5])
Ritesh Kumar
fonte
2
Existe algum motivo para você usar uma compreensão de lista em vez de compreensão de gerador?
64
De fato, uma solução simples, mas a complexidade é elevada porque cada count () analisa a lista novamente, portanto, não use para listas grandes.
21715 Danuker
4
@JohnJ, o tipo de bolha também é simples e funciona. Isso não significa que devemos usá-lo!
John La Rooy
@JohnLaRooy Na verdade, isso significa que não devemos usá-lo, porque quase sempre existe uma maneira mais eficiente (e mais simples) de classificar.
lostsoul29
1
@ watsonic: Seu "interruptor simples" falha ao reduzir a complexidade do tempo de quadrático para quadrado no caso geral. Substituir lpor set(l)apenas reduz a complexidade do pior momento e, portanto, não faz nada para resolver as preocupações de eficiência em larga escala com esta resposta. Provavelmente não era tão simples, afinal. Em suma, não faça isso.
23917 Cecil Curry
82

Você não precisa da contagem, apenas se o item foi visto antes. Adaptado que responde a este problema:

def list_duplicates(seq):
  seen = set()
  seen_add = seen.add
  # adds all elements it doesn't know yet to seen and all other to seen_twice
  seen_twice = set( x for x in seq if x in seen or seen_add(x) )
  # turn the set into a list (as requested)
  return list( seen_twice )

a = [1,2,3,2,1,5,6,5,5,5]
list_duplicates(a) # yields [1, 2, 5]

Caso a velocidade seja importante, aqui estão alguns horários:

# file: test.py
import collections

def thg435(l):
    return [x for x, y in collections.Counter(l).items() if y > 1]

def moooeeeep(l):
    seen = set()
    seen_add = seen.add
    # adds all elements it doesn't know yet to seen and all other to seen_twice
    seen_twice = set( x for x in l if x in seen or seen_add(x) )
    # turn the set into a list (as requested)
    return list( seen_twice )

def RiteshKumar(l):
    return list(set([x for x in l if l.count(x) > 1]))

def JohnLaRooy(L):
    seen = set()
    seen2 = set()
    seen_add = seen.add
    seen2_add = seen2.add
    for item in L:
        if item in seen:
            seen2_add(item)
        else:
            seen_add(item)
    return list(seen2)

l = [1,2,3,2,1,5,6,5,5,5]*100

Aqui estão os resultados: (bem feito @JohnLaRooy!)

$ python -mtimeit -s 'import test' 'test.JohnLaRooy(test.l)'
10000 loops, best of 3: 74.6 usec per loop
$ python -mtimeit -s 'import test' 'test.moooeeeep(test.l)'
10000 loops, best of 3: 91.3 usec per loop
$ python -mtimeit -s 'import test' 'test.thg435(test.l)'
1000 loops, best of 3: 266 usec per loop
$ python -mtimeit -s 'import test' 'test.RiteshKumar(test.l)'
100 loops, best of 3: 8.35 msec per loop

Curiosamente, além dos horários, o ranking também muda levemente quando o pypy é usado. O mais interessante é que a abordagem baseada em contador se beneficia enormemente das otimizações do pypy, enquanto a abordagem de cache do método que sugeri parece não ter quase nenhum efeito.

$ pypy -mtimeit -s 'import test' 'test.JohnLaRooy(test.l)'
100000 loops, best of 3: 17.8 usec per loop
$ pypy -mtimeit -s 'import test' 'test.thg435(test.l)'
10000 loops, best of 3: 23 usec per loop
$ pypy -mtimeit -s 'import test' 'test.moooeeeep(test.l)'
10000 loops, best of 3: 39.3 usec per loop

Aparentemente, esse efeito está relacionado à "duplicidade" dos dados de entrada. Eu configurei l = [random.randrange(1000000) for i in xrange(10000)]e obtive estes resultados:

$ pypy -mtimeit -s 'import test' 'test.moooeeeep(test.l)'
1000 loops, best of 3: 495 usec per loop
$ pypy -mtimeit -s 'import test' 'test.JohnLaRooy(test.l)'
1000 loops, best of 3: 499 usec per loop
$ pypy -mtimeit -s 'import test' 'test.thg435(test.l)'
1000 loops, best of 3: 1.68 msec per loop
moooeeeep
fonte
6
Apenas curioso - qual é o objetivo de seen_add = seen.add aqui?
22412 Rob
3
@ Rob Desta maneira, você acabou de chamar a função que procurou uma vez antes. Caso contrário, você precisaria procurar (uma consulta no dicionário) a função de membro addtoda vez que uma inserção fosse necessária.
precisa saber é o seguinte
verifiquei com meus próprios dados e o% de tempo do Ipython; seu método parece mais rápido no teste, MAS: "A execução mais lenta demorou 4,34 vezes mais que a mais rápida. Isso pode significar que um resultado intermediário está sendo armazenado em cache"
Joop
1
@moooeeeep, eu adicionei outra versão ao seu script para você tentar :) Tente também pypyse você tiver à mão e estiver indo para a velocidade.
John La Rooy
@JohnLaRooy Boa melhoria no desempenho! Curiosamente, quando usei o pypy para avaliar os resultados, a abordagem baseada em contador melhora significativamente.
moooeeeep
42

Você pode usar iteration_utilities.duplicates:

>>> from iteration_utilities import duplicates

>>> list(duplicates([1,1,2,1,2,3,4,2]))
[1, 1, 2, 2]

ou se você deseja apenas uma duplicata, isso pode ser combinado com iteration_utilities.unique_everseen:

>>> from iteration_utilities import unique_everseen

>>> list(unique_everseen(duplicates([1,1,2,1,2,3,4,2])))
[1, 2]

Ele também pode lidar com elementos laváveis ​​(no entanto, ao custo de desempenho):

>>> list(duplicates([[1], [2], [1], [3], [1]]))
[[1], [1]]

>>> list(unique_everseen(duplicates([[1], [2], [1], [3], [1]])))
[[1]]

Isso é algo que apenas algumas das outras abordagens aqui podem lidar.

Benchmarks

Fiz um rápido benchmark contendo a maioria (mas não todas) das abordagens mencionadas aqui.

A primeira referência incluiu apenas um pequeno intervalo de comprimentos de lista, porque algumas abordagens têm O(n**2)comportamento.

Nos gráficos, o eixo y representa o tempo, portanto, um valor mais baixo significa melhor. Também é plotado log-log para que a ampla gama de valores possa ser melhor visualizada:

insira a descrição da imagem aqui

Removendo as O(n**2)abordagens, fiz outro benchmark de até meio milhão de elementos em uma lista:

insira a descrição da imagem aqui

Como você pode ver, a iteration_utilities.duplicatesabordagem é mais rápida do que qualquer uma das outras abordagens e até o encadeamento unique_everseen(duplicates(...))foi mais rápido ou igualmente rápido do que as outras abordagens.

Outra coisa interessante a ser observada aqui é que as abordagens dos pandas são muito lentas para listas pequenas, mas podem competir facilmente por listas mais longas.

No entanto, como esses benchmarks mostram que a maioria das abordagens tem desempenho aproximadamente igual, não importa muito qual delas é usada (exceto as três que tiveram O(n**2)tempo de execução).

from iteration_utilities import duplicates, unique_everseen
from collections import Counter
import pandas as pd
import itertools

def georg_counter(it):
    return [item for item, count in Counter(it).items() if count > 1]

def georg_set(it):
    seen = set()
    uniq = []
    for x in it:
        if x not in seen:
            uniq.append(x)
            seen.add(x)

def georg_set2(it):
    seen = set()
    return [x for x in it if x not in seen and not seen.add(x)]   

def georg_set3(it):
    seen = {}
    dupes = []

    for x in it:
        if x not in seen:
            seen[x] = 1
        else:
            if seen[x] == 1:
                dupes.append(x)
            seen[x] += 1

def RiteshKumar_count(l):
    return set([x for x in l if l.count(x) > 1])

def moooeeeep(seq):
    seen = set()
    seen_add = seen.add
    # adds all elements it doesn't know yet to seen and all other to seen_twice
    seen_twice = set( x for x in seq if x in seen or seen_add(x) )
    # turn the set into a list (as requested)
    return list( seen_twice )

def F1Rumors_implementation(c):
    a, b = itertools.tee(sorted(c))
    next(b, None)
    r = None
    for k, g in zip(a, b):
        if k != g: continue
        if k != r:
            yield k
            r = k

def F1Rumors(c):
    return list(F1Rumors_implementation(c))

def Edward(a):
    d = {}
    for elem in a:
        if elem in d:
            d[elem] += 1
        else:
            d[elem] = 1
    return [x for x, y in d.items() if y > 1]

def wordsmith(a):
    return pd.Series(a)[pd.Series(a).duplicated()].values

def NikhilPrabhu(li):
    li = li.copy()
    for x in set(li):
        li.remove(x)

    return list(set(li))

def firelynx(a):
    vc = pd.Series(a).value_counts()
    return vc[vc > 1].index.tolist()

def HenryDev(myList):
    newList = set()

    for i in myList:
        if myList.count(i) >= 2:
            newList.add(i)

    return list(newList)

def yota(number_lst):
    seen_set = set()
    duplicate_set = set(x for x in number_lst if x in seen_set or seen_set.add(x))
    return seen_set - duplicate_set

def IgorVishnevskiy(l):
    s=set(l)
    d=[]
    for x in l:
        if x in s:
            s.remove(x)
        else:
            d.append(x)
    return d

def it_duplicates(l):
    return list(duplicates(l))

def it_unique_duplicates(l):
    return list(unique_everseen(duplicates(l)))

Referência 1

from simple_benchmark import benchmark
import random

funcs = [
    georg_counter, georg_set, georg_set2, georg_set3, RiteshKumar_count, moooeeeep, 
    F1Rumors, Edward, wordsmith, NikhilPrabhu, firelynx,
    HenryDev, yota, IgorVishnevskiy, it_duplicates, it_unique_duplicates
]

args = {2**i: [random.randint(0, 2**(i-1)) for _ in range(2**i)] for i in range(2, 12)}

b = benchmark(funcs, args, 'list size')

b.plot()

Referência 2

funcs = [
    georg_counter, georg_set, georg_set2, georg_set3, moooeeeep, 
    F1Rumors, Edward, wordsmith, firelynx,
    yota, IgorVishnevskiy, it_duplicates, it_unique_duplicates
]

args = {2**i: [random.randint(0, 2**(i-1)) for _ in range(2**i)] for i in range(2, 20)}

b = benchmark(funcs, args, 'list size')
b.plot()

aviso Legal

1 Esta é a partir de uma biblioteca de terceiros que tenho escrito: iteration_utilities.

MSeifert
fonte
1
Vou enfiar meu pescoço aqui e sugerir que escrever uma biblioteca sob medida para fazer o trabalho em C, em vez de Python, provavelmente não seja o espírito da resposta que estava sendo procurada - mas essa é uma abordagem legítima! Gosto da largura da resposta e da exibição gráfica dos resultados - muito bom ver que eles estão convergindo, me faz pensar se eles se cruzam à medida que as entradas aumentam ainda mais! Pergunta: qual é o resultado das listas classificadas principalmente em oposição às listas completamente aleatórias?
F1Rumors 17/10/2018
30

Eu me deparei com essa pergunta enquanto olhava para algo relacionado - e me pergunto por que ninguém ofereceu uma solução baseada em gerador? Resolver esse problema seria:

>>> print list(getDupes_9([1,2,3,2,1,5,6,5,5,5]))
[1, 2, 5]

Eu estava preocupado com a escalabilidade, então testei várias abordagens, incluindo itens ingênuos que funcionam bem em pequenas listas, mas escalam horrivelmente à medida que as listas ficam maiores (nota: seria melhor usar o tempo, mas isso é ilustrativo).

Eu incluí o @moooeeeep para comparação (é impressionantemente rápido: mais rápido se a lista de entradas for completamente aleatória) e uma abordagem de iterais que é ainda mais rápida para as listas classificadas ... Agora inclui a abordagem de pandas do @firelynx - lenta, mas não terrivelmente e simples. Nota - a abordagem de ordenação / tee / zip é consistentemente mais rápida na minha máquina para listas grandes e ordenadas, o moooeeeep é mais rápido para listas embaralhadas, mas sua milhagem pode variar.

Vantagens

  • muito rápido, simples de testar duplicatas 'any' usando o mesmo código

Premissas

  • As duplicatas devem ser relatadas apenas uma vez
  • A ordem duplicada não precisa ser preservada
  • A duplicata pode estar em qualquer lugar da lista

Solução mais rápida, 1 milhão de entradas:

def getDupes(c):
        '''sort/tee/izip'''
        a, b = itertools.tee(sorted(c))
        next(b, None)
        r = None
        for k, g in itertools.izip(a, b):
            if k != g: continue
            if k != r:
                yield k
                r = k

Abordagens testadas

import itertools
import time
import random

def getDupes_1(c):
    '''naive'''
    for i in xrange(0, len(c)):
        if c[i] in c[:i]:
            yield c[i]

def getDupes_2(c):
    '''set len change'''
    s = set()
    for i in c:
        l = len(s)
        s.add(i)
        if len(s) == l:
            yield i

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

def getDupes_4(c):
    '''in set'''
    s,r = set(),set()
    for i in c:
        if i not in s:
            s.add(i)
        elif i not in r:
            r.add(i)
            yield i

def getDupes_5(c):
    '''sort/adjacent'''
    c = sorted(c)
    r = None
    for i in xrange(1, len(c)):
        if c[i] == c[i - 1]:
            if c[i] != r:
                yield c[i]
                r = c[i]

def getDupes_6(c):
    '''sort/groupby'''
    def multiple(x):
        try:
            x.next()
            x.next()
            return True
        except:
            return False
    for k, g in itertools.ifilter(lambda x: multiple(x[1]), itertools.groupby(sorted(c))):
        yield k

def getDupes_7(c):
    '''sort/zip'''
    c = sorted(c)
    r = None
    for k, g in zip(c[:-1],c[1:]):
        if k == g:
            if k != r:
                yield k
                r = k

def getDupes_8(c):
    '''sort/izip'''
    c = sorted(c)
    r = None
    for k, g in itertools.izip(c[:-1],c[1:]):
        if k == g:
            if k != r:
                yield k
                r = k

def getDupes_9(c):
    '''sort/tee/izip'''
    a, b = itertools.tee(sorted(c))
    next(b, None)
    r = None
    for k, g in itertools.izip(a, b):
        if k != g: continue
        if k != r:
            yield k
            r = k

def getDupes_a(l):
    '''moooeeeep'''
    seen = set()
    seen_add = seen.add
    # adds all elements it doesn't know yet to seen and all other to seen_twice
    for x in l:
        if x in seen or seen_add(x):
            yield x

def getDupes_b(x):
    '''iter*/sorted'''
    x = sorted(x)
    def _matches():
        for k,g in itertools.izip(x[:-1],x[1:]):
            if k == g:
                yield k
    for k, n in itertools.groupby(_matches()):
        yield k

def getDupes_c(a):
    '''pandas'''
    import pandas as pd
    vc = pd.Series(a).value_counts()
    i = vc[vc > 1].index
    for _ in i:
        yield _

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

def getDupes(fn,c):
    return list(fn(c))

STABLE = True
if STABLE:
    print 'Finding FIRST then ALL duplicates, single dupe of "nth" placed element in 1m element array'
else:
    print 'Finding FIRST then ALL duplicates, single dupe of "n" included in randomised 1m element array'
for location in (50,250000,500000,750000,999999):
    for test in (getDupes_2, getDupes_3, getDupes_4, getDupes_5, getDupes_6,
                 getDupes_8, getDupes_9, getDupes_a, getDupes_b, getDupes_c):
        print 'Test %-15s:%10d - '%(test.__doc__ or test.__name__,location),
        deltas = []
        for FIRST in (True,False):
            for i in xrange(0, 5):
                c = range(0,1000000)
                if STABLE:
                    c[0] = location
                else:
                    c.append(location)
                    random.shuffle(c)
                start = time.time()
                if FIRST:
                    print '.' if location == test(c).next() else '!',
                else:
                    print '.' if [location] == list(test(c)) else '!',
                deltas.append(time.time()-start)
            print ' -- %0.3f  '%(sum(deltas)/len(deltas)),
        print
    print

Os resultados para o teste 'todos os enganados' foram consistentes, encontrando duplicatas "primeiro" e depois duplicatas "todos" nesta matriz:

Finding FIRST then ALL duplicates, single dupe of "nth" placed element in 1m element array
Test set len change :    500000 -  . . . . .  -- 0.264   . . . . .  -- 0.402  
Test in dict        :    500000 -  . . . . .  -- 0.163   . . . . .  -- 0.250  
Test in set         :    500000 -  . . . . .  -- 0.163   . . . . .  -- 0.249  
Test sort/adjacent  :    500000 -  . . . . .  -- 0.159   . . . . .  -- 0.229  
Test sort/groupby   :    500000 -  . . . . .  -- 0.860   . . . . .  -- 1.286  
Test sort/izip      :    500000 -  . . . . .  -- 0.165   . . . . .  -- 0.229  
Test sort/tee/izip  :    500000 -  . . . . .  -- 0.145   . . . . .  -- 0.206  *
Test moooeeeep      :    500000 -  . . . . .  -- 0.149   . . . . .  -- 0.232  
Test iter*/sorted   :    500000 -  . . . . .  -- 0.160   . . . . .  -- 0.221  
Test pandas         :    500000 -  . . . . .  -- 0.493   . . . . .  -- 0.499  

Quando as listas são embaralhadas primeiro, o preço do tipo se torna aparente - a eficiência cai visivelmente e a abordagem @moooeeeep domina, com as abordagens set & dict sendo semelhantes, mas com desempenho inferior:

Finding FIRST then ALL duplicates, single dupe of "n" included in randomised 1m element array
Test set len change :    500000 -  . . . . .  -- 0.321   . . . . .  -- 0.473  
Test in dict        :    500000 -  . . . . .  -- 0.285   . . . . .  -- 0.360  
Test in set         :    500000 -  . . . . .  -- 0.309   . . . . .  -- 0.365  
Test sort/adjacent  :    500000 -  . . . . .  -- 0.756   . . . . .  -- 0.823  
Test sort/groupby   :    500000 -  . . . . .  -- 1.459   . . . . .  -- 1.896  
Test sort/izip      :    500000 -  . . . . .  -- 0.786   . . . . .  -- 0.845  
Test sort/tee/izip  :    500000 -  . . . . .  -- 0.743   . . . . .  -- 0.804  
Test moooeeeep      :    500000 -  . . . . .  -- 0.234   . . . . .  -- 0.311  *
Test iter*/sorted   :    500000 -  . . . . .  -- 0.776   . . . . .  -- 0.840  
Test pandas         :    500000 -  . . . . .  -- 0.539   . . . . .  -- 0.540  
F1Rumors
fonte
@moooeeeep - tenha interesse em ver suas opiniões sobre a abordagem ifilter / izip / tee.
F1Rumors
1
esta resposta é incrivelmente boa. Não entendo que não tenha tido mais pontos para as explicações e testes que são muito úteis para aqueles que precisariam.
dlewin
1
A classificação do python é O (n) quando apenas um item está fora de ordem. Você deve random.shuffle(c)dar conta disso. Além disso, também não consigo replicar seus resultados ao executar o script inalterado (ordenação totalmente diferente), talvez também seja dependente da CPU.
John La Rooy
Obrigado @ John-La-Rooy, a observação astuta na CPU / máquina local foi impactante - por isso devo alterar o item YYMV . O uso da classificação O (n) foi deliberado: o elemento duplicativo é inserido em locais diferentes, especificamente para ver o impacto da abordagem, se houver apenas uma duplicata em um local bom (início da lista) ou ruim (final da lista) com esses elementos. abordagens. Eu considerei uma lista aleatória - por exemplo, random.shuffle - mas decidi que só seria sensato se eu fizesse muito mais execuções! Terei que retornar e comparar um equivalente de execução / reprodução aleatória múltipla e ver qual é o impacto.
F1Rumors
Alterado para incluir a abordagem @firelynx pandas e para executar na lista totalmente embaralhada, bem como na lista classificada. Isso ocorre porque o timsort nativo usado pelo Python é mau rápido em dados principalmente ordenados (melhor caso) e as listas embaralhadas são o seu pior cenário - que sacode os resultados.
F1Rumors
13

Usando pandas:

>>> import pandas as pd
>>> a = [1, 2, 1, 3, 3, 3, 0]
>>> pd.Series(a)[pd.Series(a).duplicated()].values
array([1, 3, 3])
escritor
fonte
10

O contador é novo no python 2.7:


Python 2.5.4 (r254:67916, May 31 2010, 15:03:39) 
[GCC 4.1.2 20080704 (Red Hat 4.1.2-46)] on linux2
a = [1,2,3,2,1,5,6,5,5,5]
import collections
print [x for x, y in collections.Counter(a).items() if y > 1]
Type "help", "copyright", "credits" or "license" for more information.
  File "", line 1, in 
AttributeError: 'module' object has no attribute 'Counter'
>>> 

Em uma versão anterior, você pode usar um ditado convencional:

a = [1,2,3,2,1,5,6,5,5,5]
d = {}
for elem in a:
    if elem in d:
        d[elem] += 1
    else:
        d[elem] = 1

print [x for x, y in d.items() if y > 1]
Edward
fonte
9

Aqui está uma solução pura e concisa -

for x in set(li):
    li.remove(x)

li = list(set(li))
Nikhil Prabhu
fonte
A lista original está perdida, no entanto. Isto pode ser corrigido através da cópia dos conteúdos para outra lista - temp = li [:]
Nikhil Prabhu
3
Esse é um exercício bastante desagradável para listas grandes - remover elementos das listas é muito caro!
F1Rumors 23/08/19
7

Sem converter para lista e provavelmente a maneira mais simples seria algo como abaixo. Isso pode ser útil durante uma entrevista quando eles pedem para não usar conjuntos

a=[1,2,3,3,3]
dup=[]
for each in a:
  if each not in dup:
    dup.append(each)
print(dup)

======= else para obter 2 listas separadas de valores exclusivos e valores duplicados

a=[1,2,3,3,3]
uniques=[]
dups=[]

for each in a:
  if each not in uniques:
    uniques.append(each)
  else:
    dups.append(each)
print("Unique values are below:")
print(uniques)
print("Duplicate values are below:")
print(dups)
Chetan_Vasudevan
fonte
1
Porém, isso não resulta em uma lista de duplicatas de uma (ou na lista original), mas em uma lista de todos os elementos exclusivos de uma (ou na lista original). O que alguém faria depois que terminasse de formar a lista "dup"?
gameCoder95
6

Eu faria isso com os pandas, porque eu uso muito os pandas

import pandas as pd
a = [1,2,3,3,3,4,5,6,6,7]
vc = pd.Series(a).value_counts()
vc[vc > 1].index.tolist()

[3,6]

Provavelmente não é muito eficiente, mas com certeza é menos código do que muitas outras respostas, então pensei em contribuir

firelynx
fonte
3
Note-se também que os pandas contém uma função interna de duplicados pda = pd.Series(a) print list(pda[pda.duplicated()])
Len Blokken
6

o terceiro exemplo da resposta aceita fornece uma resposta incorreta e não tenta fornecer duplicatas. Aqui está a versão correta:

number_lst = [1, 1, 2, 3, 5, ...]

seen_set = set()
duplicate_set = set(x for x in number_lst if x in seen_set or seen_set.add(x))
unique_set = seen_set - duplicate_set
yota
fonte
6

Que tal simplesmente percorrer cada elemento da lista, verificando o número de ocorrências e adicionando-as a um conjunto que imprimirá as duplicatas. Espero que isto seja útil a alguém.

myList  = [2 ,4 , 6, 8, 4, 6, 12];
newList = set()

for i in myList:
    if myList.count(i) >= 2:
        newList.add(i)

print(list(newList))
## [4 , 6]
HenryDev
fonte
5

Podemos usar itertools.groupbypara encontrar todos os itens que possuem dups:

from itertools import groupby

myList  = [2, 4, 6, 8, 4, 6, 12]
# when the list is sorted, groupby groups by consecutive elements which are similar
for x, y in groupby(sorted(myList)):
    #  list(y) returns all the occurences of item x
    if len(list(y)) > 1:
        print x  

A saída será:

4
6
alfasin
fonte
1
Ou, mais concisamente:dupes = [x for x, y in groupby(sorted(myList)) if len(list(y)) > 1]
frnhr 9/12/19
5

Eu acho que a maneira mais eficaz de encontrar duplicatas em uma lista é:

from collections import Counter

def duplicates(values):
    dups = Counter(values) - Counter(set(values))
    return list(dups.keys())

print(duplicates([1,2,3,6,5,2]))

Ele usa Countertodos os elementos e todos os elementos exclusivos. Subtrair o primeiro pelo segundo deixará de fora apenas as duplicatas.

Anand Chitipothu
fonte
4

Um pouco tarde, mas talvez seja útil para alguns. Para uma lista ampla, achei que isso funcionou para mim.

l=[1,2,3,5,4,1,3,1]
s=set(l)
d=[]
for x in l:
    if x in s:
        s.remove(x)
    else:
        d.append(x)
d
[1,3,1]

Mostra apenas e todas as duplicatas e preserva a ordem.

user3109122
fonte
3

Uma maneira muito simples e rápida de encontrar enganos com uma iteração no Python é:

testList = ['red', 'blue', 'red', 'green', 'blue', 'blue']

testListDict = {}

for item in testList:
  try:
    testListDict[item] += 1
  except:
    testListDict[item] = 1

print testListDict

A saída será a seguinte:

>>> print testListDict
{'blue': 3, 'green': 1, 'red': 2}

Isso e muito mais no meu blog http://www.howtoprogramwithpython.com

Igor Vishnevskiy
fonte
3

Estou entrando muito tarde nessa discussão. Mesmo assim, eu gostaria de lidar com esse problema com um liners. Porque esse é o charme do Python. se apenas queremos obter as duplicatas em uma lista separada (ou em qualquer coleção), sugiro que faça o seguinte: diga que temos uma lista duplicada que podemos chamar de 'destino'

    target=[1,2,3,4,4,4,3,5,6,8,4,3]

Agora, se quisermos obter as duplicatas, podemos usar o liner a seguir:

    duplicates=dict(set((x,target.count(x)) for x in filter(lambda rec : target.count(rec)>1,target)))

Este código colocará os registros duplicados como chave e contará como valor no dicionário 'duplicatas'. O dicionário 'duplicado' terá a seguinte aparência:

    {3: 3, 4: 4} #it saying 3 is repeated 3 times and 4 is 4 times

Se você deseja apenas todos os registros com duplicatas sozinhos em uma lista, é novamente um código muito menor:

    duplicates=filter(lambda rec : target.count(rec)>1,target)

A saída será:

    [3, 4, 4, 4, 3, 4, 3]

Funciona perfeitamente nas versões python 2.7.x +

akhil pathirippilly
fonte
3

Python 3.8 one-liner, se você não quiser escrever seu próprio algoritmo ou usar bibliotecas:

l = [1,2,3,2,1,5,6,5,5,5]

res = [(x, count) for x, g in groupby(sorted(l)) if (count := len(list(g))) > 1]

print(res)

Imprime item e conta:

[(1, 2), (2, 2), (5, 4)]

groupby utiliza uma função de agrupamento para que você possa definir seus agrupamentos de maneiras diferentes e retornar Tuple campos conforme necessário.

groupby é preguiçoso, por isso não deve ser muito lento.

yǝsʞǝla
fonte
2

Alguns outros testes. Claro que fazer ...

set([x for x in l if l.count(x) > 1])

... é muito caro. É cerca de 500 vezes mais rápido (a matriz mais longa fornece melhores resultados) para usar o próximo método final:

def dups_count_dict(l):
    d = {}

    for item in l:
        if item not in d:
            d[item] = 0

        d[item] += 1

    result_d = {key: val for key, val in d.iteritems() if val > 1}

    return result_d.keys()

Apenas 2 loops, sem l.count()operações muito caras .

Aqui está um código para comparar os métodos, por exemplo. O código está abaixo, aqui está a saída:

dups_count: 13.368s # this is a function which uses l.count()
dups_count_dict: 0.014s # this is a final best function (of the 3 functions)
dups_count_counter: 0.024s # collections.Counter

O código de teste:

import numpy as np
from time import time
from collections import Counter

class TimerCounter(object):
    def __init__(self):
        self._time_sum = 0

    def start(self):
        self.time = time()

    def stop(self):
        self._time_sum += time() - self.time

    def get_time_sum(self):
        return self._time_sum


def dups_count(l):
    return set([x for x in l if l.count(x) > 1])


def dups_count_dict(l):
    d = {}

    for item in l:
        if item not in d:
            d[item] = 0

        d[item] += 1

    result_d = {key: val for key, val in d.iteritems() if val > 1}

    return result_d.keys()


def dups_counter(l):
    counter = Counter(l)    

    result_d = {key: val for key, val in counter.iteritems() if val > 1}

    return result_d.keys()



def gen_array():
    np.random.seed(17)
    return list(np.random.randint(0, 5000, 10000))


def assert_equal_results(*results):
    primary_result = results[0]
    other_results = results[1:]

    for other_result in other_results:
        assert set(primary_result) == set(other_result) and len(primary_result) == len(other_result)


if __name__ == '__main__':
    dups_count_time = TimerCounter()
    dups_count_dict_time = TimerCounter()
    dups_count_counter = TimerCounter()

    l = gen_array()

    for i in range(3):
        dups_count_time.start()
        result1 = dups_count(l)
        dups_count_time.stop()

        dups_count_dict_time.start()
        result2 = dups_count_dict(l)
        dups_count_dict_time.stop()

        dups_count_counter.start()
        result3 = dups_counter(l)
        dups_count_counter.stop()

        assert_equal_results(result1, result2, result3)

    print 'dups_count: %.3f' % dups_count_time.get_time_sum()
    print 'dups_count_dict: %.3f' % dups_count_dict_time.get_time_sum()
    print 'dups_count_counter: %.3f' % dups_count_counter.get_time_sum()
sergzach
fonte
2

Método 1:

list(set([val for idx, val in enumerate(input_list) if val in input_list[idx+1:]]))

Explicação: [val para idx, val in enumerate (input_list) se val em input_list [idx + 1:]] é uma compreensão de lista, que retorna um elemento, se o mesmo elemento estiver presente em sua posição atual, na lista, o índice .

Exemplo: input_list = [42,31,42,31,3,31,31,5,6,6,6,6,6,7,42]

começando com o primeiro elemento da lista, 42, com o índice 0, verifica se o elemento 42 está presente na input_list [1:] (ou seja, do índice 1 até o final da lista) Como 42 está presente na input_list [1:] , retornará 42.

Em seguida, ele passa para o próximo elemento 31, com o índice 1, e verifica se o elemento 31 está presente na input_list [2:] (ou seja, do índice 2 até o final da lista), porque 31 está presente na input_list [2:], retornará 31.

Da mesma forma, ele percorre todos os elementos da lista e retornará apenas os elementos repetidos / duplicados para uma lista.

Então, porque temos duplicados, em uma lista, precisamos escolher um de cada duplicado, ou seja, remover duplicado entre duplicados e, para fazer isso, chamamos um python interno incorporado chamado set (), e ele remove os duplicados,

Ficamos com um conjunto, mas não uma lista, e, portanto, para converter de um conjunto em lista, usamos tipecasting, list () e isso converte o conjunto de elementos em uma lista.

Método 2:

def dupes(ilist):
    temp_list = [] # initially, empty temporary list
    dupe_list = [] # initially, empty duplicate list
    for each in ilist:
        if each in temp_list: # Found a Duplicate element
            if not each in dupe_list: # Avoid duplicate elements in dupe_list
                dupe_list.append(each) # Add duplicate element to dupe_list
        else: 
            temp_list.append(each) # Add a new (non-duplicate) to temp_list

    return dupe_list

Explicação: Aqui Criamos duas listas vazias, para começar. Continue percorrendo todos os elementos da lista, para ver se existe em temp_list (inicialmente vazio). Se não estiver na lista_ temp, então a adicionamos à lista_ temp, usando o método append .

Se ele já existe no temp_list, significa que o elemento atual da lista é duplicado e, portanto, precisamos adicioná-lo ao dupe_list usando o método append .

S471
fonte
2
raw_list = [1,2,3,3,4,5,6,6,7,2,3,4,2,3,4,1,3,4,]

clean_list = list(set(raw_list))
duplicated_items = []

for item in raw_list:
    try:
        clean_list.remove(item)
    except ValueError:
        duplicated_items.append(item)


print(duplicated_items)
# [3, 6, 2, 3, 4, 2, 3, 4, 1, 3, 4]

Basicamente, você remove duplicatas convertendo para set ( clean_list) e itera o arquivo raw_list, enquanto remove cada um itemda lista limpa para ocorrência em raw_list. Se itemnão for encontrado, a ValueErrorexceção levantada é capturada e a itemé adicionada à duplicated_itemslista.

Se o índice de itens duplicados for necessário, apenas enumeratea lista e brinque com o índice. ( for index, item in enumerate(raw_list):), que é mais rápido e otimizado para listas grandes (como milhares de elementos)

Tudo é muito
fonte
2

uso do list.count()método na lista para descobrir os elementos duplicados de uma determinada lista

arr=[]
dup =[]
for i in range(int(input("Enter range of list: "))):
    arr.append(int(input("Enter Element in a list: ")))
for i in arr:
    if arr.count(i)>1 and i not in dup:
        dup.append(i)
print(dup)
Ravikiran D
fonte
maneira simples de encontrar os elementos duplicados na lista utilizando a função contagem
Ravikiran D
2

uma linha, por diversão, e onde uma única declaração é necessária.

(lambda iterable: reduce(lambda (uniq, dup), item: (uniq, dup | {item}) if item in uniq else (uniq | {item}, dup), iterable, (set(), set())))(some_iterable)
Wizr
fonte
1
list2 = [1, 2, 3, 4, 1, 2, 3]
lset = set()
[(lset.add(item), list2.append(item))
 for item in list2 if item not in lset]
print list(lset)
Haresh Shyara
fonte
1

Solução de uma linha:

set([i for i in list if sum([1 for a in list if a == i]) > 1])
ytpillai
fonte
1

Há muitas respostas aqui em cima, mas acho que essa é uma abordagem relativamente legível e fácil de entender:

def get_duplicates(sorted_list):
    duplicates = []
    last = sorted_list[0]
    for x in sorted_list[1:]:
        if x == last:
            duplicates.append(x)
        last = x
    return set(duplicates)

Notas:

  • Se você deseja preservar a contagem de duplicação, livre-se do elenco para 'definir' na parte inferior para obter a lista completa
  • Se você preferir usar geradores, substitua duplicates.append (x) pelo yield x e a declaração de retorno na parte inferior (você pode converter para definir posteriormente)
tvt173
fonte
1

Aqui está um gerador rápido que usa um dict para armazenar cada elemento como uma chave com um valor booleano para verificar se o item duplicado já foi produzido.

Para listas com todos os elementos que são tipos hash:

def gen_dupes(array):
    unique = {}
    for value in array:
        if value in unique and unique[value]:
            unique[value] = False
            yield value
        else:
            unique[value] = True

array = [1, 2, 2, 3, 4, 1, 5, 2, 6, 6]
print(list(gen_dupes(array)))
# => [2, 1, 6]

Para listas que podem conter listas:

def gen_dupes(array):
    unique = {}
    for value in array:
        is_list = False
        if type(value) is list:
            value = tuple(value)
            is_list = True

        if value in unique and unique[value]:
            unique[value] = False
            if is_list:
                value = list(value)

            yield value
        else:
            unique[value] = True

array = [1, 2, 2, [1, 2], 3, 4, [1, 2], 5, 2, 6, 6]
print(list(gen_dupes(array)))
# => [2, [1, 2], 6]
John B
fonte
1
def removeduplicates(a):
  seen = set()

  for i in a:
    if i not in seen:
      seen.add(i)
  return seen 

print(removeduplicates([1,1,2,2]))
ASHISH RANJAN
fonte
Você retorna um conjunto e não uma lista, conforme solicitado. Um conjunto contém apenas elementos exclusivos, portanto, a instrução if não é realmente necessária. Você também deve explicar qual é a vantagem da sua solução em comparação com a outra.
Clemens
1

Ao usar o toolz :

from toolz import frequencies, valfilter

a = [1,2,2,3,4,5,4]
>>> list(valfilter(lambda count: count > 1, frequencies(a)).keys())
[2,4] 
Andreas Profous
fonte
0

foi assim que tive que fazer isso porque me desafiei a não usar outros métodos:

def dupList(oldlist):
    if type(oldlist)==type((2,2)):
        oldlist=[x for x in oldlist]
    newList=[]
    newList=newList+oldlist
    oldlist=oldlist
    forbidden=[]
    checkPoint=0
    for i in range(len(oldlist)):
        #print 'start i', i
        if i in forbidden:
            continue
        else:
            for j in range(len(oldlist)):
                #print 'start j', j
                if j in forbidden:
                    continue
                else:
                    #print 'after Else'
                    if i!=j: 
                        #print 'i,j', i,j
                        #print oldlist
                        #print newList
                        if oldlist[j]==oldlist[i]:
                            #print 'oldlist[i],oldlist[j]', oldlist[i],oldlist[j]
                            forbidden.append(j)
                            #print 'forbidden', forbidden
                            del newList[j-checkPoint]
                            #print newList
                            checkPoint=checkPoint+1
    return newList

para que sua amostra funcione como:

>>>a = [1,2,3,3,3,4,5,6,6,7]
>>>dupList(a)
[1, 2, 3, 4, 5, 6, 7]
Matt S
fonte
3
Não era isso que o OP queria. Ele queria uma lista das duplicatas, não uma lista com as duplicatas removidas. Para fazer uma lista com as duplicatas removidas, eu sugeriria duplist = list(set(a)).
Zondo