[python-brasil] A* (A estrela)
Cairo Rocha
Galera,
Foi me passado um trabalho de Inteligencia Artificial(resolver o problema das N-Rainhas) e resolvi fazer em Python(professor deu um prazo muito curto pra implementar 3 algoritmos - A*, Genetico e PSR - busca com retrocesso e Consistencia de arco)... e meu A* tá muito muito ineficiente, pra 7 rainhas ele demora 16minutos... Vocês podem me dar dica para otimizar meu codigo?
http://codepad.org/jgi3d9uc
O algoritmo A* é o ultimo(a_estrela).
Abraços
| 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. |
`-----------------------------------------------------------´
Alterar configurações via web (Requer Yahoo! ID)
Alterar configurações via e-mail: Alterar recebimento para lista diária de mensagens | Alterar formato para o tradicional
Visite seu Grupo | Termos de uso do Yahoo! Grupos | Sair do grupo
Christian S. Perone
Cairo, fiz um GA para resolver o n-queens com 64 rainhas há um tempo, ele
demorou 40 segundos, se te interessar
http://pyevolve.sourceforge.net/wordpress/?p=780
2009/10/5 Cairo Rocha <cairoaorocha@gmail.com>
> Galera,
>
> Foi me passado um trabalho de Inteligencia Artificial(resolver o problema
> das N-Rainhas) e resolvi fazer em Python(professor deu um prazo muito curto
> pra implementar 3 algoritmos - A*, Genetico e PSR - busca com retrocesso e
> Consistencia de arco)... e meu A* tá muito muito ineficiente, pra 7 rainhas
> ele demora 16minutos... Vocês podem me dar dica para otimizar meu codigo?
>
> http://codepad.org/jgi3d9uc
>
> O algoritmo A* é o ultimo(a_estrela).
>
> Abraços
>
>
>
> ------------------------------------
>
> ,----------------------------------------------------------.
> | 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
>
>
>
--
Christian S. Perone
http://pyevolve.sourceforge.net/wordpress
"Forgive, O Lord, my little jokes on Thee, and I'll forgive Thy great big
joke on me."
[As partes desta mensagem que não continham texto foram removidas]
David Kwast
2009/10/5 Cairo Rocha <cairoaorocha@gmail.com>
> Foi me passado um trabalho de Inteligencia Artificial(resolver o problema
das N-Rainhas) e resolvi fazer em Python(professor deu um prazo muito curto
pra implementar 3 algoritmos - A*, Genetico e PSR - busca com retrocesso e
Consistencia de arco)... e meu A* tá muito muito ineficiente, pra 7 rainhas
ele demora 16minutos... Vocês podem me dar dica para otimizar meu codigo?
A primeira coisa que eu faria seria achar o gargalo do código.
Incrivelmente, o Python possui 2 módulos (que eu sei de cabeça) para isso.
http://docs.python.org/library/profile.html#module-cProfile
python -m cProfile myscript.py
http://docs.python.org/library/hotshot.html#module-hotshot
Só depois é bom pensar em otimizar algo. Geralmente é uma linha que fica 99%
do tempo da execução do programa.
[As partes desta mensagem que não continham texto foram removidas]
Cairo Rocha
> A primeira coisa que eu faria seria achar o gargalo do código.
> Incrivelmente, o Python possui 2 módulos (que eu sei de cabeça) para isso.
>
> http://docs.python.org/library/profile.html#module-cProfile
>
> python -m cProfile myscript.py
David, Testei com esse modulo ele coloca 99% do tempo em execfile e a_estrela.py, não informa o que acontece nos meus metodos.
> Cairo, fiz um GA para resolver o n-queens com 64 rainhas há um tempo, ele
> demorou 40 segundos, se te interessar
> http://pyevolve.sourceforge.net/wordpress/?p=780
Eu não posso usar bibliotecas prontas =/
| 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. |
`-----------------------------------------------------------´
Alterar configurações via web (Requer Yahoo! ID)
Alterar configurações via e-mail: Alterar recebimento para lista diária de mensagens | Alterar formato para o tradicional
Visite seu Grupo | Termos de uso do Yahoo! Grupos | Sair do grupo
psycoman
Cairo,
Posta como vc executou o resultado e o profile, acho que fica mais
facil de ajduar.
On Oct 6, 6:44 am, "Cairo Rocha" <cairoaoro...@gmail.com> wrote:
> > A primeira coisa que eu faria seria achar o gargalo do código.
> > Incrivelmente, o Python possui 2 módulos (que eu sei de cabeça) para isso.
>
> >http://docs.python.org/library/profile.html#module-cProfile
>
> > python -m cProfile myscript.py
>
> David, Testei com esse modulo ele coloca 99% do tempo em execfile e a_estrela.py, não informa o que acontece nos meus metodos.
>
> > Cairo, fiz um GA para resolver o n-queens com 64 rainhas há um tempo, ele
> > demorou 40 segundos, se te interessar
> >http://pyevolve.sourceforge.net/wordpress/?p=780
>
> Eu não posso usar bibliotecas prontas =/
David Kwast
2009/10/6 Cairo Rocha <cairoaorocha@gmail.com>
> > A primeira coisa que eu faria seria achar o gargalo do código.
> > Incrivelmente, o Python possui 2 módulos (que eu sei de cabeça) para
isso.
> >
> > http://docs.python.org/library/profile.html#module-cProfile
> >
> > python -m cProfile myscript.py
>
> David, Testei com esse modulo ele coloca 99% do tempo em execfile e
a_estrela.py, não informa o que acontece nos meus metodos.
Tem várias métricas para medir.
http://docs.python.org/library/profile.html#pstats.Stats.sort_stats
Eu fiz um teste em um programa meu que usa o PIL e demora vários segundos
para terminar.
david@localhost /mnt/hdb1/Projetos/PyPilUtils/samples/photo_album $ python
-m cProfile -s cumulative photo.py
2155 function calls in *23.708* CPU seconds
Ordered by: cumulative time
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 23.708 23.708 <string>:1(<module>)
1 0.002 0.002 23.708 23.708 {execfile}
1 0.006 0.006 23.706 23.706 photo.py:3(<module>)
1 0.001 0.001 22.973 22.973
composers.py:7(photo_album_cover)
3 0.003 0.001 22.306 7.435 utils.py:12(resize_4by3)
4 0.000 0.000 19.227 4.807 Image.py:1250(resize)
*4 18.714 4.678 18.714 4.678 {built-in method stretch*}
6 0.038 0.006 3.414 0.569 ImageFile.py:115(load)
3 0.000 0.000 3.401 1.134 Image.py:734(crop)
86 3.312 0.039 3.312 0.039 {built-in method decode}
3 0.000 0.000 0.579 0.193 utils.py:5(rotate)
...
Precisa interpretar algumas coisas. O código rodou por 23 segundos. Desses
23, 18 segundos foram gastos no método stretch que foi chamado 4 vezes.
Visto isso, eu não tenho muitas opções de otimização. Posso tentar o mesmo
resultado por outra operação do PIL, e ver se fica mais rápido. Ou tento
usar outra biblioteca. Mexer no resto do código só vai influenciar alguma
coisa dentro dos 5 segundos em que o método stretch não roda.
Outra coisa, a coluna de tempo cumulativo não serve como somatório para o
cálculo do tempo total do código. Por isso que o execfile "gasta" todo o
tempo, o cProfile liga o cronometro quando ele começa a rodar e só desliga
no final.
Olhando todas as chamadas ordenadas pelo tempo, posso ver qual trecho do meu
código é responsável pela demora. módulo photo -> função photo_album_cover
-> função resize_4by3 -> Image.resize -> stretch
Basta trocar um deles por um código mais rápido que eu resolvo meu problema
de performance. Mas nesse caso em particular, duvido que algo "barato' possa
ser feito, me parece mais fácil rodar o código em um Core 2 Duo 2Ghz em vez
do Amd Athlon 1.1Ghz que ele rodou agora.
Por favor, nos poste seus resultados ordenados pelo tempo para podermos te
ajudar melhor. Experimente também o hotshot.
python -m cProfile *-s cumulative* arquivo.py
[As partes desta mensagem que não continham texto foram removidas]
João Bordignon
2009/10/6 Cairo Rocha <cairoaorocha@gmail.com>
>
>
>
> > A primeira coisa que eu faria seria achar o gargalo do código.
> > Incrivelmente, o Python possui 2 módulos (que eu sei de cabeça) para isso.
> >
> > http://docs.python.org/library/profile.html#module-cProfile
> >
> > python -m cProfile myscript.py
>
> David, Testei com esse modulo ele coloca 99% do tempo em execfile e a_estrela.py, não informa o que acontece nos meus metodos.
>
Caio, tudo bem?
Eu testei seu algorítmo do jeito que o David mostrou.
E o que consome a maior parte do processamento é o método "menor"
da classe FilaDePrioridade, nele você faz um loop por todos os
elementos procurando o que tem o menor custo.
Tenta trocar ele por esse:
def menor(self):
if self.is_empty():
return None
return min(self.l, key=lambda x: x.custo)
Troquei a sua busca, pela função min do python. Passando como chave o
atributo custo. Deve ter alguma forma mais eficiente de fazer. Mas já melhorou
bastante aqui.
João Bordignon
| 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. |
`-----------------------------------------------------------´
Alterar configurações via web (Requer Yahoo! ID)
Alterar configurações via e-mail: Alterar recebimento para lista diária de mensagens | Alterar formato para o tradicional
Visite seu Grupo | Termos de uso do Yahoo! Grupos | Sair do grupo
João Bordignon
2009/10/6 João Bordignon <joaoeb@gmail.com>:
>
> Caio, tudo bem?
Perdão, Cairo.
João Bordignon
João Bordignon
2009/10/6 João Bordignon <joaoeb@gmail.com>:
> Cairo, tudo bem?
>
> Eu testei seu algorítmo do jeito que o David mostrou.
> E o que consome a maior parte do processamento é o método "menor"
> da classe FilaDePrioridade, nele você faz um loop por todos os
> elementos procurando o que tem o menor custo.
> Tenta trocar ele por esse:
>
> def menor(self):
> if self.is_empty():
> return None
> return min(self.l, key=lambda x: x.custo)
>
> Troquei a sua busca, pela função min do python. Passando como chave o
> atributo custo. Deve ter alguma forma mais eficiente de fazer. Mas já melhorou
> bastante aqui.
>
> João Bordignon
>
Verificando melhor, esse método nem é necessário. Visto que ele só é utilizado
pelo outro método, o pop. Alterei para eliminar o método,
http://pastebin.ca/1599095
Agora o gargalo mudou para o método "sucessor" da classe No. Eu não sei bem
o que ele faz, mas é certeza que o rolo está nos loops aninhados.
Boa sorte.
João Bordignon
David Kwast
Seria legal mostrar as mudanças e a migração do gargalho. Outras pessoas
podem aprender muito com esta experiência. As 5-10 primeiras linhas do
resultado do cProfile já bastam, não estou querendo nenhum relatório com
análises de complexidade.
[]s
David Kwast
2009/10/6 João Bordignon <joaoeb@gmail.com>
>
>
> 2009/10/6 João Bordignon <joaoeb@gmail.com <joaoeb%40gmail.com>>:
> > Cairo, tudo bem?
> >
> > Eu testei seu algorítmo do jeito que o David mostrou.
> > E o que consome a maior parte do processamento é o método "menor"
> > da classe FilaDePrioridade, nele você faz um loop por todos os
> > elementos procurando o que tem o menor custo.
> > Tenta trocar ele por esse:
> >
> > def menor(self):
> > if self.is_empty():
> > return None
> > return min(self.l, key=lambda x: x.custo)
> >
> > Troquei a sua busca, pela função min do python. Passando como chave o
> > atributo custo. Deve ter alguma forma mais eficiente de fazer. Mas já
> melhorou
> > bastante aqui.
> >
> > João Bordignon
> >
>
> Verificando melhor, esse método nem é necessário. Visto que ele só é
> utilizado
> pelo outro método, o pop. Alterei para eliminar o método,
> http://pastebin.ca/1599095
>
> Agora o gargalo mudou para o método "sucessor" da classe No. Eu não sei bem
> o que ele faz, mas é certeza que o rolo está nos loops aninhados.
>
> Boa sorte.
>
> João Bordignon
>
>
[As partes desta mensagem que não continham texto foram removidas]
Henr"Ikke" Pereira
Outra coisa interessante seria utilizar o psyco[1[] pra compilar o código.
Lembro que o ganho de tempo nos problemas do spoj[2], utilizando o psyco é
na casa de segundos, então se teu código roda em 5 segundos, bem provável
que ele rode em 0.algumacoisa.
[1] - http://psyco.sourceforge.net/
[2] - http://br.spoj.pl/
2009/10/6 David Kwast <david.kwast@gmail.com>
>
>
> Seria legal mostrar as mudanças e a migração do gargalho. Outras pessoas
> podem aprender muito com esta experiência. As 5-10 primeiras linhas do
> resultado do cProfile já bastam, não estou querendo nenhum relatório com
> análises de complexidade.
>
> []s
>
> David Kwast
>
> 2009/10/6 João Bordignon <joaoeb@gmail.com <joaoeb%40gmail.com>>
>
> >
> >
> > 2009/10/6 João Bordignon <joaoeb@gmail.com <joaoeb%40gmail.com> <joaoeb%
João Bordignon
2009/10/6 David Kwast <david.kwast@gmail.com>
>
>
>
> Seria legal mostrar as mudanças e a migração do gargalho. Outras pessoas
> podem aprender muito com esta experiência. As 5-10 primeiras linhas do
> resultado do cProfile já bastam, não estou querendo nenhum relatório com
> análises de complexidade.
>
> []s
>
> David Kwast
>
Boa idéia David,
Vou fazer quando estiver em casa hoje. Aproveitei esse problema do Cairo para
esfriar a cabeça aqui no trabalho.
João Bordignon
David Kwast
2009/10/6 João Bordignon <joaoeb@gmail.com>
> Boa idéia David,
>
> Vou fazer quando estiver em casa hoje. Aproveitei esse problema do Cairo
para
> esfriar a cabeça aqui no trabalho.
É legal mostrar que muitas vezes a linguagem de programação pouco influencia
na velocidade do programa em resolver um problema particular. Acredito que a
grande maioria das vezes a estrutura de dados escolhida influencia muito
mais. Nisso Python ajuda muito, pois é muito fácil usar HashTables e
LinkedLists. Em linguagens menos ricas, o programador pode "ter medo" de
sair usaando estruturas de dados "alternativas" ou que precisam de
imports/includes.
[As partes desta mensagem que não continham texto foram removidas]
psycoman
Que tal implementar deste jeito a lista de prioridades ?
>>> a = [[2,'a'],[3,'d'],[1,'c']]
>>> a
[[2, 'a'], [3, 'd'], [1, 'c']]
>>> a.sort()
>>> a
[[1, 'c'], [2, 'a'], [3, 'd']]
>>>
deste jeito vc pode sempre mandar ordernar depos do insert e pegar o
menor.
não e elegante mais se ta procurando velocidade acho que ajuda
On Oct 6, 4:19 pm, David Kwast <david.kw...@gmail.com> wrote:
> 2009/10/6 João Bordignon <joa...@gmail.com>
>
> > Boa idéia David,
>
> > Vou fazer quando estiver em casa hoje. Aproveitei esse problema do Cairo
> para
> > esfriar a cabeça aqui no trabalho.
>
> É legal mostrar que muitas vezes a linguagem de programação pouco influencia
> na velocidade do programa em resolver um problema particular. Acredito que a
> grande maioria das vezes a estrutura de dados escolhida influencia muito
> mais. Nisso Python ajuda muito, pois é muito fácil usar HashTables e
> LinkedLists. Em linguagens menos ricas, o programador pode "ter medo" de
> sair usaando estruturas de dados "alternativas" ou que precisam de
> imports/includes.
>
> [As partes desta mensagem que não continham texto foram removidas]
David Kwast
2009/10/6 psycoman <waldecir@gmail.com>
> Que tal implementar deste jeito a lista de prioridades ?
>
> >>> a = [[2,'a'],[3,'d'],[1,'c']]
> >>> a
> [[2, 'a'], [3, 'd'], [1, 'c']]
> >>> a.sort()
> >>> a
> [[1, 'c'], [2, 'a'], [3, 'd']]
> >>>
>
> deste jeito vc pode sempre mandar ordernar depos do insert e pegar o
> menor.
>
> não e elegante mais se ta procurando velocidade acho que ajuda
Legal, não sabia disso.
[As partes desta mensagem que não continham texto foram removidas]
João Bordignon
Eu ia fazer aqui em casa novamente. Mas descobri
que minha sugestão de antes tem um bug.
Desculpe Cairo, falha minha aqui. Ignore minhas
sugestões de antes. :(
Pelo menos eu aprendi como utilizar o cProfile :)
João Bordignon
Cairo Rocha
Ae galera,
Muito obrigado pela ajuda de todos, meu codigo já melhorou bastante... Eu eliminei alguns gargalos e agora o problema pra 6 rainhas passou de 60s pra 4s!
Usei o cProfile pra ver onde ele tava travando(mas não executei como informaram aqui, chamei ele de dentro do programa aí deu certo), o psyco eu já estava utilizando!
O que eu fiz: eliminei as classes Nó e FilaDePrioridade e usei apenas tuplas utilizando o modulo heappq para inserir e remover de uma lista( o primeiro item da tupla é a minha função F(n) = G(n) + H(n), onde G é o custo pra chegar no nó e H(n) é a heuristica)...
E falando com meu professor, ele falou que não sou obrigado a gerar todos os filhos, então troquei pra ele gerar apenas os que vão chegar num resultado!
Segue o codigo: http://pastebin.ca/1600113
| 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. |
`-----------------------------------------------------------´
Alterar configurações via web (Requer Yahoo! ID)
Alterar configurações via e-mail: Alterar recebimento para lista diária de mensagens | Alterar formato para o tradicional
Visite seu Grupo | Termos de uso do Yahoo! Grupos | Sair do grupo
David Kwast
2009/10/6 Cairo Rocha <cairoaorocha@gmail.com>
> Ae galera,
>
> Muito obrigado pela ajuda de todos, meu codigo já melhorou bastante... Eu
eliminei alguns gargalos e agora o problema pra 6 rainhas passou de 60s pra
4s!
>
> Usei o cProfile pra ver onde ele tava travando(mas não executei como
informaram aqui, chamei ele de dentro do programa aí deu certo), o psyco eu
já estava utilizando!
60s -> 4s é um belo speed-up. Não importa qual e como o profiler foi usado,
o que importa é que deu muito certo. Talvez o psyco atrapalhou a medição
correta do cProfile por fora. Falando nisso, você poderia nos informar o
tempo de execução sem o psyco? Com e sem essa otimização da estrutura de
dados se possível.
[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. |
`-----------------------------------------------------------´
Alterar configurações via web (Requer Yahoo! ID)
Alterar configurações via e-mail: Alterar recebimento para lista diária de mensagens | Alterar formato para o tradicional
Visite seu Grupo | Termos de uso do Yahoo! Grupos | Sair do grupo
