[python-brasil] Ordenar apenas os n maiores elementos de uma lista
Felipe Munhoz
seguinte:
Por exemplo em uma lista de 100 elementos eu preciso somente dos 20 maiores
os outros 80 elementos eu não preciso ordenar.
Acredito que o tempo de execução ira melhorar bastante se eu não precisar
ordenar 100 % dos elementos, certo ?
Existe alguma forma de fazer isso sem criar um algoritmo especifico, ou
seja, usando apenas o sort do próprio python ?
--
Felipe Munhoz
[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
<*> 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
Diego Manenti Martins
> Olá, estive pesquisando sobre isso na internet mas não obtive sucesso, é o
> seguinte:
>
> Por exemplo em uma lista de 100 elementos eu preciso somente dos 20 maiores
> os outros 80 elementos eu não preciso ordenar.
>
> Acredito que o tempo de execução ira melhorar bastante se eu não precisar
> ordenar 100 % dos elementos, certo ?
>
> Existe alguma forma de fazer isso sem criar um algoritmo especifico, ou
> seja, usando apenas o sort do próprio python ?
Da para fazer usando nlargest:
>>> from heapq import nlargest as nlargest
>>> l = range(100)
>>> l
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36,
37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53,
54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70,
71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87,
88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]
>>> sorted(nlargest(20, l))
[80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]
>>>
--
Diego Manenti Martins
Técnico em eletrônica
+55 48 8421-1025
Rafael "SDM" Sierra
>
> > Existe alguma forma de fazer isso sem criar um algoritmo especifico, ou
> > seja, usando apenas o sort do próprio python ?
>
> Da para fazer usando nlargest:
>
> >>> from heapq import nlargest as nlargest
Só uma observação acerca do nlargest, na documentação está escrito:
"""
nlargest(n, iterable, key=None)
Find the n largest elements in a dataset.
Equivalent to: sorted(iterable, key=key, reverse=True)[:n]
"""
Ok, então vamos testar ambos:
Sorted:
sdm@ubuntu:~$ python -m timeit -s "x = xrange(1000)" "y=sorted(x,
reverse=True)[:20]"
10000 loops, best of 3: 136 usec per loop
NLargest:
sdm@ubuntu:~$ python -m timeit -s "from heapq import nlargest" "x =
xrange(1000)" "y=nlargest(20, x)"
100 loops, best of 3: 2.76 msec per loop
Esse resultado se repetiu varias vezes, então acho que o nlargest não
é muito indicado (a perfomance foi absurdamente diferente) para esses
casos (talves com outros tipos de objetos na lista seja, mas com
numeros não é).
Alguem pode confirmar se é isso mesmo? Ou se fiz algo errado nos testes?
--
Rafael "SDM" Sierra
http://stiod.com.br/
Nilton Volpato
On 6/12/07, Felipe Munhoz <mun...@gmail.com> wrote:
> Olá, estive pesquisando sobre isso na internet mas não obtive sucesso, é o
> seguinte:
>
> Por exemplo em uma lista de 100 elementos eu preciso somente dos 20 maiores
> os outros 80 elementos eu não preciso ordenar.
>
> Acredito que o tempo de execução ira melhorar bastante se eu não precisar
> ordenar 100 % dos elementos, certo ?
>
> Existe alguma forma de fazer isso sem criar um algoritmo especifico, ou
> seja, usando apenas o sort do próprio python ?
Esse é um assunto muito interessante. Existem algoritmos para seleção
do k-ésimo elemento em tempo linear, eu implementei um deles em python
e em C como um módulo para python.
Eu comparei 4 versões: 1. usando sort, 2. implementação em python
puro, 3. implementação em python usando psyco, 4. implementação em C
como módulo python.
Dentre essas versões uma que sempre é pior é a (1), usando o sort
embutido do python. E em geral (3) e (4) são muito mais rápido que as
outras opções, sendo que (3) usando python+psyco pode ser mais rápido
que (4) em C em certos casos.
Veja essa mensagem, muito mais explicativa:
http://article.gmane.org/gmane.comp.python.brasil/17530
Os links não funcionam mais, entretanto fiz uma cópia aqui:
http://www.loco.ic.unicamp.br/~nilton/files/kth/
Inclusive com o código pode ser encontrado neste mesmo link acima.
Abraços,
-- Nilton
Nilton Volpato
[...]
> Só uma observação acerca do nlargest, na documentação está escrito:
> """
> nlargest(n, iterable, key=None)
> Find the n largest elements in a dataset.
>
> Equivalent to: sorted(iterable, key=key, reverse=True)[:n]
> """
Equivalente nesse caso quer dizer que o comportamento é o mesmo, mas
não a implementação.
> Ok, então vamos testar ambos:
>
> Sorted:
> sdm@ubuntu:~$ python -m timeit -s "x = xrange(1000)" "y=sorted(x,
> reverse=True)[:20]"
> 10000 loops, best of 3: 136 usec per loop
>
> NLargest:
> sdm@ubuntu:~$ python -m timeit -s "from heapq import nlargest" "x =
> xrange(1000)" "y=nlargest(20, x)"
> 100 loops, best of 3: 2.76 msec per loop
>
> Esse resultado se repetiu varias vezes, então acho que o nlargest não
> é muito indicado (a perfomance foi absurdamente diferente) para esses
> casos (talves com outros tipos de objetos na lista seja, mas com
> numeros não é).
>
> Alguem pode confirmar se é isso mesmo? Ou se fiz algo errado nos testes?
É isso mesmo, em termos de complexidade assintótica a ordenação leva
tempo O(m log m) para ordenar m elementos. O nlargest leva tempo O(m +
n log m) ou O(m log n) para escolher os n maiores entre m elementos, a
complexidade depende de como é feita a implementação. Mas como esse
módulo heapq é péssimo em termos de eficiência (e em termos de
funcionalidade também), a constante oculta pela notação O( . ) acaba
sendo muito grande. E dentre essas duas opções acaba sendo melhor
ordenando mesmo. Mas a melhor opção é usar um bom (e bem implementado)
algoritmo de seleção do k-ésimo, veja meu email anterior.
Abraço,
-- Nilton
Felipe Munhoz
Abraço
On 6/12/07, Nilton Volpato <nilton....@gmail.com> wrote:
>
> On 6/12/07, Rafael SDM Sierra <rafae...@gmail.com<rafaeljsg14%40gmail.com>>
--
Felipe Munhoz
[As partes desta mensagem que não continham texto foram removidas]
,-----------------------------------------------------------.
Rodrigo Senra
-----------------------------------------------
|módulo heapq é péssimo em termos de eficiência (e em termos de
|funcionalidade também), a constante oculta pela notação O( . ) acaba
|sendo muito grande. E dentre essas duas opções acaba sendo melhor
|ordenando mesmo. Mas a melhor opção é usar um bom (e bem implementado)
|algoritmo de seleção do k-ésimo, veja meu email anterior.
Excelente o email do Nilton, como já era de se esperar.
Eu só queria acrescentar que se o padrão de uso é ter sempre
os [1:K]-maiores valores e não apenas o K-ésimo maior valor,
eu acho que o heap (a estrutura não a implementação) ainda é
a ferramenta mais adequada para esta tarefa.
E como observou o Nilton, se não acharmos um módulo que implementa heap
adequadamente (com o desempenho satisfatório), este seria um ótimo
projeto para quem estiver cursando estruturas de dados ou análise
de algoritmos. Heap implementado sobre vetor não tem porque não
ser eficiente, com extração do mínimo (ou máximo) em Theta(1) e
com inserção em Theta(lg n).
PAra quem quiser um empurrãozinho (e não tiver o Introduction to Algorithms
do Cormen), eu recomendo [1]
[1] http://en.wikipedia.org/wiki/Heap_(data_structure)
Abração
Senra
---
http://rodrigo.senra.nom.br
Felipe Almeida Lessa
> Excelente o email do Nilton, como já era de se esperar.
> Eu só queria acrescentar que se o padrão de uso é ter sempre
> os [1:K]-maiores valores e não apenas o K-ésimo maior valor,
> eu acho que o heap (a estrutura não a implementação) ainda é
> a ferramenta mais adequada para esta tarefa.
Eu sei que este não é o foco desta lista e não quero gerar muita
discussão off-topic, apenas me passou pela cabeça. E a complexidade de
uma implementação feita usando sort numa linguagem não-estrita
(preguiçosa)?
Algo como (em Haskell):
$ ghci
___ ___ _
/ _ \ /\ /\/ __(_)
/ /_\// /_/ / / | | GHC Interactive, version 6.6, for Haskell 98.
/ /_\\/ __ / /___| | http://www.haskell.org/ghc/
\____/\/ /_/\____/|_| Type :? for help.
Loading package base ... linking ... done.
Prelude> :m Data.List
Prelude Data.List> :t sortBy
sortBy :: (a -> a -> Ordering) -> [a] -> [a]
Prelude Data.List> :t flip
flip :: (a -> b -> c) -> (b -> a -> c)
Prelude Data.List> :t compare
compare :: (Ord a) => a -> a -> Ordering
Prelude Data.List> :t take
take :: Int -> [a] -> [a]
Prelude Data.List> let lista =
[92,45,69,46,58,90,37,45,60,71,26,202,34,2,30,98,74,21]
Prelude Data.List> take 10 (sortBy (flip compare) lista)
[202,98,92,90,74,71,69,60,58,46]
Me lembro de ver em algum lugar que você podia achar em tempo linear o
maior elemento fazendo algo assim só que com take 1, mas não lembro
onde. Alguém tem alguma pista?
Até mais,
--
Felipe.
Rodrigo Pinheiro Marques de Araújo
Eu estava desenvolvendo um simulador de redes peer-to-peer, e precisava tirar o máximo do algoritmo de menor caminho do dijkstra, para melhorar a implementação do dijkstra da biblioteca que eu estava usando (networkx [1]), eu troquei o algoritmo de heap que ela usava (heapq) por um heap binario do pacote Opus7 [2]. Melhorou bastante.
Durante os testes de desempenho, um colega fera nos desafios da acm me sugeriu usar um heap fibonacci, por que segundo o Cormen ele seria o mais adequado. Ele me explicou a diferença nas complexidades, mas no momento eu não lembro exatamente.
Em [3] tem uma implementação de um heap fibonacci, entretanto esta implementação não obteve desempenho melhor que o heap binário implementado pelo pacote Opus7 [2] como eu esperava.
Enfim, são algumas implementações a mais de heap para você testar com o seu problema.
Não sei dizer se os heaps binário e fibonacci são os melhores para o seu caso, mas vale dar uma olhada.
Acabei descobrindo hoje, que na Opus7 [2] tem inclusive um heap chamado HeapSorter, talvez seja útil.
Espero ter ajudado.
Rodrigo Fenrrir
[1] - https://networkx.lanl.gov/wiki
[2] - http://www.brpreiss.com/books/opus7/
[3] - http://cs.anu.edu.au/~Alistair.Rendell/Teaching/apac_comp3600/
_______________________________________________________
Yahoo! Mail - Sempre a melhor opção para você!
Experimente já e veja as novidades.
http://br.yahoo.com/mailbeta/tudonovo/
Paul Eipper
http://en.wikipedia.org/wiki/Heap_(data_structure)
Lá também fala que o heap fibonacci tem melhor desempenho para
calcular a trajetória mais curta com o algoritmo dijkstra.
--
Paul Eipper
Em 14/06/07, Rodrigo Pinheiro Marques de
Araújo<rodrigo...@yahoo.com.br> escreveu:
Davi Reis
eu não achei um algoritmo melhor que o davisort para ordenação
parcial. A solução clássica é o partial quicksort (procure "partial
sort" para obter a literatura).
Aqui você implementações do davisort em C e pascal:
http://homepages.dcc.ufmg.br/~davi/davisort.c
http://homepages.dcc.ufmg.br/~davi/davisort.p
Não é complicado. Basicamente uma mistura de quicksort com insertion
sort. No livro "Projeto de Algoritmos com Implementação em Pascal e C"
tem um exercício com uma explicação melhorzinha.
> > ,----------------------------------------------------------.
> > | 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
> >
> >
> >
>
>
>
--
[]s
Davi de Castro Reis
Leonardo Santagada
Em 15/06/2007, às 18:52, Davi Reis escreveu:
> Aproveitando a thread para fazer uma propaganda pessoal, por enquanto
> eu não achei um algoritmo melhor que o davisort para ordenação
> parcial. A solução clássica é o partial quicksort (procure "partial
> sort" para obter a literatura).
>
> Aqui você implementações do davisort em C e pascal:
> http://homepages.dcc.ufmg.br/~davi/davisort.c
> http://homepages.dcc.ufmg.br/~davi/davisort.p
>
> Não é complicado. Basicamente uma mistura de quicksort com insertion
> sort. No livro "Projeto de Algoritmos com Implementação em Pascal e C"
> tem um exercício com uma explicação melhorzinha.
>
Uma pergunta total off topic, tu conseguiria declarar esse tipo
ChaveTipo em outro arquivo e fazer algo tipo parametrizar essa
estrutura? Pq até onde eu me lembro isso é semi impossivel em pascal
puro o que faz a linguagem perder toda a graça. E por pascal puro eu
não sei direito o que eu quero dizer, pq q eu lembre tem uns 2
padrões de pascal que nenhum compilador segue, então interprete como
quiser.
--
Leonardo Santagada
"If it looks like a duck, and quacks like a duck, we have at least to
consider the possibility that we have a small aquatic bird of the
family anatidae on our hands." - Douglas Adams
Goedson Teixeira Paixao
> [ "Nilton Volpato" <nilton....@gmail.com> ]:
> -----------------------------------------------
> |módulo heapq é péssimo em termos de eficiência (e em termos de
> |funcionalidade também), a constante oculta pela notação O( . ) acaba
> |sendo muito grande. E dentre essas duas opções acaba sendo melhor
> |ordenando mesmo. Mas a melhor opção é usar um bom (e bem
> implementado)
> |algoritmo de seleção do k-ésimo, veja meu email anterior.
>
> Excelente o email do Nilton, como já era de se esperar.
> Eu só queria acrescentar que se o padrão de uso é ter sempre
> os [1:K]-maiores valores e não apenas o K-ésimo maior valor,
> eu acho que o heap (a estrutura não a implementação) ainda é
> a ferramenta mais adequada para esta tarefa.
Posso estar redondamente enganado aqui (faz muito tempo que eu e o
Cormen não batemos um papinho :) mas, dependendo da relação entre K e N
(K menor que log(N)), um selection sort parcial (repetir K vezes a busca
e remoção do maior elemento do array) seria mais eficiente do que o uso
de um heap, não?
--
Goedson Teixeira Paixao http://mundolivre.wordpress.com/
Debian Project http://www.debian.org/
Jabber ID: goe...@jabber.org http://www.jabber.org/
[As partes desta mensagem que não continham texto foram removidas]
,-----------------------------------------------------------.
Rodrigo Dias Arruda Senra
Há quanto tempo hein Sr. Goedson Paixão ;oD
Bom, te ver de novo nestas bandas.
Contextualizando...
>> [ "Nilton Volpato" ]:
>> -----------------------------------------------
>> |módulo heapq é péssimo em termos de eficiência (e em termos de
>> |funcionalidade também), a constante oculta pela notação O( . ) acaba
>> |sendo muito grande. E dentre essas duas opções acaba sendo melhor
>> |ordenando mesmo. Mas a melhor opção é usar um bom (e bem
>> implementado)
>> |algoritmo de seleção do k-ésimo, veja meu email anterior.
> [ Rodrigo Senra ]:
>>
>> Excelente o email do Nilton, como já era de se esperar.
>> Eu só queria acrescentar que se o padrão de uso é ter sempre
>> os [1:K]-maiores valores e não apenas o K-ésimo maior valor,
>> eu acho que o heap (a estrutura não a implementação) ainda é
>> a ferramenta mais adequada para esta tarefa.
[ Goedson Teixeira Paixao ]:
---------------------
>Posso estar redondamente enganado aqui (faz muito tempo que eu e o
>Cormen não batemos um papinho :) mas, dependendo da relação entre K e N
>(K menor que log(N)), um selection sort parcial (repetir K vezes a
>busca e remoção do maior elemento do array) seria mais eficiente do
>que o uso de um heap, não?
O lance é que se vc precisa dos n-maiores (ou n-menores) não é
necessário *ordenar __todo__ o conjunto*. Essa é a chave.
Por exemplo, consideremos K=1, o que significa que só é desejado o
maior(ou o menor) elemento. A extração do maior(menor) é Theta(lg n).
Ou seja, é necessário tempo proporcional a log na base 2 do número
de elementos presentes no conjunto.
A função tempo em relação ao crescimento do conjunto seria f(n)= c*lg n
.:. onde c é uma constante. A constante c varia de acordo com o
algoritmo e com a sua implementação. Para valores muito pequenos de n,
é preciso testar cada algoritmo pois aberrações podem acontecer.
Um bubblesort **pode** ganhar de um quicksort para conjuntos muito
pequenos, uma vez que suas respectivas curvas de crescimento não se
cruzaram ainda. A análise de complexidade (assintótica) garante que
uma vez que as curvas de crescimento se cruzem, então é possível definir
qual é melhor do que o outro.
Goedson, talvez a sua observação se referi-se a esta constante c
ao invés de K, e a este fenômeno em que para valores suficientemente
pequenos a análise assintótica não se aplica. Inclusive a maioria das
rotinas avançadas de ordenação tem condicionais (if's) que comutam
o algoritmo a ser usado dependendo do tamanho do problema. O próprio
algoritmo usado pelo Python (thanks Tim Peters) usa este recurso.
De qualquer forma, uma passada do selection sort, para funcionar,
teria que percorrer pelo menos (no pior caso) *todos* os N elementos
do conjunto para selecionar o maior (ou menor). Enquanto o heap,
só precisa percorrer lg N. Por isso, que eu disse que se não for preciso
ordenar, o heap (em regime) é melhor ;o)
Agora, e se só for necessário escolher o maior(ou menor) uma única vez
para um dado conjunto. E depois e joga fora todo o conjunto ?
Talvez seja isso que vc tenha em mente ? Neste caso uma passada
no conjunto inteiro (= uma passada do Selection) ainda é Theta(n).
Uma abordagem ingênua com heaps seria inserir (levando O(lg n)) cada
um dos valores, o que levaria O(n* lg n). Porém, existe o algoritmo
heapify(make heap), que transforma o vetor em um max(min)-heap-binomial
com complexidade Theta(n).
E mesmo neste caso, uma passada do selection não seria (em teoria)
melhor que usar o Heap.
Abração
Senra
Abração
Senra
Nilton Volpato
On 7/4/07, Goedson Teixeira Paixao <goe...@debian.org> wrote:
[...]
> Posso estar redondamente enganado aqui (faz muito tempo que eu e o
> Cormen não batemos um papinho :) mas, dependendo da relação entre K e N
> (K menor que log(N)), um selection sort parcial (repetir K vezes a busca
> e remoção do maior elemento do array) seria mais eficiente do que o uso
> de um heap, não?
Sim, você está certo. Existem 1001 (leia-se nove :^), maneiras de
resolver esse problema, e dentre essas todas, usar o selection sort
parcial é a menos geral, pois só funciona eficientemente para K <
log(N), entretanto pode ser usada caso se saiba que os valores K e N
vão satisfazer essa propriedade.
Vamos nos ater ao problema de ordenar os K maiores elementos de uma
lista L de N elementos. Vou listar (não exaustivamente) algumas formas
de se resolver esse problema.
*1* Usar um algoritmo de seleção do k-ésimo em tempo linear, depois
ordena os L[0:K] maiores elementos. Complexidade de pior caso: O(N + K
log(K)).
*2* Construir um heap (máximo) de tamanho N com todos os elementos. E
depois ir retirando apenas os K maiores. Complexidade de pior caso:
O(N + K log(N))
*3* Construir um heap (mínimo) de tamanho K com quaisquer K elementos
da lista L. Para cada um dos elementos restantes, se esse elemento for
maior que o mínimo do heap (topo), remover o topo do heap e inserir
esse elemento no heap. No final o heap fica com todos os K maiores
elementos. Complexidade de pior caso: O(K + (N-K)*log(K)) = O(K + N
log(K))
*4* Fazer um quicksort modificado que faz o particionamento, do vetor
e só faz a ordenação recursiva do lado que contém os K maiores
elementos. Complexidade depior caso: O(N^2), complexidade do caso
médio: O(N + K log(K)).
*5* Usar o selection sort parcial. Complexidade: O(K N).
*6* Ordenar a lista toda. Pegar apenas a parte relevante, jogar o
resto fora. Complexidade: O(N log(N))
*7* Um algoritmo probabilístico. Escolher K elementos aleatoriamente
na lista L. Verificar se todos os elementos restantes são menores que
o menor dos escolhidos. Complexidade caso médio é algo como: O(N K!)
*8* Exercício.
*9* Exercício.
Dentre todos esse métodos aí, temos todo tipo de complexidade de tempo:
1 - O(N + K log(K))
2 - O(N + K log(N))
3 - O(K + N log(K))
4 - pior caso: O(K + N log(K)), caso médio: O(N^2)
5 - O(K N)
6 - O(N log(N))
7 - O(N K!)
Nenhum desses 7 métodos tem a mesma complexidade. E é até difícil
comparar alguns deles, mas certamente o método 7 é o mais ineficiente
de todos.
O método 5 é eficiente se K for *muito* pequeno, mas muito pequeno
mesmo, menor que log(N). Ou seja, se você for selecionar o 32-ésimo
elemento sua lista teria que ter 4 giga elementos! e você precisaria
de muita memória. Em termos práticos só funcionaria se K < 5. E mesmo
que K sejam os 0.1% maiores elementos esse algoritmo já é O(N^2). Já
métodos 1, 2, 3 e 4 funcionam muito bem para a maioria dos casos.
Abraços,
-- Nilton