Em Ruby:
1 2 3 4 5 6 7 8 9 10 11 |
def fib(n) if n == 0 || n == 1 n else fib(n-1) + fib(n-2) end end 36.times do |i| puts "n=#{i} => #{fib(i)}" end |
E em Python:
1 2 3 4 5 6 7 8 |
def fib(n): if n == 0 or n == 1: return n else: return fib(n-1) + fib(n-2) for i in range(36): print "n=%d => %d" % (i, fib(i)) |
Os resultados foram os seguintes:
Ruby 1.8.6: | 158.869s |
Python 2.5.1: | 31.507s |
Ruby 1.9.0: | 11.934s |
Claro que isso não diz necessariamente muita coisa. O JRuby, por exemplo, ultrapassa o Ruby MRI em vários testes isolados como esse mas quando roda uma aplicação Rails inteira, ele fica um pouco para trás em alguns cenários. Uma das razões é Regular Expression, como explica Ola Bini.
Enfim, claro que um artigo com um título desses não iria ficar sem resposta por muito tempo. E eis uma delas
Só que aqui o autor cometeu outro erro. Ele resolveu mudar o algoritmo de Python para usar generators:
1 2 3 4 5 6 7 8 9 10 |
def fib(n): a, b = 0, 1 i = 0 while i < n: yield (i, a) a, b = b, a + b i += 1 for i, f in fib(36): print "n=%d => %d" % (i, f) |
No micro dele o resultado caiu para ‘espantosos’ 0.078s apenas! 1000 vezes mais rápido do que o Ruby 1.9 no algoritmo acima. Claro, há um erro nessa comparação, nos comentários está explicado: esse autor comparou um algoritmo recursivo em Ruby com um não-recursivo em Python. Eis uma versão parecida em Ruby:
1 2 3 4 5 6 7 8 9 10 11 |
def fib (n, &block) a, b = 0, 1 i = 0 while i < n yield [i, a] a, b = b, a + b i += 1 end end fib(36) { |i, f| puts "n=#{i} => #{f}" } |
Mas o que eu queria mostrar foi uma versão que estava em um dos comentários onde, na máquina desse programador em particular, rodou em 0.008 seg.
1 2 3 4 5 6 7 8 9 |
@cache = [] def fib(n) return @cache[n] if @cache[n] return n if n < 2 return @cache[n] = fib(n-1) + fib(n-2) end 36.times {|n| puts "fib(#{n}) = #{fib(n)}" } |
Achei uma implementação interessante e como eu acabei de falar de blocos e estou dando curso de Rails, talvez interessasse aos estudantes. Porém fica um alerta: Ruby não é melhor que Python nem vice-versa, o assunto é amplo demais para generalizar assim. O bom e velho Python continua sendo uma excelente linguagem e espero que Ruby 1.9 evolua bem também.
Update 30/11: O Rodrigo Kochenburger compilou algo semelhante ao último algoritmo acima, mas usando Hash:
1 2 |
fibonacci2 = Hash.new {|hsh,key| hsh[key] = key < 2 ? key : hsh[key-1] + hsh[key-2] } 10000.times {|i| puts fibonacci2[i] } |
Os tempos caem dramaticamente. Para apenas 36 vezes (que é muito pouco):
real 0m0.009s user 0m0.005s sys 0m0.004s
E para 10 mil vezes:
real 0m20.190s user 0m11.513s sys 0m0.345s
Então, resolvi fazer uma versão em Java 1.5 (meu Java está ficando enferrujado …), veja só:
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 |
import java.util.HashMap; import java.math.BigDecimal; class Teste { static HashMap<BigDecimal,BigDecimal> hsh = new HashMap<BigDecimal,BigDecimal>(); static final BigDecimal CONST_1 = new BigDecimal(1); static final BigDecimal CONST_2 = new BigDecimal(2); public static void main(String[] args) { BigDecimal total = new BigDecimal(args[0]); BigDecimal count = new BigDecimal(0); while ( count.compareTo(total) < 0 ) { System.out.println(fibonacci(count)); count = count.add(CONST_1); } } public static BigDecimal fibonacci(BigDecimal i) { if ( i.compareTo(CONST_2) < 0 ) { hsh.put(i, i); return i; } BigDecimal left = hsh.get(i.subtract(CONST_1)); BigDecimal right = hsh.get(i.subtract(CONST_2)); if ( left == null ) left = new BigDecimal(0); if ( right == null ) right = new BigDecimal(0); BigDecimal res = left.add(right); hsh.put(i, res); return res; } } |
Ouch, tenho certeza que dá para melhorar esse meu código, mesmo assim o mesmo algoritmo de duas linhas do Ruby se tornou este monstro no Java :-) Eu sei, eu sei, é um caso específico. De qualquer forma, testando para 36 vezes temos estes tempos:
real 0m0.135s user 0m0.082s sys 0m0.036s
Como esperado, o Java fica muito atrás. Mas 36 vezes é muito pouco. Não dá tempo da JVM otimizar o bytecode em tempo de execução com o JIT, mas em 10 mil vezes deve dar:
real 0m21.379s user 0m11.095s sys 0m0.530s
Agora sim, literalmente se igualou ao Ruby. Isso demonstra a maturidade da JVM e porque Charles Nutter acredita que é possível sim ter JRuby mais rápido do que o MRI, aplicando as otimizações nos lugares certos.
A título de comparação rodei o algoritmo não-recursiva de Python na mesma máquina. Os resultados para 36 vezes foram:
real 0m0.020s user 0m0.010s sys 0m0.010s
E para 10.000 vezes foram:
real 0m16.376s user 0m8.695s sys 0m0.301s
Impressionante. Em 10 mil vezes dá para ver que o Python foi pelo menos 30% mais rápido do que Ruby 1.8 e Java 1.5. Infelizmente eu não tenho instalado nem o YARV nem o Java 1.6, também não estou com paciência para tentar CPython :-) Alguém se habilita?
Update 2, 30/11: Bom, a curiosidade matou o gato :-) Baixei o Yarv e compilei no meu Macbook. Eis os tempos pro mesmo algoritmo de Hash com 36 vezes:
real 0m0.027s user 0m0.007s sys 0m0.005s
E agora com 10 mil vezes:
real 0m19.830s user 0m11.545s sys 0m0.434s
O Python continua ganhando :-) Melhorou um pouco em relação ao Ruby 1.8 mas não tanto assim, pelo menos para esse algoritmo. Não sei se tem alguma coisa para fazer na compilação para melhorar.