Posts Tagged ‘ Recursividade ’

Criador de Funções com Metaclasses

Esse é um projeto que fiz meses atrás para gerar funções em Python com operadores matemáticos usando metaclasses.
Com isso, você pode fazer:

g = f ** 2 + 1   #função que eleva ao quadrado e soma 1
g(10) == 101

O código abaixo é uma versão (muito) simplificada do módulo que coloquei no GitHub, mas serve como exemplo de uso de metaclasses em Python (neste caso, Python 3):

import operator

class MetaFuncBuilder(type):
    def __init__(self, *args, **kw):
        super().__init__(*args, **kw)
        attr = '__{0}{1}__'

        for op in (x for x in dir(operator) if not x.startswith('__')):
            oper = getattr(operator, op)
            op = op.rstrip('_') #special case for keywords: and_, or_

            def func(self, *n, oper=oper):
                return type(self)(lambda x: oper(self.func(x), *n),
                                  self.op + [(oper.__name__, n[0])
                                             if n else oper.__name__])
            def rfunc(self, n, *, oper=oper):
                return type(self)(lambda x: oper(n, self.func(x)),
                                  self.op + [(n, oper.__name__)])
           
            setattr(self, attr.format('', op), func)
            setattr(self, attr.format('r', op), rfunc)

class FuncBuilder(metaclass=MetaFuncBuilder):
    def __init__(self, func=None, op=None):
        self.op = op if op else []
        self.func = func if func else lambda x: x

    def __repr__(self):
        return '<var %s>' % self.op

    def __call__(self, *args):
        if not args:
            return self.func() #unary operators
        required, *args = args
        out = self.func(required)
        return out(*args) if args else out

f = FuncBuilder()

Em duas situações é comum o uso de metaclasses em Python: para que um certa classe tenha propriedades novas ou para automatizar algum mecanismo nas classes. Neste caso, usei para automatizar a criação de métodos para cada operador em Python, com ajuda do módulo operator.

Em Python, os operadores matemáticos binários existem nas formas __op__, __rop__ e __iop__, onde op é o nome, r significa que o objeto é o segundo operador e i significa in-place. Outros operadores existem em apenas uma forma.
Assim, o código pega os operadores e cria as três formas de cada um (os que existem em apenas uma forma ficam com 2 formas extras que não causam problema algum, já que não são nunca chamadas) e todos os operadores, ao invés de executar a operação designada, apenas criam uma novo objeto-função que pode ser chamado ou ter novas funções adicionadas.

O módulo no GitHub tem uma centena de outras funcionalidades para gerar essas funções, mas ele sofre de um problema que pode ser bem sério: Chamadas de função em Python são caras!

Basicamente, cada objeto do tipo FuncBuilder guarda a operação que tem que executar e o próximo da lista. Isso gera um monte de chamadas de função em cima dos operadores, o que pode deixar o código muito mais lento.

Minha próxima alteração pra esse código seria juntar todas as operações numa só chamada de função, o que não vai permitir extrair uma função de dentro de outra (como é possível agora por meio de closures), mas vai reduzir o custo para apenas uma chamada de função, como seria natural. Isso não vai ser tão simples por causa dessa estrutura recursiva da classe, mas quando tiver tempo, eu faço.

Os Bonacci’s

Não consigo entender o motivo de todo professor de computação inventar de mostrar a série de Fibonacci ao começar um curso ou apresentar uma nova linguagem.

O problema não é a série, mas sim a aberração recursiva (não dá para chamar de algoritmo) que calcula o n-ésimo termo da sequência em tempo O(2n).

Para quem não se lembra,

def fibonacci(num):
    if num == 0: return 0
    if num == 1: return 1
    return fibonacci(num-1) + fibonacci(num-2)

Se for para calcular apenas uma vez e até o vigésimo termo num computador que rode a uns 2GHz não vai dar para notar as mais de 10 milhões de chamadas recursivas pois isso pode ser feito em poucos milissegundos.

Se quiser ir mais longe e calcular o Fibonacci de 47, último que cabe num inteiro unsigned de 4 bytes, você vai levar uns bons 40 ou 50 segundos usando uma linguagem compilada como C, C++ ou até vários minutos com o algoritmo acima em python.

Minha grande dúvida é: Por que usar um algoritmo com essa complexidade se existe um em O(n), fazendo as somas até chegar no n-ésimo elemento e outro em O(log2(n)) usando a proporção áurea, também conhecido como número de ouro?

Encontramos o elemento fazendo:

Onde

Assim, para calcular o n-ésimo termo da série de Fibonacci, basta arrendondar o valor de F(n).

A complexidade desse algoritmo é log2(n) pois a exponenciação não é feita em apenas uma operação.

Obviamente, esse algoritmo está limitado à representação em ponto flutuante da máquina. Utilizando um double, é possível ter um número que varia de 10-308 até 10308, mas a precisão só vai até 15 algarismos. Assim, para elementos acima de F(70), o computador vai começar a errar o valor de da série a partir do 15º algarismo.

Se a ideia é fazer um gerador da série de Fibonacci, o melhor algoritmo é o que seria usado para encontrar o valor em O(n), mas, como vamos sempre ter os valores anteriores, encontrar o próximo elemento será em O(1):

#Exemplo de gerador
def geraFibonacci(num):
    ultimos = [0,1]
    for i in range(num):
        if i <= 1:
            yield i
        else:
            ultimos = [ ultimos[-1], sum(ultimos) ]
            yield ultimos[-1]
    return

OBS: Para Python 2.x, sempre usar xrange() no lugar de range()

O legal da série de Fibonacci é que ela é mais que “a soma dos dois elementos anteriores”. Mais elegante é dizer que o termo seguinte é o anterior vezes o número de ouro.

Definido isso, podemos até colocar números na base φ, pois, como fazemos na base 2, cada número da série é o anterior vezes 2.

O número 101002 vale 24 + 22 = 20
O numero 10100φ vale F(4) + F(2) = 4.

Na representação escolhida para a base φ, os dois últimos “bits” devem sempre valer zero, pois a série começa em 0, 1, 1, 2, 3, 5… e teríamos um número 1 repetido e um número 0 que não acrescenta nada.

Para entender melhor o porquê desses algarismos serem zero, ao escolher dois termos consecutivos da série de Fibonacci para representar um número na base φ, seria o mesmo que pegar o seguinte já que ele é a soma dos outros dois. Assim , 100110000 = 101000000. Da mesma forma, 100011 = 100100.

Num exemplo mais prático, 27 = 21+5+1+0 = F(8) + F(5) + F(1) + F(0) = F(8) + F(5) + F(2) = 100100100φ.

Visto isso, podemos variar um pouco a série de Fibonacci para encontrar outras, como a Negafibonacci onde é definido F(n) para n < 0, sendo F(-n) = (-1)n F(n).

Mais interessante ainda são as séries que generalizam a quantidade de termos anteriores para formar o atual. A mais conhecida é a de Tribonacci, mas você pode fazer “Quadrinacci”, “Hexanacci”, etc.

A série de Tribonacci define os três primeiros termos como [0, 1, 1] e calcula os seguintes com a soma dos 3 anteriores. Com ela, teríamos uma razão dada pela raiz real da equação t3-t2-t-1 = 0 que vale aproximadamente 1.839287.

É possível ver que a razão da série vai aumentando ao usar mais termos para calcular o seguinte. Assim, poderíamos generalizar e encontrar a série de N-nacci que pegaria os N termos anteriores para achar o atual. Apenas temos que definir os primeiros N elementos.

Para ficar coerente, sempre começamos com 0 e 1 e depois colocamos os seguintes imaginando que antes do 0 teríamos mais zeros. Para N = 8, por exemplo, definimos 0, 1, 1, 2, 4, 8, 16, 32.

Já deu para perceber que fora os dois primeiros termos definimos os seguintes são da forma 2k, k variando de 0 a N-2. Assim, para N tendendo a infinito, a Série de “Infinitonacci” irá ter uma razão de 2 e teremos chegado à representação na base 2!

# N-nacci
def Nnacci(num, N=2):
    if N < 2: N=2
    lista = [0,1]
    lista += [2**i for i in range(0,N-2)]

    if num <= N-1:
        return lista[num]
    for i in range(num-(N-1)):
        lista = lista[1:] + [sum(lista)]
    return lista[-1]

Exemplos:
Para N = 2 : φ ~ 1.618034
Para N = 3 : φ3 ~ 1.839287
Para N = 4 : φ4 ~ 1.927562
Para N = 5 : φ5 ~ 1.965948
Para N = 8 : φ8 ~ 1.996031
Para N = 10 : φ10 ~ 1.999019
Para N = 20 : φ20 ~ 1.999999

Se olhar com calma, é bem simples de entender que a série de “Infinitonacci” tem razão 2, pois

Ou seja, o próximo termo vale a soma de todos os anteriores + 1.

Qual a utilidade disso tudo?
Bem, ainda não sei.