Ruby 1.9 vs Python

2007 November 30, 14:44 h

Mais um incauto pecou (propositadamente) ao escrever um artigo Holy Shmoly, Ruby 1.9 smokes Python away!. Sua intenção era demonstrar como o Ruby 1.9 já é muito mais rápido do que Python.

Para isso ele fez o bom e velho algoritmo de Fibonacci (versão recursiva) em ambas as linguagens. Na verdade minha intenção nem de longe é comparar com Python, mas para iniciantes em Ruby o algoritmo que vou colocar no final do artigo pode ser interessante de estudar.

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.

tags: obsolete python

Comments

comentários deste blog disponibilizados por Disqus