Jumpi’s Notepad

My annotations about the life, universe and everything!!! ;)

Posts Tagged ‘fibonacci

O Python e a sua misteriosa otimização de chamada de função

with 4 comments

Continuando a saga de Fibonacci, eu e meu amigo Marcio fizemos algumas correções e tcharam… devo reconhecer… o script python quando faz chamada de função consegue ser incrivelmente mais rápido que o script perl, também fazendo chamada de função. Porem descobrimos uma coisa muito bizarra e que nos chamou a atenção enquanto realizávamos os testes e por isso foco a minha atenção em relação ao teste feito com python…

Rodando o seguinte código, feito inline em python:

#!/usr/bin/python
for i in range(1000000):
a, b = 0, 1
for j in range(71):
a, b = b, a+b
return b

Profiling do código com chamada de função:


alan@desenv:~$ python -m cProfile fibo.py
1000005 function calls in 86.083 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 86.083 86.083 :1()
1 57.280 57.280 86.083 86.083 fibo.py:7()
1 0.000 0.000 86.083 86.083 {execfile}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
1000001 28.802 0.000 28.802 0.000 {range}

E agora o mesmo código, só que realizando chamada de função:


#!/usr/bin/python
import sys
#import psyco
def fib(n):
a, b = 0, 1
for j in range(n):
a, b = b, a+b
return b

x = int(sys.argv[1])
y = int(sys.argv[2])
for i in range(x):
fib(y)

Profiling do código com chamada de função:


alan@desenv:~$ python -m cProfile fibo.py
2000005 function calls in 35.174 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 35.174 35.174 :1()
1 4.785 4.785 35.173 35.173 fibo.py:6()
1000000 25.671 0.000 30.327 0.000 fibo.py:6(fib)
1 0.000 0.000 35.174 35.174 {execfile}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
1000001 4.718 0.000 4.718 0.000 {range}

Ou seja, tirando o tempo de overhead do profile, o programa que realiza a chamada de função, consegue ser incrivelmente mais rápido que o programa inline, mesmo efetuando mais chamadas.

Bem… achei isso muito bizarro, sendo que, teoricamente o esperado era que o inline fosse mais rápido. Bem, se alguém puder me explicar isso eu agradeço bastante, pois a única conclusão que consegui tirar ate aqui, e que o python, mesmo sem usar otimizadores, vide psyco, já tem uma otimização natural de funções, o que torna as chamadas de função extremamente rápidas, porem eu queria entender essa otimização de chamada de funções, pois gostei bastante e fiquei interessado em saber como tal feature funciona.

E agora a minha conclusão em relação ao que eu aprendi com esse teste ate aqui, se você precisa fazer um programa bem rápido para testar qualquer coisa, use perl, resolve na maioria dos casos, agora se você precisa de um teste mais elaborado, com chamada de função, vou começar a pensar em usar o python…

Written by jumpi

January 11, 2008 at 3:06 am

Posted in Pessoal, Programming

Tagged with , ,

Fibonacci Series Test (Perl and Python)

with 7 comments

Post in portuguese about my tests with Fibonacci Series using perl and python…

Esses dias, para ser mais exato, na segunda-feira, o meu colega de trabalho marcio a.k.a. tio estava falando sobre a sua escolha para criar um projeto de site que ele esta fazendo e para testar ele implementou o algorítimo de Fibonacci usando C, C++, Ruby e Python e mediu o tempo utilizando o comando time… C e C++ entraram na lista so para ele poder criar um parâmetro. E então ele decidiu escolher pelo python devido ao tempo, porem, ele esqueceu do nosso velho amigo Perl e eu disse a ele que perl executava o mesmo teste mais rápido que python e ele me desafiou, ou seja, estou fazendo esse teste para demonstrar que o nosso velho amigo perl pode ser bom, lembrando que não sou um bom programador python, mais tentei deixar o código o mais próximo possível entre ambas as linguagens para que nenhum boi-corneta (como diria o meu amigo Caloni, gostei da expressão, por isso a utilizei aqui também) venha se espantar aqui…

Bem… para a realização desse teste, utilizei o meu laptop, um macbook com perl 5.8.8 e python 2.5.1 como podem ver abaixo:

[jumpi@Painkiller]~/Sources: perl -v
This is perl, v5.8.8 built for darwin-thread-multi-2
level (with 1 registered patch, see perl -V for more detail)
Copyright 1987-2006, Larry Wall
[jumpi@Painkiller]~/Sources: python -V
Python 2.5.1

Para fazer os testes, utilizei uma versão iterativa do algorítimo de Fibonacci (afinal de contas, poderia apelar para a recursiva, porem achei melhor utilizar essa para o teste), segue abaixo o código:

Em perl:

#!/usr/bin/perl
use strict;
my $n = shift;
my ($a,$b)=(1,2);
print "$a\n$b\n";
for(1..$n-2) {
  ($a,$b) = ($b,$a+$b);
  print "$b\n"
}

Em python:

#!/usr/bin/python
import sys
def fib(n):
 a, b = 0, 1
  for i in range(n):
   print b
   a, b = b, a+b
n = int(sys.argv[1])
fib(n)

E executei ambos os códigos, fazendo 10000 iterações e medindo o tempo usando o comando time, onde obtive o seguinte resultado:

Em perl:

real	0m0.188s
user	0m0.054s
sys	0m0.047s

Em python:

real	0m10.778s
user	0m8.104s
sys	0m0.231s

Well… ai esta a prova, pelo que posso ver o nosso velho amigo rabugento perl terminou a sua tarefa em um tempo menor que o python, pelo que posso enxergar, 10x mais rápido???

Brincadeiras a parte, através desse teste simples, podemos perceber que o perl, mesmo estando ultrapassado na visão de muitos, ainda executa muito bem o serviço, logico que poderíamos utilizar n técnicas em ambas as linguagens. Porem, como eu disse no principio, tentei simplificar ao máximo para não criar vantagens para nenhum dos lados.

Quero nesse post agradecer ao tio, pois sem ele, não teria o porque executar esses testes e ao amigo Caloni de onde tirei expressões para compor esse post…

Tio, vamos fazer o projeto utilizando perl + catalyst??? Hein??? Hein??? To Brincando!!! ;D

Written by jumpi

January 9, 2008 at 4:07 am

Posted in Math, Pessoal, Programming

Tagged with , ,