Re: [python-brasil] Desempenho do psyco
Rodrigo Dias Arruda Senra
-----------------------------------------------
| Olá gente!
|
| Só para integrar a galera da minha situação, estou cursando mestrado
| aqui na UFRN, na área de otimização e algoritmos experimentais...
Parabéns João.
| Tenho que implementar alguns algoritmos e estou cogitando utilizar
| python para tal. Até o momento, vinha utilizando C/C++, pois nesta área
| desempenho é muito importante.
É preciso tomar alguns cuidados na mistura do meio acadêmico e do meio
corporativo. No meio corporativo há cenários em que o desempenho do
programador é + importante, e outros cenários em que o desempenho de
execução é + importante. Nos primeiros se usa Python, nos últimos substitui-se
código Python por C até que o desempenho desejado seja atingido.
No mundo acadêmico, em particular no estudo de algoritmos, pode-se usar técnicas
de análise assintótica para comparar o desempenho de algoritmos: as famosoas
funções Omega(),Theta(),Big-O(),omega() e little-o(). A análise assintótica
é o bechmark acadêmico de um algorítmo.
Vc até pode usar comparação de execução, mas tem que tomar vários cuidados.
Só para citar um exemplo, linguagens que possuem "garbage collection" deveriam
desligar o coletor de lixo durante a aferição de desempenho, pois ele pode
ludibriar os resultados.
| Basicamente a performance é importante pois tenho que comparar meus
| resultados com os resultados de outras pessoas. Esta comparação é feita
| levando-se em consideração o tempo de execução do algoritmo e a
| qualidade da solução encontrada.
O que você *não* deve fazer é comparar dois algoritmos diferentes de mesmo propósito
usando ambientes diferentes (implementação em C e Python).
Se vc quiser comparar Python vs C use o mesmo algoritmo, de vc quiser comparar
Algoritmo A vs Algoritmo B use a mesma linguagem, senão o valor científico
se perde.
Hoje, a melhor implementação em Python *sempre* vai perder da melhor implementação
em C. Se o resultado for diferente significa que vc não tinha a melhor implementação =)
A razão é muito simples, Python lhe dá flexibilidade e produtividade ao custo de
overhead. C lhe tira tudo isso pagando em desempenho de execução. Como Python está
implementado em C é uma corrida injusta.
Apesar disso, existe o projeto PyPy http://codespeak.net/pypy/
e dizem: 'Rumors have it that the secret goal is being faster-than-C which is nonsense, isn't it?'
A questão é que eventualmente a tradução de código Python (via PyPy) para código
de máquina *pode* gerar código mais eficiente que Código C escrito por um programador
qualquer e otimizado pelo compilador C.
| A pergunta é: existe algum estudo que indique a diferença de desempenho
| em programas algorítmicos quando se utiliza C/C++ e Python + Psyco?
Existe um já um pouco desatualizado (congelou em 2001) que não involve Psyco,
vc pode conferir em:
http://www.bagley.org/~doug/shootout/ (original)
http://dada.perl.it/shootout/ (testado em windows)
| Se a diferença for em torno de 10% a 15% acho que posso utilizar Python
| sem problemas. Mais que isso já fica impratiável.
| Se for menor que isto, vou passar a utilizar python em todos meus
| projetos :)
Este não é um bom critério para decidir quando usar Python ou C
;o)
Espero que tenha ajudado.
Abração
Senra
,_
| ) Rodrigo Senra <rsenra |at| acm.org>
|(______ -----------------------------------------------
_( (|__|] GPr Sistemas http://www.gpr.com.br
_ | (|___|] IC - Unicamp http://www.ic.unicamp.br/~921234
___ (|__|]
L___(|_|] -----------------------------------------------
* Antes de enviar a sua pergunta procure por uma solução em:
http://pythonbrasil.com.br/
http://python.org
http://google.com
* Não envie e-mails HTML para a lista.
* Evite mensagens off-topic
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
João Paulo Fernandes Farias
Demorei um tempo para responder pois estava implementando as heurísticas
em python e em C++.
Bom, para minha tristeza o resultado foi totalmente desfavorável para o
psyco... Implementei o mesmo algoritmo em python (+ psyco) e em C++. A
implementação em python conseguiu uma rodar uma média de 25 iterações do
algoritmo em 60 segundos, enquando a implementação em C++ rodou uma
média de 160! Ou seja, C++ ainda é mais ou menos 6,5 vezes mais rápido
que python + psyco.
O que me deixa menos triste é que eu descobri uma maneira utilizar o
python para este tipo de projeto: eu implemento primeiro em python, que
é muito mais produtivo e termino bem rápido, verifico se está tudo
correto e depois passo pra C++ de forma mais tranquila. O chato é ter
que re-escrever em C++ :(
Bom, fica o alerta para quem trabalha na área de otimização e algoritmos
experimentais, incluindo heurísticas em geral. Se você estavam pensando
em utilizar python nos seus projetos, pensem novamente. Como os
resultados que são levados em conta nesta área comparam o tempo de
execução das implementações (não importa em que linguagem), python não é
aconselhável (ainda).
Vocês podem até se perguntar se isto influencia, mas sei que influencia,
pois já implementei algoritmos que ficam rodando dias, às vezes semanas
ou meses para atingir um resultado aceitável. Imagina uma implementação
do mesmo algoritmo 6 vezes mais lenta.... ao invés de rodar em um dia,
roda em uma semana. Ao invés de rodar em um mês, roda em 6 meses!!!!
JP.
Em Qui, 2004-09-23 às 11:21 -0300, Rudá Moura escreveu:
> Por que tu não pegas uns programas em C++ e Py, ou faz alguns exemplos
> pequenos e testa por si mesmo? Eu acho melhor tirar as suas próprias
> conclusões.
>
> Bom, se tu procurar direito, vais encontrar bastante coisa no google,
> mas eu recomendo o http://pythonbrasil.com.br/moin.cgi/BenchmarkAdHoc
Osvaldo Santana
Pois é,
Eu sei que você implementou o mesmo algoritmo nas duas linguagens. Mas
o que você provou com isso? Que um algoritmo é mais rápido que outro?
Não. Você provou que C++ é mais rápido que Python e isso não causa
nenhuma surpresa.
Acho que todos aqui na lista sabem que algo implementado em Python
certamente vai rodar mais devagar do que algo implementado em C++.
Mas o dado mais importante deste teu teste não foi exatamente esse: o
resultado mais interessante do seu trabalho foi que você concluiu que
é muito mais rápido implementar algo em Python do que em C++.
Se for pra você comparar algoritmos você *sempre* vai ter que
implementá-los na mesma linguagem e rodá-los na mesma plataforma. Se
não fizer isso você vai estar comparando bananas com maçãs.
Valeu,
Osvaldo
On Fri, 01 Oct 2004 16:09:42 +0000, João Paulo Fernandes Farias
<jpaulo...@yahoo.com.br> wrote:
> Pois é... Implementei o mesmo algoritmo.
>
> Vou anexar as duas implementações, assim, se você tiver paciência, pode
> testar, analisar e tirar suas conclusões.
>
> --
> JP.
>
> Em Sex, 2004-10-01 às 16:06 -0300, Osvaldo Santana escreveu:
> > Continuo achando que performance de Algoritmo deve independer de implementação.
> >
> > Se você implementar o *mesmo* algoritmo em C++ e em Python é muito
> > provável que C++ se dê melhor. Mas se você implementar um algoritmo
> > ruim em C++ e um algoritmo bom em Python que façam as mesmas coisas é
> > bem provável que C++ se dê mal.
> >
> > Valeu,
> > Osvaldo
> >
> > On Fri, 01 Oct 2004 14:58:29 +0000, João Paulo Fernandes Farias
--
Osvaldo Santana Neto (aCiDBaSe)
icq, url = (11287184, "http://www.pythonbrasil.com.br")
Leonardo Santagada
Eu olhei o teu algoritmo e ele parece ter alguns pontos q poderiam
ser bem mais otimizados em python (eu nem olhei o c++) depois eu posso
dar uma olhada mais afundo para ter certeza do que, mas ele parece
muito com código de quem esta começando no python e traduzindo coisas
direto do C++.
Uma idéia fora mudar o código (o q é sempre a melhor otimização a
fazer), seria usar o profiler do python e descobrir quais partes do
código levam mais tempo. isso já ajudaria, outra coisa é usar o Pyrex
e escrever os teus programas num python com declaração de tipos. tem
gente q faz coisas com "nunber crunching" ficarem até 15 vezes mais
rapidas com o Pyrex. Tu não precisa converter todo o código, só a
parte mais lenta...
ps.: Se tu quiser velocidade mesmo, pq não fazes em ASM? eu aposto q
faço algo em assembler 15 vezes mais rapido q c++
Espero q isso ajude,
On Fri, 01 Oct 2004 16:09:42 +0000, João Paulo Fernandes Farias
<jpaulo...@yahoo.com.br> wrote:
> Pois é... Implementei o mesmo algoritmo.
>
> Vou anexar as duas implementações, assim, se você tiver paciência, pode
> testar, analisar e tirar suas conclusões.
>
> --
> JP.
>
> Em Sex, 2004-10-01 às 16:06 -0300, Osvaldo Santana escreveu:
>
>
> > Continuo achando que performance de Algoritmo deve independer de implementação.
> >
> > Se você implementar o *mesmo* algoritmo em C++ e em Python é muito
> > provável que C++ se dê melhor. Mas se você implementar um algoritmo
> > ruim em C++ e um algoritmo bom em Python que façam as mesmas coisas é
> > bem provável que C++ se dê mal.
> >
> > Valeu,
> > Osvaldo
> >
> > On Fri, 01 Oct 2004 14:58:29 +0000, João Paulo Fernandes Farias
> > <jpaulo...@yahoo.com.br> wrote:
--
Leonardo Santagada
"But hey, the fact that I have better taste than anybody else in the
universe is just something I have to live with. It's not easy being
me."
-- Linus Torvalds.
Adam Victor Nazareth Brandizzi
> Pois é,
>
> Eu sei que você implementou o mesmo algoritmo nas duas linguagens. Mas
> o que você provou com isso? Que um algoritmo é mais rápido que outro?
> Não. Você provou que C++ é mais rápido que Python e isso não causa
> nenhuma surpresa.
Se um programa de processamento numérico feito em Python conseguisse
ficar mais rápido que um programa feito em C++, eu iria jogar a toalha,
pegar minhas malas e mudar de planeta :)
> Acho que todos aqui na lista sabem que algo implementado em Python
> certamente vai rodar mais devagar do que algo implementado em C++.
Decerto, mas...
> Mas o dado mais importante deste teu teste não foi exatamente esse: o
> resultado mais interessante do seu trabalho foi que você concluiu que
> é muito mais rápido implementar algo em Python do que em C++.
...para que separar? Python consegue se integrar muito bem com
linguagens compiladas. Faça a parte do programa que leva 3 horas em
Fortran/C++/Assembly e as janelinhas, gráficos e comunicação em rede com
Python :)
> Se for pra você comparar algoritmos você *sempre* vai ter que
> implementá-los na mesma linguagem e rodá-los na mesma plataforma. Se
> não fizer isso você vai estar comparando bananas com maçãs.
>
> Valeu,
> Osvaldo
--
Adam Victor Nazareth Brandizzi
Estudante de Ciência da Computação - UnB - Usuário Linux nº 366316
ICQ: 168537710 | Jabber: bar...@myjabber.net | Telefone: (61)9639 5258
"Real programmers don't use Pascal: just the integer ones can do it."
Carlos Ribeiro
Continuo achando que performance de Algoritmo deve independer de implementação.
> Bom, para minha tristeza o resultado foi totalmente desfavorável para o
> psyco... Implementei o mesmo algoritmo em python (+ psyco) e em C++. A
> implementação em python conseguiu uma rodar uma média de 25 iterações do
> algoritmo em 60 segundos, enquando a implementação em C++ rodou uma
> média de 160! Ou seja, C++ ainda é mais ou menos 6,5 vezes mais rápido
> que python + psyco.
Fica a pergunta: o que custa mais caro, hora de máquina ou hora de
programador? Há algum tempo atrás a resposta era clara -- hora de
computador. Hoje, nem tanto... a hora de programador, em certos casos,
custa muito mais caro do que o tempo de execução.
A propósito, existem vários casos em que a diferença Python x C++ vai
ficar *muito* menor... especialmente se ele utilizar as extensões mais
otimizadas, como é o caso do NumPy, por exemplo. É provável que essas
extensões já estejam tão testadas e otimizadas a ponto de serem mais
rápidas que o código de um programador C++ 'normal' -- não digo nem
ruim, apenas que não conheça todos os macetes para otimização de
algoritmos numéricos.
--
Carlos Ribeiro
Consultoria em Projetos
blog: http://rascunhosrotos.blogspot.com
blog: http://pythonnotes.blogspot.com
mail: carri...@gmail.com
mail: carri...@yahoo.com
João Paulo Fernandes Farias
Vou anexar as duas implementações, assim, se você tiver paciência, pode
testar, analisar e tirar suas conclusões.
--
JP.
Em Sex, 2004-10-01 às 16:06 -0300, Osvaldo Santana escreveu:
> Continuo achando que performance de Algoritmo deve independer de implementação.
>
> Se você implementar o *mesmo* algoritmo em C++ e em Python é muito
> provável que C++ se dê melhor. Mas se você implementar um algoritmo
> ruim em C++ e um algoritmo bom em Python que façam as mesmas coisas é
> bem provável que C++ se dê mal.
>
> Valeu,
> Osvaldo
>
> On Fri, 01 Oct 2004 14:58:29 +0000, João Paulo Fernandes Farias
> <jpaulo...@yahoo.com.br> wrote:
Carlos Ribeiro
Fiquei curioso com o problema em si, mas agora estou meio "atolado"
com um sistema em Python que eu estou desenvolvendo. Dei uma olhadinha
no código em Python. Concordo com uma coisa que já foi dita antes por
aqui -- parece que a solução em C foi simplesmente portada para
Python, sem considerar as diferenças de expressividade entre as
linguagens e suas características únicas.
Correndo o risco de errar, vou dar um exemplo:
<instancia.py>
def avaliar(self, rota):
total = 0
for i in xrange(len(rota)):
total += self.distancia[rota[i-1]][rota[i]]
return total
O loop acima é típico de um programa em C, onde os índices são
calculados rapidamente, o que não é o caso em Python. Também suspeito
de um problema com o loop, porque ele começa com um índice negativo
(quando i=0), que eu não sei se seria o caso. Escrevi uma alternativa
um pouco mais "pitônica", seria bom testar:
def avaliar(self, rota):
total = 0
passo_ant = rota[0]
for passo in rota[1:]:
total += self.distancia[passo_ant][passo]
passo_ant = passo
return total
Ao invés de três indexações no loop, agora tem apenas duas.
Tem uma mudança mais radical que eu consideraria, mas que implica
mexer mais fundo no algoritmo. O vetor rota está sendo utilizado como
índice, o que é bom em C, mas não ajuda em Python. Por outro lado, o
fato de self.distancia ser uma variável mutável ajuda. Se o vetor rota
referenciar cada subvetor de distancia diretamente, o código será
acelerado.
Explicando melhor:
self.distancia[0] -> distâncias medidas a partir do nó zero
self.distancia[1] -> distâncias medidas a partir do nó um
e assim por diante, não é? Então, ao invés de fazer com que rota[i]
referencie o número do nó de número [i] pelo caminho, que tal fazer
com que ele referencie diretamente o subvetor de self.distância? Algo
assim como:
estamos no passo <i> do algoritmo, e vamos colocar o nó <n> neste
passo. O código atual funciona assim:
rota[i] = n
mas poderia funcionar assim:
rota[i] = self.distancia[n]
Isso vai acelerar *todas* as referências às distâncias entre nós, que
agora podem ser calculadas como:
rota = passo[0]
for passo in rota[1:]:
passo+=rota
É claro que nesse exemplo simples o número do nó foi perdido. Mas, e
se colocarmos no elemento zero de cada subvetor de distância uma cópia
do número n?
distancia[n][0] --> n
distancia[n][1] --> distância do nó <n> para o nó <1>
distancia[n][max] --> ... distância do nó <n> para o nó <max>
Pense nesse tipo de coisa. Deve ajudar.
--
Carlos Ribeiro
Consultoria em Projetos
blog: http://rascunhosrotos.blogspot.com
blog: http://pythonnotes.blogspot.com
mail: carri...@gmail.com
mail: carri...@yahoo.com
Carlos Ribeiro
On Fri, 01 Oct 2004 20:01:11 -0300, João Paulo Fernandes Farias
<jpaulo...@yahoo.com.br> wrote:
> Valeu pela dica. Não entendi muito bem o segundo método que você
> sugeriu, se der pra tentar explicar melhor...
Desculpe, eu 'embolei' um pouco minha explicação. A idéia estava clara
para mim mas eu não consegui traduzi-la corretamente para o email.
(Aliás, eu errei feio no pseudo código abaixo - achei que os elementos
desejados ficariam na primeira coluna, mas você vai ver abaixo que
eles ficam na diagonal da matriz construída)
> Mais especificamente, essa parte eu não entendi:
>
> rota = passo[0]
> for passo in rota[1:]:
> passo+=rota
>
> E mais, como eu saberia qual elemento do vetor eu devo somar para
> calcular a distância total?
Esqueça esse trecho, sei lá no que eu estava pensando :-) A idéia
correta é a seguinte: o vetor de rotas, hoje, armazena apenas índices
para o vetor de distâncias. Mas em Python, é fácil manipular o vetor
de distâncias de uma forma que seria mais complicada (or propensa a
erros) em C/C++. Isso pode substituir ou acelerar as referências
indiretas ao vetor de distância (indexadas pela rota) ao longo do
algoritmo.
Detalhando um pouco mais, a idéia é construir uma versão ordenada do
vetor distância. Vou dar um exemplo da estrutura de dados sem nenhum
código para não confundir mais (confesso que estou me perdendo um
pouco aqui, é meio abstrato pros meus neurônios a essa altura do dia):
distância[0] = [0,1,4]
distância[1] = [1,0,2]
distância[2] = [4,2,0]
Imagine agora que a rota seja assim: 2 --> 0 --> 1. Neste caso, a rota fica:
rota = [2,0,1]
E um vetor auxiliar, construído durante o próprio processamento, seria assim:
rotadist[0] = distancia[2] = [4,2,0]
rotadist[1] = distância[0] = [0,1,4]
rotadist[2] = distância[1] = [1,0,2]
A matriz acima contém a distância total na diagonal principal. Um loop
simples calcula a distância total:
total = 0
for i in xrange(len(rota)-1):
total += rota[i][i]
Mas em Python, pode ser que esta forma seja mais eficiente (precisa testar):
total = 0
for i, passo in enumerate(rotadist[:-1]):
total += passo[i]
Deve ser mais ou menos a mesma coisa -- uma delas chama xrange e
indexa duas vezes (o que é mais lento), enquanto a outra enumera os
itens de uma lista (a indexação é feita implicitamente no código em
C), e indexa em Python somente uma vez.
Lembre-se também que no Python, agora, existem também bibliotecas
nativas em C para heaps, que podem ser muito bem aplicados na
construção deste tipo de algoritmo, para alguns tipos de heurística.
Carlos Ribeiro
On Fri, 01 Oct 2004 22:00:15 -0300, João Paulo Fernandes Farias
<jpaulo...@yahoo.com.br> wrote:
>
> Agora entendi legal!
>
> Se tiver um tempo eu faço essas alterações, embora ache que não vá
> melhorar muito, pois a função avaliar é pouco utilizada...
Eu dei o exemplo com a função avaliar, porque ela era pequena, e
porque o tipo de código que estava lá é o tipo que "denuncia" a origem
C/C++. Mas pelo que vi em outros módulos, mesmo sem entender o
funcionamento geral, é que boa parte do código foi portado de uma
solução C/C++ diretamente.
A intenção não é colocar defeito -- longo disso -- mas para poder
acertar uma implementação interessante em Python, o ideal seria dar um
ou dois passos atrás, reler o algoritmo em sua versão de 'alto nível',
e pensar em uma forma correta de expressá-lo em Python. Se você tiver
o mesmo algoritmo implementado em outra linguagem de apelo acadêmico,
como Lisp, Scheme ou Smalltalk, já é meio caminho andado. Boa parte do
código que está lá é na verdade resultado de uma forma de expressar
idéias em C/C++ -- usando extensivamente vetores indexados no lugar de
estruturas abstratas de nível mais alto.
Como falei, estou um pouco atolado, mas acho que estou precisando de
"pequenos desafios" também para desenferrujar :-). Se você puder me
passar mais informações sobre o problema (em email privado, ou na
lista, como queira), podemos continuar a conversa.
Leonardo Santagada
Eu tb estou preparando uns projetos e a minha viagem pra itália, mas
eu te dei um monte de idéias no outro email, mas vamos fazer isso por
partes, pois parece q temos o interesse de um bom pessoal.
1) Rode o código no profiler e mande pra cá os resultados, vamos aos
10% do programa que gasta 90% do tempo
2) Procure maneiras mais pythonicas de montar os teus algoritmos, ou
use pyrex q compila para c.
3) Alguém falou q vai fazer as malas e sair do planeta quando código
python for mais rapido que codigo c? Bom eu não quero mais nenhum
email teu nessa lista, a não ser q tu consiga um satelite com tcp/ip,
porque o Armin Rigo mostrou já código de sort de uma lista mais rapido
em python do que o mais otimizado em c. Algumas operações com a
Numeric são mais rapidas do que feitas em c puro (sem bibliotecas
muito otimizadas como Blas e linpack (esse tipo de coisa, pq nem sei
se são essas as bibliotecas certas))
4) Infelizmente esperar pelo pipi, que vai ser uma revolução em termos
de compiladores tudo idéia do louco do Armim Rigo.
ps. : Pq eu falo tanto no Armin? Bom isso é porque ele me fez saber o
que é python, ele é o criador do editor de quake o Quark (QUake ARmy
Knife) que era feito em delphi para win95 e vinha com o python 1.5.
Eu sempre soube q ele usava isso, ai quando vi um artigo numa revista
sobre esse raio de python.... bom foi amor a primeira programada.
--
Leonardo Santagada
"But hey, the fact that I have better taste than anybody else in the
universe is just something I have to live with. It's not easy being
me."
-- Linus Torvalds.
Rodrigo Dias Arruda Senra
[ João Paulo Fernandes Farias <jpaulo...@yahoo.com.br> ]
-----------------------------------------------
| Olá!
|
| Demorei um tempo para responder pois estava implementando as heurísticas
| em python e em C++.
|
| Bom, para minha tristeza o resultado foi totalmente desfavorável para o
| psyco... Implementei o mesmo algoritmo em python (+ psyco) e em C++. A
| implementação em python conseguiu uma rodar uma média de 25 iterações do
| algoritmo em 60 segundos, enquando a implementação em C++ rodou uma
| média de 160! Ou seja, C++ ainda é mais ou menos 6,5 vezes mais rápido
| que python + psyco.
O que é um resultado totalmente natural. A pergunta é quanto tempo você levou
para implementar em C++ e quanto tempo vc levou para implementar em Python ?
Seria legal compararmos.
Essa é uma medida importantíssima, na maioria dos projetos o desempenho
do desenvolvedor é um fator mais crítico que o desempenho do software.
| O que me deixa menos triste é que eu descobri uma maneira utilizar o
| python para este tipo de projeto: eu implemento primeiro em python, que
| é muito mais produtivo e termino bem rápido, verifico se está tudo
| correto e depois passo pra C++ de forma mais tranquila. O chato é ter
| que re-escrever em C++ :(
Não precisa re-escrever tudo. Só o miolo que executa com maior frequencia.
Se puder mover os loops para dentro do código C tambe ajuda. Não deve mover tudo
para o C para não perder a flexibilidade do Python.
| Bom, fica o alerta para quem trabalha na área de otimização e algoritmos
| experimentais, incluindo heurísticas em geral. Se você estavam pensando
| em utilizar python nos seus projetos, pensem novamente.
Não vejo problema, desde que vc compare Python com Python. Afinal vc está otimizando
o algoritmo ou a implementação ?
| Como os resultados que são levados em conta nesta área comparam o tempo de
| execução das implementações (não importa em que linguagem),
Teria alguma referência de um paper para eu dar uma olhadela ?
| Vocês podem até se perguntar se isto influencia, mas sei que influencia,
| pois já implementei algoritmos que ficam rodando dias, às vezes semanas
| ou meses para atingir um resultado aceitável.
Ah, aí são outros 500's! (De onde será que veio essa expressão??)
Aí o que importa é otimização de execução. Um cuidado a ser tomado com
Python nestes casos é monitorar o consumo de memória e cuidar para seu
programa não começar a fazer swap. Já caí nessa armadilha fazendo software
para análise de monitoração em rede.
| Imagina uma implementação
| do mesmo algoritmo 6 vezes mais lenta.... ao invés de rodar em um dia,
| roda em uma semana. Ao invés de rodar em um mês, roda em 6 meses!!!!
Isso é verdade. Nestes casos otimizações agressivas são mais indicadas
e C é o canal.
Abração
Senra
,_
| ) Rodrigo Senra <rsenra |at| acm.org>
|(______ -----------------------------------------------
_( (|__|] GPr Sistemas http://www.gpr.com.br
_ | (|___|] IC - Unicamp http://www.ic.unicamp.br/~921234
___ (|__|]
L___(|_|] -----------------------------------------------
João Paulo Fernandes Farias
É o grasp.py
Rode ele sem parâmetros que ele dá uma dica.
No caso, eu coloquei os parâmetros do programa em python na linha de
comando, você deve usar o ch130.tsp sim. Mas pode usar o berlin52 que é
uma instância menor.
Já na implementação em C++ coloquei os parâmetros no código... :( Se
quiser alterar tem que mexer no código.
--
JP
Em Sáb, 2004-10-02 às 13:18 -0300, Rodrigo Dias Arruda Senra escreveu:
> [ João Paulo Fernandes Farias <jpaulo...@yahoo.com.br> ]
> -----------------------------------------------
> | Pois é... Implementei o mesmo algoritmo.
> |
> | Vou anexar as duas implementações, assim, se você tiver paciência, pode
> | testar, analisar e tirar suas conclusões.
>
> No caso do C++ não há duvida do que rodar João.
> Mas no caso do Python, qual o script que equivale
> a executar o main.cpp. É o geral/buscalocal.py ?
> Que instância usar, ch130.tsp ?
>
> t+
> Senra
>
> ,_
> | ) Rodrigo Senra <rsenra |at| acm.org>
> |(______ -----------------------------------------------
> _( (|__|] GPr Sistemas http://www.gpr.com.br
> _ | (|___|] IC - Unicamp http://www.ic.unicamp.br/~921234
> ___ (|__|]
> L___(|_|] -----------------------------------------------
>
>
Gustavo Barbieri
João Paulo,
Por que você não tenta usar o PyRex pra implementar o algoritmo?
http://www.cosc.canterbury.ac.nz/~greg/python/Pyrex/
Com ele você gera código C a partir de uma mistura de C e Python!
Olhe nos exemplos, se você usar:
a = 1
ele usa um PyObject
se você usar:
cdef int a
ele usa um int em C!
Eu acho que só na otimização de tipos você já reduz um bocado o tempo
de execução!
--
Gustavo Sverzut Barbieri
---------------------------------------
Computer Engineer 2001 - UNICAMP
GPSL - Grupo Pro Software Livre
Cell..: +55 (19) 9165 8010
Jabber: gsbar...@jabber.org
ICQ#: 17249123
GPG: 0xB640E1A2 @ wwwkeys.pgp.net
Rodrigo Dias Arruda Senra
[ João Paulo Fernandes Farias <jpaulo...@yahoo.com.br> ]
-----------------------------------------------
|
|
| Rode ele sem parâmetros que ele dá uma dica.
| No caso, eu coloquei os parâmetros do programa em python na linha de
| comando, você deve usar o ch130.tsp sim.
João,
a estrutura dessa app não ajuda no profiling.
fim = inicio + datetime.timedelta(seconds=tempo)
zero = datetime.timedelta()
iteracoes = 0
while fim - datetime.datetime.now() >= zero:
... # código suprimido aqui
if melhor.custo == otimo:
break
Este loop sempre vai levar pelo menos <seconds>.
Simplifiquei ao máximo a estrutura para constar apenas as rotinas
que interessam, do ponto de vista de medida de tempo.
O trecho aser medid ficou assim:
<code>
import solucao
import construcao
import instancia
import buscalocal
if __name__ == "__main__":
#import psyco
#psyco.full()
inst = instancia.Instancia("../instancias/ch130.tsp")
sol = solucao.Solucao(inst)
sol.rota, sol.custo = construcao.construir(inst)
buscalocal.twoOpt(sol, inst)
</code>
As medidas foram:
# Sem otimização, psyco desabilitado (Erro: 0:00.2)
8.36user 0.01system 0:08.47elapsed
# Com psyco ligado (Erro: 0:00.08)
1.68user 0.01system 0:01.70elapsed
Primeira observação: Psyco faz um bom trabalho! Hooray 4 Armin Rigo!!
<profile>
time python grasp2.py
527 function calls in 8.380 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 8.380 8.380 <string>:1(?)
1 0.880 0.880 0.880 0.880 buscalocal.py:13(twoOpt)
1 7.270 7.270 7.310 7.310 construcao.py:9(construir)
1 0.000 0.000 8.380 8.380 grasp2.py:19(main)
1 0.010 0.010 0.190 0.190 instancia.py:11(__init__)
1 0.180 0.180 0.180 0.180 instancia.py:50(inicializarDistancias)
2 0.000 0.000 0.000 0.000 instancia.py:68(avaliar)
1 0.000 0.000 8.380 8.380 profile:0(main())
0 0.000 0.000 profile:0(profiler)
258 0.020 0.000 0.020 0.000 random.py:135(randrange)
258 0.020 0.000 0.040 0.000 random.py:198(randint)
1 0.000 0.000 0.000 0.000 solucao.py:8(__init__)
1 0.000 0.000 0.000 0.000 string.py:125(join)
8.42user 0.01system 0:08.77elapsed
</profile>
Segunda observação: O gargalo está em construcao.py !
Sugestões:
1) Sua instância é uma lista de listas de inteiros, subsituir isso por
uma matrix bidimensional usando módulo Numeric ou numarray
2) Substituir alguns loops de construcao.py por mecanismos disponíveis
no módulo itertools
3) Re-escrever apenas construir(instancia) em C
É isso aí.
[]s
Senra
,_
| ) Rodrigo Senra <rsenra |at| acm.org>
|(______ -----------------------------------------------
_( (|__|] GPr Sistemas http://www.gpr.com.br
_ | (|___|] IC - Unicamp http://www.ic.unicamp.br/~921234
___ (|__|]
L___(|_|] -----------------------------------------------
* Antes de enviar a sua pergunta procure por uma solução em:
http://pythonbrasil.com.br/
http://python.org
http://google.com
* Não envie e-mails HTML para a lista.
* Evite mensagens off-topic
Links do Yahoo! Grupos
<*> Para visitar o site do seu grupo na web, acesse: