[python-brasil] Identificar duplicidade em lista
Antonio Prado
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
<*> Para visitar o site do seu grupo na web, acesse:
http://br.groups.yahoo.com/group/python-brasil/
<*> Para sair deste grupo, envie um e-mail para:
python-brasi...@yahoogrupos.com.br
<*> O uso que você faz do Yahoo! Grupos está sujeito aos:
http://br.yahoo.com/info/utos.html
Pedro Werneck
> 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
Rodrigo
"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]
Luciano Ramalho
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 <sup...@antonioprado.eti.br>:
Antonio Prado
>
> 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.
Francisco Viégas Vianna
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 <casti...@gmail.com>
Danilo Cabello
> 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
Francisco Viégas Vianna
relativa deles teria bastante influência.
Dependendo da aplicação, acho que pode ser mais vantajoso mesmo.
2010/6/30 Danilo Cabello <danilo....@gmail.com>
> 2010/6/30 Francisco Viégas Vianna <francisco...@gmail.com>:
> > 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]
------------------------------------
Luciano Ramalho
> 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]
Pinguim Azul
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 <danilo....@gmail.com>:
> 2010/6/30 Francisco Viégas Vianna <francisco...@gmail.com>:
>> 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
Junior Polegato - Linux
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
voyeg3r
[ i for i in set(lista) if lista.count(i) > 1 ]
On 1 jul, 09:14, Junior Polegato - Linux <li...@juniorpolegato.com.br>
wrote:
Pinguim Azul
> # 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
Narcélio Filho
> 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
Pinguim Azul
>>> [ 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
Paulo Eduardo Neves
> 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]
------------------------------------
Paulo Eduardo Neves
<paulo...@gmail.com> 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
Pinguim Azul
> 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
Luciano Ramalho
> 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
Francisco Viégas Vianna
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 <bluep...@gmail.com>
[As partes desta mensagem que não continham texto foram removidas]
------------------------------------
Iuri
>
>
> 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 ?
>
A implementação do set() é feita com hashs.
Quando o i in x é utilizado para um set, isso é no máximo O(n), mas no
melhor caso é O(1). Gera o hash de i e acessa no set o bucket correspondente
ao hash. A partir disso, compara os objetos do bucket para ver se algum
deles é igual ao objeto i. Se vc supor que não vai utilizar uma quantidade
muito grande de objetos no set, o i in x é aproximadamente O(1).
Repare que o Python "executa o in" de formas diferentes para os diferentes
tipos (duck typing). O in é dependente da implementação do método
__contains__.
Mas o melhor do Python é que se você tiver dúvida sobre a implementação,
você pode por exemplo ir na sua pasta de libs do Python (usr/lib/python no
meu caso) e conferir a implementação no arquivo sets.py.
[]s
iuri
>
> 2010/7/1 Pinguim Azul <bluep...@gmail.com <bluepenguin%40gmail.com>>
>
>
> > 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 <danilo....@gmail.com<danilo.cabello%40gmail.com>
> >:
> > > 2010/6/30 Francisco Viégas Vianna <francisco...@gmail.com<francisco.v.vianna%40gmail.com>
> >:
> > >> 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
Francisco Viégas Vianna
tipos (duck typing). O in é dependente da implementação do método
__contains__.
Era exatamente o que eu queria saber.
Obrigado.
2010/7/2 Iuri <iuris...@gmail.com>
Carlos Ribeiro
> Esse teste é feito em tempo constante para qualquer lista?
> Mais especificamente, como o python executa o in ?
>
Como o pessoal já falou, a implementação em C do Python (CPython) usa hashes
extensivamente, pela própria natureza das construções da linguagem.
Dicionários são hashes e a "infraestrutura" de classes usa dicionários &
hashes. O legal é que a implementação de hash já está muito madura e e foi
extensivamente otimizada, o que a torna melhor, mais eficiente e menos
sujeita a "casos problemáticos" do que o código que a grande maioria dos
programadores C/C++ é capaz de produzir. Em 99.99% dos casos é a melhor
solução, e se comporta (estatisticamente) como "O(1)".
Em geral só não vale a pena usar hashes em Python para objetos simples que
sejam tratados nativamente em C/C++ como inteiros curtos, etc. - isso porque
há um certo overhead em tratar estes itens como "objetos" e fazer o hash
deles. Em alguns casos vale a pena usar arrays, buffers ou rotinas especiais
(como o NumPy). Mas para strings ou qualquer outro tipo de objeto complexo a
implementação do CPython é excelente.
--
Carlos Ribeiro
Consultoria em Projetos
twitter: http://twitter.com/carribeiro
blog: http://rascunhosrotos.blogspot.com
mail: carri...@gmail.com