Comparação de desempenho

Estou estudando Haskell ao mesmo tempo em que me aperfeiçoo em Lua e Kepler.

Meu interesse em Haskell é usá-la como linguagem compilada, enquanto continuo usando Lua (e eventualmente Python) como linguagem geral.

Estava impressionado com a velocidade de Haskell em recursões, principalmente no cálculo de Fibonacci (que costumo usar para comparações de desempenho), resolvendo índices altíssimos em frações de segundo, enquanto a própria linguagem C demora para retornar algum resultado.

Foi então que me dei conta de que a implementação em Haskell de Fibonacci que eu estava usando aplicava memoização!

Resolvi refazer os códigos comparatórios usando memoização também nas outras linguagens.

Observação:

1. Não refiz em Java porque não conheço a linguagem o suficiente para trabalhar com memoização (imagino que haja algum módulo pronto) e números grandes.
2. Não refiz em C e C++ porque fiquei com preguiça de reescrever usando GNU MP.

Fiz os testes da seguinte forma: executei cinco vezes cada «programa» anotando seus tempos de execução; removi o maior e e o menor tempos; calculei a média geométrica.

Foi aí que tive uma surpresa agradável: Lua foi a segunda mais rápida!

Seguem as médias:

• Haskell: 4,0ms
• Lua: 21,7ms
• [update 2007-05-02]Ruby: 42,0ms[/update]
• Python: 58,0ms
• Perl: 97,3ms

[update 2007-05-02]
Escrevi errado da primeira vez!

Havia colocado microssegundo (μs) em vez de milissegundo (ms). Minha máquina não é tão rápida assim. =P

Desculpem!
[/update]

Agora os códigos (retirei os comandos de saída para stdout para medir as velocidades):

Haskell

module Main where

import IO

fib = 1 : 1 : zipWith (+) fib (tail fib)

main = do
    hSetBuffering stdin LineBuffering
    let num = fib !! 1000
    putStrLn (show num)

Lua

local fib
do
    local memo = setmetatable(
        { ["0"] = 1, ["1"] = 1 },
        { __mode = "k" }
    )

    function fib(n)
        if not memo["" .. n] then
            memo["" .. n] = fib(n - 2) + fib(n - 1)
        end
        return memo["" .. n]
    end
end

local num = fib(1000)
print(num)

[update 2007-05-02]
Ruby

def fib(n, memo={ 0 => 1, 1 => 1 })
    if not memo.member? n
        memo[n] = fib(n - 2, memo) + fib(n - 1, memo)
    end
    return memo[n]
end

num = fib(1000)
print(num)

Obrigado Fenrrir!
[/update]

Python

def fib(n, memo={ 0: 1, 1: 1 }):
    if not n in memo:
        memo[n] = fib(n - 2) + fib(n - 1)
    return memo[n]

num = fib(1000)
print(num)

Perl

use Memoize;

sub fib {
    my $n = shift;

    if ($n < 2) {
        return 1;
    } else {
        return fib($n - 2) + fib($n - 1);
    }
}

memoize 'fib';

my $num = fib 1_000;
print "$num\n";

exit 0;

[]'s
Rodrigo Cacilhas