Identificar duplicidade em lista

classic Classic list List threaded Threaded
23 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Identificar duplicidade em lista

Antonio Prado
Em uma lista qualquer necessito verificar se em determinada coluna
existem valores repetidos. Qual a melhor forma de fazer isto?

Desde já, obrigado.

Antonio.


Reply | Threaded
Open this post in threaded view
|

Re: Identificar duplicidade em lista

Pedro Werneck-2
On Tuesday 29 June 2010 16:38:59 Antonio Prado wrote:
> Em uma lista qualquer necessito verificar se em determinada coluna
> existem valores repetidos. Qual a melhor forma de fazer isto?
>
> Desde já, obrigado.
>
> Antonio.

Coluna? Como assim? É uma lista de listas? Uma matriz?

O jeito mais simples de verificar se há valores repetidos é converter para set
e comparar se o tamanho muda.

>>> a = [1, 2, 3, 4, 5]
>>> len(a) == len(set(a))
True
>>> b = [1, 2, 3, 3, 4, 5]
>>> len(b) == len(set(b))
False
>>>




--
Pedro Werneck
Reply | Threaded
Open this post in threaded view
|

Re: Identificar duplicidade em lista

Rodrigo-63
Bota simples nisso.

"A muito tempo atrás", programando em outra linguagem me deparei com um
problema parecido, só que naquele caso além de identificar se ha
duplicidade em listas eu tambem tinha que apontar QUAL era a duplicidade.

Naquela plataforma (MUMPS) eu tive que implementar uma variação do
'Buble Sort' para varrer a lista toda (pré classificada) e comparar o
item atual com o proximo.

Não ficou bonito mas funcionou.

Imagino se há alguma forma Pythonica de fazer algo semelhante.


Em 29/6/2010 22:13, Pedro Werneck escreveu:

>
> On Tuesday 29 June 2010 16:38:59 Antonio Prado wrote:
> > Em uma lista qualquer necessito verificar se em determinada coluna
> > existem valores repetidos. Qual a melhor forma de fazer isto?
> >
> > Desde já, obrigado.
> >
> > Antonio.
>
> Coluna? Como assim? É uma lista de listas? Uma matriz?
>
> O jeito mais simples de verificar se há valores repetidos é converter
> para set
> e comparar se o tamanho muda.
>
> >>> a = [1, 2, 3, 4, 5]
> >>> len(a) == len(set(a))
> True
> >>> b = [1, 2, 3, 3, 4, 5]
> >>> len(b) == len(set(b))
> False
> >>>
>
> --
> Pedro Werneck
>
>


[As partes desta mensagem que não continham texto foram removidas]

Reply | Threaded
Open this post in threaded view
|

Re: Identificar duplicidade em lista

Luciano Ramalho
In reply to this post by Antonio Prado
Antonio, procure no histórico desta lista a palavra "duplicado". Há
uma série de mensagens deste ano com o assunto "Ajuda com itens
duplicados em listas e dicionários"

[ ]s
Luciano

2010/6/29 Antonio Prado <[hidden email]>:

> Em uma lista qualquer necessito verificar se em determinada coluna
> existem valores repetidos. Qual a melhor forma de fazer isto?
>
> Desde já, obrigado.
>
> Antonio.
>
>
>
>
> ------------------------------------
>
> ,-----------------------------------------------------------.
> | Antes de enviar um e-mail para o grupo leia:              |
> | http://www.pythonbrasil.com.br/moin.cgi/AntesDePerguntar  |
> | E se você é usuário do BOL lembre-se de cadastrar o       |
> | e-mail do grupo na lista branca do seu sistema anti-spam. |
> `-----------------------------------------------------------´Links do Yahoo! Grupos
>
>
>
Reply | Threaded
Open this post in threaded view
|

Re: Identificar duplicidade em lista

Antonio Prado
In reply to this post by Pedro Werneck-2
Em Ter, 2010-06-29 às 22:13 -0300, Pedro Werneck escreveu:

>  
> On Tuesday 29 June 2010 16:38:59 Antonio Prado wrote:
> > Em uma lista qualquer necessito verificar se em determinada coluna
> > existem valores repetidos. Qual a melhor forma de fazer isto?
> >
> > Desde já, obrigado.
> >
> > Antonio.
>
> Coluna? Como assim? É uma lista de listas? Uma matriz?
>
> O jeito mais simples de verificar se há valores repetidos é converter
> para set
> e comparar se o tamanho muda.
>
> >>> a = [1, 2, 3, 4, 5]
> >>> len(a) == len(set(a))
> True
> >>> b = [1, 2, 3, 3, 4, 5]
> >>> len(b) == len(set(b))
> False
> >>>
>
> --
> Pedro Werneck


É uma gtk.ListStore que está sendo utilizada em uma gtk.TreeView.

>>> print lista[0][0]
'123'
>>> print lista[1][0]
'897'


Fiz da seguinte forma:

numero = []
for linha in range(len(lista)):
    numero.append(lista[linha][0])

if len(numero) <> len(set(numero)):
    print "Número duplicado"


Talvez possa ser feito de forma mais "elegante", mas inicialmente
atendeu ao propósito.


Obrigado.







Reply | Threaded
Open this post in threaded view
|

Re: Identificar duplicidade em lista

Francisco Viégas Vianna
In reply to this post by Rodrigo-63
Tirando o fato de que vc usou um bubbleSort, acho q essa é a melhor solução
não pythonica que eu consigo pensar.

Mas temos que concordar que o que o Pedro colocou

>>> a = [1, 2, 3, 4, 5]
>>> len(a) == len(set(a))
True
>>> b = [1, 2, 3, 3, 4, 5]
>>> len(b) == len(set(b))
False
>>>

é realmente simples.


Alguém sabe com que complexidade o python realiza essas operações?
Um mergeSort e uma varredura me dariam a resposta em tempo O(n log n).

Hum... fiquei curioso agora....

2010/6/30 Rodrigo <[hidden email]>

> Bota simples nisso.
>
> "A muito tempo atrás", programando em outra linguagem me deparei com um
> problema parecido, só que naquele caso além de identificar se ha
> duplicidade em listas eu tambem tinha que apontar QUAL era a duplicidade.
>
> Naquela plataforma (MUMPS) eu tive que implementar uma variação do
> 'Buble Sort' para varrer a lista toda (pré classificada) e comparar o
> item atual com o proximo.
>
> Não ficou bonito mas funcionou.
>
> Imagino se há alguma forma Pythonica de fazer algo semelhante.
>
>
> Em 29/6/2010 22:13, Pedro Werneck escreveu:
> >
> > On Tuesday 29 June 2010 16:38:59 Antonio Prado wrote:
> > > Em uma lista qualquer necessito verificar se em determinada coluna
> > > existem valores repetidos. Qual a melhor forma de fazer isto?
> > >
> > > Desde já, obrigado.
> > >
> > > Antonio.
> >
> > Coluna? Como assim? É uma lista de listas? Uma matriz?
> >
> > O jeito mais simples de verificar se há valores repetidos é converter
> > para set
> > e comparar se o tamanho muda.
> >
> > >>> a = [1, 2, 3, 4, 5]
> > >>> len(a) == len(set(a))
> > True
> > >>> b = [1, 2, 3, 3, 4, 5]
> > >>> len(b) == len(set(b))
> > False
> > >>>
> >
> > --
> > Pedro Werneck
> >
> >
>
>
> [As partes desta mensagem que não continham texto foram removidas]
>
>
>
> ------------------------------------
>
> ,-----------------------------------------------------------.
> | Antes de enviar um e-mail para o grupo leia:              |
> | http://www.pythonbrasil.com.br/moin.cgi/AntesDePerguntar  |
> | E se você é usuário do BOL lembre-se de cadastrar o       |
> | e-mail do grupo na lista branca do seu sistema anti-spam. |
> `-----------------------------------------------------------´Links do
> Yahoo! Grupos
>
>
>


[As partes desta mensagem que não continham texto foram removidas]

Reply | Threaded
Open this post in threaded view
|

Re: Identificar duplicidade em lista

Danilo Cabello
2010/6/30 Francisco Viégas Vianna <[hidden email]>:
> Alguém sabe com que complexidade o python realiza essas operações?
> Um mergeSort e uma varredura me dariam a resposta em tempo O(n log n).
>
> Hum... fiquei curioso agora....

Acho que um InsertionSort ficaria elegante e poderia encontrar
elementos duplicados antes do MergeSort em inúmeros casos, mas isso é
palpite não pensei muito sobre o caso.

--
Danilo Cabello
Reply | Threaded
Open this post in threaded view
|

Re: Identificar duplicidade em lista

Francisco Viégas Vianna
Creio que sim, mas só nos casos onde há repetidos, e mesmo assim, a posição
relativa deles teria bastante influência.

Dependendo da aplicação, acho que pode ser mais vantajoso mesmo.

2010/6/30 Danilo Cabello <[hidden email]>

> 2010/6/30 Francisco Viégas Vianna <[hidden email]>:
> > Alguém sabe com que complexidade o python realiza essas operações?
> > Um mergeSort e uma varredura me dariam a resposta em tempo O(n log n).
> >
> > Hum... fiquei curioso agora....
>
> Acho que um InsertionSort ficaria elegante e poderia encontrar
> elementos duplicados antes do MergeSort em inúmeros casos, mas isso é
> palpite não pensei muito sobre o caso.
>
> --
> Danilo Cabello
>
>
> ------------------------------------
>
> ,-----------------------------------------------------------.
> | Antes de enviar um e-mail para o grupo leia:              |
> | http://www.pythonbrasil.com.br/moin.cgi/AntesDePerguntar  |
> | E se você é usuário do BOL lembre-se de cadastrar o       |
> | e-mail do grupo na lista branca do seu sistema anti-spam. |
> `-----------------------------------------------------------´Links do
> Yahoo! Grupos
>
>
>


[As partes desta mensagem que não continham texto foram removidas]

Reply | Threaded
Open this post in threaded view
|

Re: Identificar duplicidade em lista

Luciano Ramalho
In reply to this post by Antonio Prado
2010/6/30 Antonio Prado <[hidden email]>:
> numero = []
> for linha in range(len(lista)):
>    numero.append(lista[linha][0])

Isso é um laço for com forte sotaque de Pascal.

Quase sempre que você percorre uma lista em Python, e usa um
range(len(lista)) para produzir indices e com eles acessar os itens,
você está usando errado a linguagem.

O seu código acima pode ser reescrito assim:

numero = []
for item in lista:
  numero.append(item[0])

Não é muito mais fácil de entender? É também mais eficiente.

Mas o jeito mais eficiente e legível de escrever qualquer laço for que
tem o objetivo de criar uma lista a partir de outra, é usar uma list
comprehension:

numero = [item[0] for item in lista]
Reply | Threaded
Open this post in threaded view
|

Re: Identificar duplicidade em lista

Pinguim Azul
In reply to this post by Danilo Cabello
Dá pra fazer em O(n) usando um hash:

def dup(a):
  x=set()
  for i in a:
    if i in x:
      return i
    x.add(i)
  return None

a=[1,2,3,4,5,2,6]
print dup(a)


2010/6/30 Danilo Cabello <[hidden email]>:

> 2010/6/30 Francisco Viégas Vianna <[hidden email]>:
>> Alguém sabe com que complexidade o python realiza essas operações?
>> Um mergeSort e uma varredura me dariam a resposta em tempo O(n log n).
>>
>> Hum... fiquei curioso agora....
>
> Acho que um InsertionSort ficaria elegante e poderia encontrar
> elementos duplicados antes do MergeSort em inúmeros casos, mas isso é
> palpite não pensei muito sobre o caso.
>
> --
> Danilo Cabello
>
>
> ------------------------------------
>
> ,-----------------------------------------------------------.
> | Antes de enviar um e-mail para o grupo leia:              |
> | http://www.pythonbrasil.com.br/moin.cgi/AntesDePerguntar  |
> | E se você é usuário do BOL lembre-se de cadastrar o       |
> | e-mail do grupo na lista branca do seu sistema anti-spam. |
> `-----------------------------------------------------------´Links do Yahoo! Grupos
>
>
>



--
Ricardo Bittencourt
http://www.ricbit.com
Reply | Threaded
Open this post in threaded view
|

Re: Identificar duplicidade em lista

Linux - Junior Polegato
In reply to this post by Antonio Prado
Olá,

         Em uma lista do Python dá para usar zip ao invés de for para
criar outra lista os a primeira coluna, mas como está usando uma lista
do GTK, aí tem que ser com for mesmo, veja:

         Lista do Python=> if len(lista) != len(set(zip(*lista)[0])):
print 'Duplicidade'
         Lista do GTK=> if len(lista) != len(set([i[0] for i in
lista])): print 'Duplicidade'

         Para contar as "duplicidades":

contador = {}
for i in lista:
....contador[i[0]] = contador[i[0]] + 1 if i[0] in contador else 1

         Para encontrar as "duplicidades":

filter(lambda chave: contador[chave] > 1, contador)


[]'s
          Junior Polegato

Reply | Threaded
Open this post in threaded view
|

Re: Identificar duplicidade em lista

voyeg3r
# listar repetidos

[ i for i in set(lista) if lista.count(i) > 1 ]


On 1 jul, 09:14, Junior Polegato - Linux <[hidden email]>
wrote:

> Olá,
>
>          Em uma lista do Python dá para usar zip ao invés de for para
> criar outra lista os a primeira coluna, mas como está usando uma lista
> do GTK, aí tem que ser com for mesmo, veja:
>
>          Lista do Python=> if len(lista) != len(set(zip(*lista)[0])):
> print 'Duplicidade'
>          Lista do GTK=> if len(lista) != len(set([i[0] for i in
> lista])): print 'Duplicidade'
>
>          Para contar as "duplicidades":
>
> contador = {}
> for i in lista:
> ....contador[i[0]] = contador[i[0]] + 1 if i[0] in contador else 1
>
>          Para encontrar as "duplicidades":
>
> filter(lambda chave: contador[chave] > 1, contador)
>
> []'s
>           Junior Polegato
Reply | Threaded
Open this post in threaded view
|

Re: Re: Identificar duplicidade em lista

Pinguim Azul
2010/7/1 voyeg3r <[hidden email]>:
> # listar repetidos
>
> [ i for i in set(lista) if lista.count(i) > 1 ]

Essa é quadrática como o bubble sort.

--
Ricardo Bittencourt
http://www.ricbit.com
Reply | Threaded
Open this post in threaded view
|

Re: Re: Identificar duplicidade em lista

Narcélio Filho
>> [ i for i in set(lista) if lista.count(i) > 1 ]
> Essa é quadrática como o bubble sort.

  E se usar a esquecida any()?

any(i for i in lista if lista.count(i) > 1)

  Não é ótima mas, ao meu ver, é bem clara.


--
[]s, Narcélio

Reply | Threaded
Open this post in threaded view
|

Re: Re: Identificar duplicidade em lista

Pinguim Azul
On Thu, Jul 1, 2010 at 12:57 PM, Narcélio Filho <[hidden email]> wrote:
>>> [ i for i in set(lista) if lista.count(i) > 1 ]
>> Essa é quadrática como o bubble sort.
>
>  E se usar a esquecida any()?
>
> any(i for i in lista if lista.count(i) > 1)

Essa também é quadrática.

--
Ricardo Bittencourt
http://www.ricbit.com
Reply | Threaded
Open this post in threaded view
|

Re: Identificar duplicidade em lista

Paulo Eduardo Neves-3
In reply to this post by Pinguim Azul
Em 1 de julho de 2010 08:17, Pinguim Azul <[hidden email]> escreveu:

> Dá pra fazer em O(n) usando um hash:
>
> def dup(a):
>  x=set()
>  for i in a:
>    if i in x:
>      return i
>    x.add(i)
>  return None
>
> a=[1,2,3,4,5,2,6]
> print dup(a)
>

Muito bom. Deve existir alguma mágica usando itertools, mas este
provavelmente é o mais rápido que dá para fazer. O ajuste que eu faria é
retornar um set para que funcione quando tiver mais de um elemento repetido.


def duplicates(aIter):
  alreadyVisited = set()
  dups = set()
  for i in aIter:
    if i in alreadyVisited:
      dups.add(i)
    else:
      alreadyVisited.add(i)
  return alreadyVisited




--
Paulo Eduardo Neves
http://www.mosquito.pro.br


[As partes desta mensagem que não continham texto foram removidas]

Reply | Threaded
Open this post in threaded view
|

Re: Identificar duplicidade em lista

Paulo Eduardo Neves-3
Em 1 de julho de 2010 13:18, Paulo Eduardo Neves
<[hidden email]> escreveu:
>
> def duplicates(aIter):
>   alreadyVisited = set()
>   dups = set()
>   for i in aIter:
>     if i in alreadyVisited:
>       dups.add(i)
>     else:
>       alreadyVisited.add(i)


ops, apertei o send sem querer

def duplicates(aIter):
  alreadyVisited = set()
  dups = set()
  for i in aIter:
    if i in alreadyVisited:
      dups.add(i)
    else:
      alreadyVisited.add(i)
  return dups

--
Paulo Eduardo Neves
http://www.mosquito.pro.br
Reply | Threaded
Open this post in threaded view
|

Re: Identificar duplicidade em lista

Luciano Ramalho
In reply to this post by Linux - Junior Polegato
2010/7/1 Junior Polegato - Linux <[hidden email]>:
>         Lista do Python=> if len(lista) != len(set(zip(*lista)[0])):
> print 'Duplicidade'
>         Lista do GTK=> if len(lista) != len(set([i[0] for i in
> lista])): print 'Duplicidade'

Como eu gosto de fazer isso que o Polegato sugeriu.

Em vez de zip(*lista)[0] eu sempre prefiro uma list comprehension,
como no seu segundo exemplo do Polegato. Eu acho mais legível e é
também mais econômico em memória, pois no list comprehension você só
vai copiar o item[0], enquanto que o zip vai copiar todos os itens.

>         Para contar as "duplicidades":
>
> contador = {}
> for i in lista:
> ....contador[i[0]] = contador[i[0]] + 1 if i[0] in contador else 1
>
>         Para encontrar as "duplicidades":
>
> filter(lambda chave: contador[chave] > 1, contador)

Eu não uso mais filter nem map depois que Python ganhou as list
comprehensions, que acho mais fáceis de ler, e evitam o uso de lambda.
A expressão acima fica assim:

[chave for chave in contador if contador[chave] > 1]

Ou ainda, para evitar acessar duas vezes o dicionário a cada iteração:

[chave for (chave, valor) in contador.iteritems() if valor > 1]

[ ]s
Luciano
Reply | Threaded
Open this post in threaded view
|

Re: Identificar duplicidade em lista

Pinguim Azul
In reply to this post by Linux - Junior Polegato
2010/7/1 Junior Polegato - Linux <[hidden email]>:
> contador = {}
> for i in lista:
> ....contador[i[0]] = contador[i[0]] + 1 if i[0] in contador else 1

Esse caso é O(n) também, mas dá pra simplificar um pouco usando setdefault:

contador = {}
for i in lista:
....contador[i[0]] = 1 + contador.setdefault(i[0], 0)

--
Ricardo Bittencourt
http://www.ricbit.com
Reply | Threaded
Open this post in threaded view
|

Re: Identificar duplicidade em lista

Francisco Viégas Vianna
In reply to this post by Pinguim Azul
Qdo programo em Python eu sempre fico entre a cruz e a espada, por dois
motivos:

1 - Sou programador C/C++ originalmente, então sempre me preocupo e sempre
me preocuparei com performance (mas sem maluquices). Me acostumei a não
escrever um programa que realize muita computação desnecessária.

2 - Já que estou programando Python, eu quero programar Python, usar os
recursos da linguagem, ser pythonico.

Meu conhecimento das implementações do Python é mto pequeno. Me esclareça
uma coisa, por favor. Isso aqui que vc sugeriu:

def dup(a):
 x=set()
 for i in a:
   if i in x:
     return i
   x.add(i)
 return None

a=[1,2,3,4,5,2,6]
print dup(a)


a linha if i in x:

Esse teste é feito em tempo constante para qualquer lista?
Mais especificamente, como o python executa o in ?

2010/7/1 Pinguim Azul <[hidden email]>

> Dá pra fazer em O(n) usando um hash:
>
> def dup(a):
>  x=set()
>  for i in a:
>    if i in x:
>      return i
>    x.add(i)
>  return None
>
> a=[1,2,3,4,5,2,6]
> print dup(a)
>
>
> 2010/6/30 Danilo Cabello <[hidden email]>:
> > 2010/6/30 Francisco Viégas Vianna <[hidden email]>:
> >> Alguém sabe com que complexidade o python realiza essas operações?
> >> Um mergeSort e uma varredura me dariam a resposta em tempo O(n log n).
> >>
> >> Hum... fiquei curioso agora....
> >
> > Acho que um InsertionSort ficaria elegante e poderia encontrar
> > elementos duplicados antes do MergeSort em inúmeros casos, mas isso é
> > palpite não pensei muito sobre o caso.
> >
> > --
> > Danilo Cabello
> >
> >
> > ------------------------------------
> >
> > ,-----------------------------------------------------------.
> > | Antes de enviar um e-mail para o grupo leia:              |
> > | http://www.pythonbrasil.com.br/moin.cgi/AntesDePerguntar  |
> > | E se você é usuário do BOL lembre-se de cadastrar o       |
> > | e-mail do grupo na lista branca do seu sistema anti-spam. |
> > `-----------------------------------------------------------´Links do
> Yahoo! Grupos
> >
> >
> >
>
>
>
> --
> Ricardo Bittencourt
> http://www.ricbit.com
>
>
> ------------------------------------
>
> ,-----------------------------------------------------------.
> | Antes de enviar um e-mail para o grupo leia:              |
> | http://www.pythonbrasil.com.br/moin.cgi/AntesDePerguntar  |
> | E se você é usuário do BOL lembre-se de cadastrar o       |
> | e-mail do grupo na lista branca do seu sistema anti-spam. |
> `-----------------------------------------------------------´Links do
> Yahoo! Grupos
>
>
>


[As partes desta mensagem que não continham texto foram removidas]

12