Ruby 1.9 vs Python

2007 November 30, 14:44 h - tags: python obsolete

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.

Comments

comentários deste blog disponibilizados por Disqus