Desempenho de algoritmos

Depois de muita propaganda aqui está o artigo sobre desempenho de algoritmos. =)

Os programadores sabem que sempre há mais de um jeito de obter o mesmo resultado, mas cada um vai apresentar um desempenho diferente.

Uma das melhores sequências para a comparação de diferentes implementações é a sequência de Fibonacci. Primeiro por ser possível usar diversos algoritmos clássicos, como recursão e reiteração, segundo porque é uma sequência que existe naturalmente, o que a torna fascinante em si.

Caso alguém não conheça a sequência de Fibonacci, ela começa assim:

1 1 2 3 5 8 13 21 34 55 89...

Os matemáticos gostam de começar de zero (0 1 1 2 3...), o que não está errado e funciona da mesma forma – aliás fica mais fácil de calcular –, no entanto se considerarmos a essência natural da sequência em vez de seu comportamento matemático (Leonardo Pisano Fibonacci era naturalista e viajante antes de matemático, mais ou menos como Wallace e Darwin), veremos que não é possível que o zero participe da sequência.

Cada elemento é igual à soma dos dois elementos anteriores, e os dois primeiros valores são 1 e 1.

Recursividade

A primeira implementação da sequência de Fibonacci – e também a mais óbvia – é o algoritmo recursivo (em inglês recursion).

Recursividade, recursão ou recorrência é quando uma determinada função faz chamada a ela mesma (com parâmetros diferentes!). O exemplo clássico é o fatorial:

— Qual o fatorial de cinco (5!)?
— É cinco vezes o fatorial de quatro (5 x 4!).
— E qual o fatorial de quatro?
— É quatro vezes o fatorial de três (4 x 3!).

Para que a recursividade funcione, é preciso haver um valor base, que funcione como parada para a recursão. No caso do fatorial, o valor base é 0! = 1, portanto:

5! = 5 x 4! = 5 x 4 x 3! = 5 x 4 x 3 x 2! = 5 x 4 x 3 x 2 x 1! = 5 x 4 x 3 x 2 x 1 x 0!
5! = 5 x 4 x 3 x 2 x 1 x 1 = 120

Fibonacci como faz duas recursões simultâneas, precisa de dois valores bases, que são o primeiro e o segundo elementos, que valem um (1). A partir daí já podemos montar nosso algoritmo recursivo:

def fib(n):
    if n < 2:
        return 1
    else:
        return fib(n - 2) + fib(n - 1)

Então, fib(0) = fib(1) = 1. Os demais valores são calculados somando-se os dois anteriores.

Ao se executar este algoritmo, podemos ver que seu desempenho cai exponencialmente em relação ao índice do elemento que se quer calcular, ou seja, é péssimo. O gráfico pode ser encontrado aqui.

Então por que pensar em recursividade?

Há algumas boas razões para isso. Primeiro porque é a maneira mais simples de resolver problemas que podem ser resolvidos desta forma; segundo porque ao se aplicar outro método chamado memoization seu desempenho aumenta assustadoramente, na mesma proporção em que aumenta a quantidade de memória requerida para resolvê-lo.

Reiteração

Reiteração (em inglês iteration) é o próprio algoritmo recursivo que foi aberto de forma a não alocar mais memória e tempo de processamento do que o necessário.

O grande problema da recursividade é que cada vez que a função se chama, ela aloca mais espaço de memória para as mesmas variáveis já em uso. Na reiteração as mesmas variáveis e a mesma memória alocada são usadas para todos os cálculos, reduzindo o tempo de processamento.

A implementação reiterativa é a seguinte:

def fib(n):
    a, b, c = 0, 1, 1
    while c <= n:
        a, b, c = b, a+b, c+1
    return b

Ao analisarmos o gráfico, podemos de cara ver que este é bem mais eficiente que o recursivo devido às grandezas dos valores no eixo y (tempo). Outra coisa que podemos reparar é que seu desempenho cai aritmeticamente (o tempo cresce em linha reta), favorecendo seu uso mesmo para índices mais altos.

Observação: devido à palavra inglesa, é comum alguns programadores dizerem iteração em vez de reiteração, o que é um neologismo desnecessário.

Memoização

Realmente não há uma palavra (não que eu conheça) em português para isso, então adaptei a palavra inglesa memoization.

Memoização é uma técnica de programação usada quando há muita memória disponível (comum hoje em dia mesmo em micros pessoais) e é necessária a efiência. Consiste em fazer cache de valores conhecidos para não que não seja necessário calculá-los novamente.

Para algoritmos não-recursivos, não faz muita diferença, a menos que se use diversas vezes os mesmos parâmetros. No entanto para algoritmos recursivos o ganho é enorme, apresentando muitas vezes desempenho superior ao equivalente reiterativo.

Então – caso haja memória suficiente – a memoização traz duas vantagens: ¹é possível usar o mais simples dos algoritmos (recursivo) e ²pode haver ganho de desempenho. Aliás, em se tratando de desempenho, o gráfico do algoritmo memoizado é quase linear com fator zero (no exemplo, oscilando por volta de 26µs).

Em Python usamos para memoização um técnica chamada «decoração», onde criamos um decorador que altera a função da forma desejada. Na verdade o decorador é uma metafunção ou classe que recebe como argumento a função original e devolve a função modificada.

O decorador para memoização em Python pode ser desenvolvido assim:

class memoize:

    def __init__(self, f):
        self.__cache, self.__func = {}, f
        self.__doc__ = f.__doc__
        for e in dir(f):
            if not e.statswith('_'):
                setattr(self, e, getattr(f, e))

    def __call__(self, *args, **kw):
        i = repr((args, kw))
        try:
            r = self.__cache[i]
        except KeyError:
            r = self.__func(*args, **kw)
            self.__cache[i] = r
        return r

Agora, basta reescrever a função recursiva com o decorador adequado:

@memoize
def fib(n):
    if n < 2:
        return 1
    else:
        return fib(n - 2) + fib(n - 1)

Matriz característica

A sequência de Fibonacci – assim como sequências semelhantes – pode também ser entendida como o resultado de uma determinada matriz elevada ao índice desejado. Basta então implementar suporte a cálculo matricial e calcular potência de forma binária.

Python possui um módulo chamado NumPy que dá suporte a matrizes, mas usa algoritmos muito lentos, portanto fiz minha própria implementação de matrizes, limitada a tratar matrizes 2x2 (que é o caso da matriz característica da sequência em questão).

A função ficou então assim:

matriz = Matriz_2x2(1, 1, 1, 0)
def fib(n):
    return pow(matriz, n)[0]

Este algoritmo só não ganha em desempenho para a memoização e a função fechada. Seu desempenho cai logaritmamente, se monstrando muito eficiente para altos índices.

Função Fechada

A partir dos autovalores da matriz característica ou do cálculo discreto da recorrência obtemos a função fechada da sequência.

A matriz característica da sequência de Fibonacci apresenta dois autovalores: e .

A função fechada é igual à subtração das potências dos autovalores pelo índice desejado dividida pela subtração dos autovalores: .

O único problema deste algoritmo é que ele calcula Fibonacci a partir de zero (0 1 1 2 3 5...), e queremos a sequência natural (a partir de 1: 1 1 2 3 5 8...), então temos de incrementar o argumento antes de poder tratá-lo:

def fib(n):
    n += 1              # incrementa o índice
    sqrt5 = pow(5., .5) # raiz quadrada de cinco
    autovalor = (1 + sqrt5) / 2, (1 - sqrt5) / 2
    resultado = (
                pow(autovalor[0], n) - pow(autovalor[1], n)
                ) / (
                autovalor[0] - autovalor[1]
                )
    return int(resultado + .5)  # arredonda o resultado

Como não há recursão, reiteração, cache e nem cálculo matricial, apenas álgebra linear, este algoritmo é altamente eficiente, sendo praticamente linear de fator zero.

No exemplo, tem um tempo de execução médio de 15,7µs até por volta do índice 46, depois sobe para 16,8µs até o índice 119, máximo do teste.

Ultimate Fibonacci

O nome é só uma brincadeira! Não é uma solução definitiva em absoluto!

Com consumo mínimo de memória, os algoritmos mais eficientes são o reiterativo e a função fechada.

Na verdade, como há uma queda aritmética de desempenho, o algoritmo reiterativo é mais eficiente que os demais apenas para índices baixos – nos exemplos até por volta do índice 21. Acima disso, o melhor algoritmo é a função fechada.

Obs.: a memoização foi descartada pelo alto consumo de memória.

Então, a idéia é usar o algoritmo reiterativo até onde ele ainda é mais eficiente e daí por diante usar a função fechada. O gráfico ficou assim.

Conclusão

O objetivo deste artigo foi apenas apresentar os diversos algoritmos clássicos para implementação de conjuntos discretos, sequências matemáticas.

A recursividade é a forma mais fácil de se implementar uma sequência, no entanto a menos eficiente – a menos que você tenha disponível muita memória, então pode usar a memoização para conseguir uma maior eficiência com a implementação mais simples.

A reiteração é a forma aberta da recursividade e o algoritmo que os programadores buscam, muitas vezes apenas porque desconhecem outras soluções.

A matriz característica é uma boa solução, se a potência de matrizes for implentada de forma binária (veja o método __pow__() da classe Matriz_2x2), caso contrário se torna muito ineficiente. De qualquer forma, a partir dos autovalores da matriz característica, é possível calcular a função fechada, que resolve a sequência por álgebra linear, método altamente eficiente e que não sofre muita variação ao longo da projeção cartesiana.

Esses algoritmos ainda podem ter desempenhos diferentes não apenas de máquina para máquina, mas também de um compilador/interpretador para outro.

Os gráficos de desempenho dos algoritmos se encontram em:

• Recursividade
• Reiteração
• Memoização
• Matriz característica
• Função fechada
• Ultimate Fibonacci

Códigos

[]'s