Bit Expressions com Erlang – P1

Aos poucos venho estudando uma nova linguagem que vem me encantando: Erlang. Ainda estou aprendendo o seu básico, mas já consigo enxergar algumas funcionalidades interessantes, apesar de ainda estar me acostumando com o paradigma funcional.

Erlang proporciona um mecanismo interessante de representação em formato binário, o que se justifica se lembrarmos que a linguagem foi desenvolvida para se trabalhar com telecomunicações (a linguagem foi desenvolvida pela Ericsson. Nas fontes que consultei existem divergências sobre a origem do nome Erlang. Há alguns lugares que dizem ser a contração de ERicsson LANGuage. Outras fontes afirmam ser uma referência ao matemático Agner Krarup Erlang).

Esse mecanismo de representação binária facilitaria a transmissão e manipuação, em nível de bit, dos dados. Por Exemplo, para se representar uma sequência de bytes em Erlang, envolvemos a em << … >>:

<<1, 77, 32, 88 >>.

Isso representa justamente quatro bytes, contendo os valores decimais: 1, 77, 32 e 88. Se quisermos entrar com os bytes em, por exemplo, hexadecimal, devemos explicitamente indicar a base:

<< 16#1, 16#4d, 16#20, 16#58 >>.

Okay, o leitor diria, até agora não vi nada de diferente em relação à uma lista. Por exemplo, eu poderia simplesmente fazer

[ 16#1, 16#4d, 16#20, 16#58 ].

e tudo daria no mesmo.

A primeira diferença em se usar Binary Sintax em Erlang é que este trunca os valores em 255 (ou 8 bits, FFh, como você preferir enxergar), ou seja, qualquer valor que for colocado acima de 255 ocasionará um overflow, justamente como um sistema difgital puro se comporta. Por exemplo:

<< 257 >>.

retorna:

<<1>>

Isso faz muito sentido, pois estamos trabalhando com bytes diretamente.

Bem, essa foi só uma rápida introdução para que possamos chegar onde eu desejo, que é a notação Binary Sintax do Erlang. Essa notação nos permite trabalhar com conjunto de dados estipulando arbitrariamente o tamanho de cada elemento em bits (isso mesmo, bits, não bytes). Imagine por exemplo que eu quero salvar um conjunto de dados que tem três elementos, cada qual pode ocupar uma faixa bem definida de valores. Com base nos valores máximo eu posso estipular a quantidade específica de bits a serem utilizados em sua representação.

Vamos ver isso de uma maneira mais prática:

Proposta – Representar em uma stream de bits o valor de um pixel que contém as três cores (Red, Green e Blue) em níveis que varias:
0~31 para R
0~63 para G
0~31 para B

Aqui usamos um bit a mais para representar a cor verde, pois o olho humano tem uma maior sensibilidade à essa cor. Perceba que estamos falando em quantidade de bits necessários para representar cada cor, e não quantidade de bytes. Se pretendêssemos usar, por exemplo, uma struct C para representar esse conjunto fariamos mais ou menos assim:

struct RGB{
char r;
char g;
char b;
};

Assim eu aloquei 8 bits para cada cor. O que é completamente desnecessário, pois a se olharmos para a faixa que vada valor deve representar, e cpontarmos quantos bits realmente são necessários, teremos:

Cor     Faixa     Bits
R         0~31         5
G         0~63         6
B         0~31         5
Total                  16

Notamos aqui que não são necessários mais que 16 bits para representar as cores RGB no nosso sistema, porém estamos trabalhando com uma struct de três chars, o que consome 24 bits. Uma alternativa é você representar as três cores em um array de char de tamanho 2, porém caberia a você toda a manipulação dos bits, o que daria um pouco de trabalho (mas nada que um programador competente não resolva em uma tarde).

A grande sacada de se usar Bit Syntax em Erlang é que você pode especificar quantos bits cada elemento deve ocupar, e quando você passa um valor que não cabe naquele elemento, ele se comporta da mesma maneira descrita anteriormente: ocorre-se um overflow. Vamos, utilizando bit syntax, passar os valores de RGB e recupera-los na forma de um stream de 16 bits:

R = 15.
G = 52.
B = 19.
<< R:5, G:6, B:5 >>.

note que a saída foi <<126,147>>, um bit stream de exatamente 16 bits. Podemos agora encapsular isso, e cuidar para que ninguém coloque valores fora da faixa especificada:

-module(rgb).
-export([marshall/3, unmarshall/1]).

marshall(R,G,B) ->
  if
    R > 31 ->
      throw({overlimit, R});
    G > 63 ->
      throw({overlimit, G});
    B > 31 ->
      throw({overlimit, B});
    true -> true
  end,
  << R:5, G:6, B:5 >>.

unmarshall(Binary) ->
<< R:5, G:6, B:5 >> = Binary,
  {R,G,B}.

Salvando esse código em um arquivo de mesmo nome de seu módulo (rgb.erl), vamos entrar no console Erlang e compila-lo:

> c(rgb).
{ok,rgb}

Pronto, agora estamos aptos a usar tanto as funções marshall e unmarshall que empacotam nossos valores RGB em stream de bits e desempacotam esse stream, devolvendo uma tupla com esses valores.

Exemplo:

rgb:unmarshall(rgb:marshall(8,19,30)).

Esse é um exemplo simplório da utilização de bit syntax em erlang, mas já dá pra ter uma pequena noção do seu poder.A idéia é explorar um pouco mais com coisas mais complexas, que provavelmente nos daria muito trabalho implementando em linguagens como C.

Pela união dos seus poderes…

Em um post anterior sobre complexidade algorítmica eu utilizei de diferentes implementações de algorítmos que executavam a mesma tarefa: encontrar um subset de números primos dentro de um conjunto maior de elementos. Na ocasião eu utilizei as implementações para exercitar um pouco de cálculo de complexidade, e o nosso foco era comprovar na prática o que a teoria (o cálculo de complexidade algorítmica) nos revelava.

Desta vez vamos utilizar uma aproximação silmilar, utilizando algorítmos diferentes que realizam o mesmo propósito porém com eficiências diferentes. Porém a nossa meta neste caso é demonstrar como podemos unir idéias que a princípio parecem desconexas para um mesmo fim, melhorando implementações e nos dando um ganho considerável de tempo.

Formalizando o problema

Uma problema que todo mundo implemente ainda nos primeiros meses de aprendizado de programação é a implementação dos Números de Fibonacci. A definição formal da sequência fibonacciana é a seguinte:

Assim, a série de Fibonacci começa com os dois elementos iguais a 1, posteriormente temos:

Um dos motivos que os professores gostam de mostrar a sequência de Fibonacci no início do aprendizado de programação dos alunos é que a esta sequência, por ser naturalmente recursiva, é facilmente implementável e demonstra ao aluno a idéia básica de recursão. Geralmente a implementação demonstrada pelos professores é similar à seguinte:

def fibo(n):
  if n==0 or n==1:
    return n
  else:
    return fibo(n-1)+fibo(n-2)

Este código é bem simples, e a recusão está bem fácil de se identificar. Porém um dos motivos que eu não gosto deste algoritmo (principalmente para mostrar para programadores que estão começando a aprender) é que este método é extremamente ineficiente. Para exemplificar, na minha máquina (um MacBook) esse algoritmo gastou pouco mais de 1:30 minutos para encontrar o valor do quadragésimo número da sequência, retornando fibo(40)=102334155. O valor está correto, mas o tempo gasto para o seu cálculo apenas reflete a fraquesa de implementação em se tratando de eficiência. Uma implementação iterativa como a seguinte:

def fibo2(n):
	if n==0 or n==1:
		return n
	n -= 1
	previous=1
	current=1
	while n>1:
		previous,current = current, current+previous
		n -= 1
	return current

resolve o mesmo problema proposto para a mesma entrada (n=40) em cerca de 110 ms (no mesmo computador). Vamos rapidamente analizar os dois códigos e tentar entender o porque desta diferença. Se olharmos para a recursão podemos claramente retirarmos a forma básica da expressão de tempo para n=1 ou n=0. Para ambos a a resposta é direta, o tempo gasto sempre será constante, portanto T(1)=t(0)=O(1).

Porém se a entrada for maior ou igual a 2, o custo computacional pode ser representado pela soma dos tempos necessários para o cálculo de f(n-1) e f(n-2). Assim fechamos nossa fórmula recursiva para o primeiro caso em:

Se resolvemos a recursão pela método da árvore de recursão, abrindo a recursão na forma de uma árvore com dois ramos (que são as duas chamadas recursivas), contabilizamos que a quantidade de passos a se executar é proporcional ao resultado de f(n). Em palavras mais simples, a quantidade de passos para se calcular cresce na sequência fibonacciana. Logo:

que, assintoticamente, cresce exponencialmente (a solução desta recursão passo a passo não convém neste post, mas pode ser abordado em um outro momento).

Por fim temos que:

Já no segundo caso a análise é muito mais simples. O nosso algoritmo tem um único loop que corre n unidades, assim temos:

o que significa que a segunda implementação tem comportamento linear. Isso claramente nos responde o porque a segunda implementação (iterativa) é tão mais eficiente que a primeira (recursiva), pois:

Porém essa análiaze nem de logne prova que toda solução recursiva (ou com comportamento recursivo) tem eficiência inferior à uma iterativa (sequer essa é a intenção deste post, lembra?).

Vamos nesse momento reservar essa primeira parte do post e mostrar um segundo caso idenpendente.

Potenciação

Um outro exemplo simples que professores podem adotar para demonstrar recursão é a soluçao de potenciação. A potenciação é simplesmente a multiplicação n vezes de uma base b por ela mesmo. Assim:

   n vezes

Uma implementação simples com recursão segue:

def pow(b,n):
  if n==1:
    return b
  return b*pow(b,n-1)

O bacana é que essa implementação roda em T(n)=O(n), ou seja, linearmente. Mas como nunca devemos nos contentar com o que já temos, podemos pensar em como melhorar essa implementação. A primeira coisa que podemos melhorar é implementar recursão-em-cauda para que o espaço ocupuado em memória não cresça ao aumentar o tamanho de n(Nota: mesmo com nossas implementações estando em Python, o fato de a linguagem suportar ou não a recursão em cauda aqui é desprezado, pois o que nos interessa é a metodologia aplicada na resolução).

def pow2(b,n,acc=1):
  if n==1:
    return b*acc
  return pow2(b,n-1,acc*b)

Mesmo com esse problema resolvido o nosso custo computacional permanece intacto. Para melhorarmos isso podemos recorrer a uma propriedade da potenciação que nos diz que:

O que, por exemplo, nos leva a dividir o cálculo

que gasta 3 multiplicaçoem em

que consome apenas duas (note que o mesmo cálculo 4^2 não precisa ser computado duas vezes). Agora basta chamarmos recursivamente para cada n/2, apenas fazendo uma pequena alteração para os casos de n ser ímpar:

def pow3(b,n):
  if n==1:
    return b

  if n%2:
    h = pow3(b,(n-1)/2)
    return b*h*h
  else:
    h = pow3(b,n/2)
    return h*h

Uma rápida análise deste código nos extrai a forma recursiva do custo computacional desta nova forma:

Essa recursão pode ser facilmente resolvida se você imaginar que a cada vez que você dobra n você incremente em O(1) o valor de T(n). Isso nos leva a uma função logarítmica de base dois:

O que é bacana, pois diminuímos aqui o comportamento assintótico do cálculo da potência de b^n pois:

Nesse nosso segundo exemplo, ao contrário do primeiro, o uso da recursão melhororu bastante o desempenho da nossa implementação. Utilizando a técnica de dividir e conquistar, nós quebramos uma potenciação em duas mais simples de se efetuar, e depois recombinamos o resultado. Porém ainda não chegamos no intuito final desse texto que é a união de técnicas com propósitos distintos para ganharmos em desempenho.

Método de Fibonacci por matrizes

Uma maneira bacana de se encontrar a sequência de fibonacci é analizando a matriz

Se multiplicarmos essa matrix por ela mesmo temos:

e novamente:

e genéricamente:

Agora o interessante para nós é o comportamento da primeira linha da matriz resultado. Chamando

percebemos que após cada multiplicação K recebe o valor dele mesmo mais o de L enquanto L recebe o antigo valor de K. Esse deslocamento de valores é semelhante (ou igual) ao que acontece com a forma recursiva da função geradora da fórmula de Fibonacci. A mesma análise pode ser feita na linha inferior da matriz. Com isso reduzimos a forma fechada da geração de números via multiplicação de matrizes:

ou seja, basta multiplicarmos a matrix geradora por ela mesmo n vezes que obtemos na segunda coluna da primeira linha o valor equivalente a a fibo(n).

Unindo forças

Agora que vêm a pergunta, seria possível aproveitar a nossa função de potenciação para multiplicarmos a matriz geradora a fim de obter o enésimo valor da sequência de Fibonacci? Bem, a nossa função da forma que ela foi concebida não serve para multiplicar matrizes, pois a multiplicação é feita na forma a*b que não é suportada para matrizes (pelo menos não em Python, que é a linguagem que estamos fazendo nossos exemplos). Porém podemos facilmente modificar nossa função para aceitar como terceiro parâmetro a função que deverá ser aplicado ao elemento a ser multiplicado:

def pow4(b,n,f=lambda x,y:x*y):
  if n==1:
    return b

  if n%2:
    h = pow4(b,(n-1)/2,f)
    return f(f(h,h),b)
  else:
    h = pow4(b,n/2,f)
    return f(h,h)

O bacana é que a nossa função continua funcionando para potenciação de números, basta omitirmos o terceiro parâmetro, passando apenas a base e o expoente à função.

Uma implementação de multiplicação de duas matrizes 2×2 é dada a seguir:

def mult_matrix(ma,mb):
  (a,b),(c,d) = ma
  (e,f),(g,h) = mb
  return [[a*e+b*g,a*f+b*h],[c*e+d*g,c*f+d*h]]

e por seguinte, definimos a nossa matriz geradora:

fib_matrix = [[1,1],[1,0]]

Agora basta encapsularmos a chamada da função que faz a chamada da potenciação para o cálculo:

def fibo3(n):
  if n==0 or n==1:
    return n
  return pow4(fib_matrix, n, mult_matrix)[0][1]

Agora com a nossa terceira implementação aplicamos o ganho de desempenho provido pela nossa implementação de potenciação para gerarmos o enésimo número da sequência de Fibonacci, melhorando a complexidade do método de O(n) [bom] para O(lg n) [melhor]. Essa mescla de técnicas nos traz melhorias significativas, que pode se mostrado na prática nesse caso.

Conclusão

Com um comparativo simples, fazendo n=1.000.000 (um milhão), o cálculo de fibo(n) consumiu :

fibo2	1m53.979s (implementação iterativa)
fibo3	0m23.732s (com potenciação recursiva de matrizes)

Por motivos óbvios a primeira implementação não foi avaliada para um n tão alto poi para testes mais simples, como n=40 foram necessários mais de 1 minuto e meio para se computar. E como o comportamento da primeira implementação é exponencial, ao almentarmos o valor de n para pouco mais de 50 unidades, o tempo de execução do nosso algoritmo explodiria (quem tiver paciência, poderia deixar o algoritimo rodando para n com valores elevados, como 100, 200, etc.)

Pretendo posteriormente fazer um comparativo caso a caso das três implementações, mas acredito que com o que equacionamos (e mostramos na prática) como é possível sempre ganharmos um pouco de desempenho se fugirmos um pouco da solução óbvia, e buscarmos por meio mais eficientes, e mesclarmos técnicas, como o que fizemos aqui nessa ocasião, nos aproveitando do ganho na implementação da potenciação para gerarmos números da sequência de Fibonacci.

Todo o código deste post pode ser enconytrado aqui: gist.github.com/972762

Update: Aqui eu fiz o upload de um arquivo contendo a representação em ASCII do 50.000.000-ésimo número da sequência de fibonacci. O arquivo têm pouco mais de 10MB, e não tem muita utilidade… mas caso vocÊ queira baixar, fique a vontade!