domingo, 29 de junho de 2008

Embaralhando palavras

Squeak Outro dia o Walter estava falando sobre um comportamento irregular da implementação de expressões regulares em Python, especificamente o token \b.

Havia uma brincadeira em Ruby com regex que seleciona cada palavra em uma frase e embaralha a ordem das letras, mantendo a primeira e a última em seus lugares.

Para separar as palavras e os elementos de espaçamento entre elas, usava-se uma regex com \b. Resolvi fazer a brincadeira em Smalltalk, mas descobri que o token também não funciona, portanto precisei fazer uma expressão que representasse cada bloco: ((\w+)|(\W+)).

Para reproduzir essa brincadeira, usando Squeak, primeiro usando o System Browser crie um método shaked na categoria copying da classe String:
shaked
| aux fst i lst temp |

(self size <= 3) ifTrue: [ ↑ self copy ].

fst := (self byteAt: 1) asCharacter asString.
lst := (self byteAt: self size) asCharacter asString.
aux := self copyFrom: 2 to: self size - 1.
temp := Array new: aux size factorial.

i := 0.
aux permutationsDo: [ :s |
i := i + 1.
temp at: i put: (fst, s, lst).
].

↑ temp at: temp size atRandom.


Agora, em um workspace, execute o seguinte código:
| phr |

" Esta é a frase a ser embaralhada "
phr := 'Kodumaro: as sombras da programação'.

Transcript open.
phr regex: '((\w+)|(\W+))' matchesDo: [ :s |
Transcript show: s shaked.
].

Transcript cr.


Selecione tudo (M-a) e execute (M-d).

[]'s
Cacilhas, La Batalema

quarta-feira, 11 de junho de 2008

Cálculos estatísticos: polinómio de Lagrange

Paradigma funcional Dando sequência aos artigos sobre cálculos estatísticos no Kodumaro – e em outros blogs amigos –, tive a ideia de falar sobre interpolação polinomial.

Por ser um método simples, decidi usar o polinómio de Lagrange:
y=\sum_{i=0}^{n-1}\Big(y_i\prod_{j=0\\j\neq i}^{n-1}\frac{x-x_j}{x_i-x_j}\Big)

Não é preciso calcular os coeficientes – é possível simplificar o cálculo final transformando parte do polinómio em um vetor de coeficientes, mas é mais fácil de visualizar sem fazê-lo.

C++


Dessa vez não vou usar C, mas C++, para poder usar recursos de orientação a objetos, como encapsulamento.

Primeiro vamos criar um namespace kodumaro e uma classe Lagrange. Abra o arquivo lagrange.h:
#ifndef LAGRANGE_H_
#define LAGRANGE_H_

namespace kodumaro {
class Lagrange {
public:
Lagrange(const double *, const double *, int);
~Lagrange() {}

double getY(double);

private:
const double *vector_x;
const double *vector_y;
int length;
};
}

#endif /*LAGRANGE_H_*/


O construtor irá receber um vetor de abscissas, um vetor de ordenadas e o tamanho dos vetores. Esses vetores representarão as coordenadas dos pontos a serem interpolados.

O método getY() retornará a ordenada para uma determinada abscissa, de acordo com a interpolação de Lagrange.

Agora o arquivo lagrange.cc contendo a implementação dos métodos:
#include "lagrange.h"

using namespace kodumaro;

Lagrange::Lagrange(const double *vx, const double vy, int len):
vector_x(vx), vetory(vy), length(len) {}

double Lagrange::getY(double x) {
double y = 0;

for (int i = 0; i < length; ++i) { // ciclo do somatório
double aux = vector_y[i];
for (int j = 0; j < length; ++j) // ciclo do produtório
if (i != j)
aux *= (x - vector_x[j]) / (vector_x[i] - vector_x[j]);
y += aux;
}

return y;
}


E está pronto! Basta incluir lagrange.h e compilar lagrange.cc junto com seu código teste.

O uso é simples:
kodumaro::Lagrange lagr(vx, vy, len);
y = lagr.getY(x);


Common Lisp


Não seria legal fazer isso sem usar uma linguagem funcional. =)

Também vamos aproveitar orientação a objetos – sim! É possível combinar orientação a objetos e programação funcional – para guardar nossos dados.

A classe será similar à de C++, mas o atributo será uma lista de pares de coordenadas:
(defclass lagrange ()
((pairs :initarg :pairs :accessor lagrange-pairs)))


Agora o método para calcular a ordenada em relação a uma abscissa:
(defmethod lagrange-get-y ((a-lagrange lagrange) x)
(reduce '+
(loop
for '(xi . yi) in (lagrange-pairs a-lagrange)
for i from 0
collect (* yi (reduce '*
(loop
for '(xj . yj) in (lagrange-pairs a-lagrange)
for j from 0
collect (if (= i j)
1
(/ (- x xj) (- xi xj)))))))))


A relação entre esse código e a expressão matemática acima é praticamente 1:1.

O uso é:
(let ((a-lagrange (make-instance 'lagrange :pairs coordinates)))
(setq y (lagrange-get-y a-lagrange x)))


Smalltalk


Se foi legal usar orientação a objetos numa linguagem onde a orientação foi costurada como em uma colcha de retalhos e em uma linguagem funcional, imaginem em uma linguagem realmente orientada a objetos!

Smalltalk é uma das linguagens mãe da orientação a objetos: criada antes de C a partir de Simula, é praticamente a linguagem que define os conceitos de orientação a objetos.

Como já disse antes, tornei-me fã do Squeak, devido a sua aplicabilidade educacional e ao XO.

No Squeak, abra o System Browser, se não houver um pacote Kodumaro crie-o e, dentro dele, uma categoria Kodumaro-Interpolation.

Na categoria, crie um classe:
PointArray subclass: #Lagrange
instanceVariableNames = ''
classVariableNames = ''
poolDictionaries: ''
category: 'Kodumaro-Interpolation'


Agora crie o método para calcular a ordenada para uma abscissa:
getY: x
| y |

y := 0.
1 to: self size do: [ :i | | aux |
aux := (self at: i) y.
1 to: self size do: [ :j |
(i ~= j) ifTrue: [
aux := aux * (
(x - (self at: j) x)
/
((self at: i) x - (self at: j) x)
)
]
].
y := y + aux.
].

↑ y


E pronto! Você pode testar instanciando Lagrange – o método new: recebe o tamanho do vetor como parâmetro – e passando a mensagem getY:.

Io


Io é uma linguagem prototipada baseada principalmente em Self e Lua, mas também em outras, como Smalltalk e Lisp.

O código Io pode ser:
Point := Object clone do(
x := 0
y := 0
)

Lagrange := List clone do(
// Gostei da ideia desse método add
add := method(sx, sy,
p := Point clone
p x = sx
p y = sy
append(p)
)

getY := method(x,
y := 0
for(i, 0, size - 1,
aux := at(i) y
for(j, 0, size - 1,
// Havia feito diferente antes,
// mas acho o if assim mais claro:
if(i != j) then(
aux = aux * ( \
(x - at(j) x) \
/ \
(at(i) x - at(j) x) \
)
)
)
y = y + aux
)
return y
)
)


Vou dar um exemplo de código pois, devido a ser uma linguagem recente, não há muita documentação.

Digamos que você salvou o código acima no arquivo lagrange.io:
Io> Importer FileImporter import("lagrange")
Io> v := Lagrange clone
Io> v add(1, 10)
Io> v add(2, 100)
Io> v add(3, 1000)
Io> v getY(2)
==> 100
Io> v getY(2.5)
==> 448.75


Conclusão


Bem, desta vez deixo a conclusão ao leitor e convido a quem quiser fazer também suas implementações.

Outro método muito interessante é o polinómio de Newton.

[]'s
Cacilhas, La Batalema

sábado, 7 de junho de 2008

Variância em Smalltalk

Squeak Já que o artigo sobre variância rendeu outro artigo interessante, me empolguei e resolvi escrever como implementar o cálculo da variância em Smalltalk.

Como gostei muito da ferramenta e para privilegiar seu foco educacional, vou usar o Squeak.

Abra o System Browser e, se não tiver o pacote Kodumaro, crie-o. Crie então a categoria Kodumaro-Variance.

Crie então a seguinte classe:
FloatArray subclass: #VariantiableArray
instanceVariableNames: ''
classVariableNames: ''
poolDictionaries: ''
category: 'Kodumaro-Variance'


Agora os métodos…

Na categoria math functions, crie o método rms:
rms
"Calculates and returns the root mean square"
| aux |

aux := 0.
self do: [ :e |
aux := aux + (e * e)
].

↑ (aux / self size) sqrt


É claro que poderíamos criar um método para retornar o numerador do cálculo, mas vou fazer diferente. =)

Vamos implementar a variância populacional com média aritmética – average, herdado de Collection, já que costuma ser um valor mais redondo – e a variância da amostra com média quadrada, ambas também na categoria math functions.
populationalVariance
"Calculates and returns the populational variance"
| aux mean |

aux := 0.
mean := self average.

self do: [ :e | | temp |
temp := e - mean.
aux := aux + (temp * temp).
].

↑ aux / self size


Agora a variância amostral:
sampleVariance
"Calculates and returns the sample variance"
| aux mean |

aux := 0.
mean := self rms.

self do: [ :e | | temp |
temp := e - mean.
aux := aux + (temp * temp).
].

↑ aux / (self size - 1)


Está pronto!

Como assim? Só isso?

É, só isso. =)

Vamos testar, abra um Workspace e digite:
| v |

v := VariantiableArray newFrom: #(1 2 3 4 5).

Transcript
open;
show: 'Média aritmética: ', v average printString; cr;
show: 'Média quadrada: ', v rms printString; cr;
show: 'Variância populacional: ', v populationalVariance printString; cr;
show: 'Variância da amostra: ', v sampleVariance printString; cr.


Pressione M-a M-d para executar.

[]'s
Cacilhas, La Batalema

terça-feira, 3 de junho de 2008

Habilitando XML em Io

VisualWorks É extremamente frustrante instalar Io e descobrir que os recursos de XML não funcionam!

Mas existe solução. ;)

Você vai primeiro no Hick.org e baixa a libsgml – estou usando a versão 1.1.4.

Descompacte, configure e compile:
bash$ tar xzvf libsgml-*.tar.gz
bash$ cd libsgml-*/
bash$ ./configure
bash$ make


Antes de instalar, edite o Makefile, identifique a seguinte linha:
install -m 644 -o root -g root --directory /usr/local/include/sgml


E substitua-a pelo seguinte:
install -o root -g root --directory /usr/local/include/sgml
install -m 644 -o root -g root include/Variant.h \
/usr/local/include/sgml/Variant.h


Não esqueça de respeitar a indentação!

Feito isso, pode instalar:
bash$ sudo make install


Agora recompile e reinstale seu pacote Io.

Para testar:
bash$ io
Io 20080120
Io> SGML
Io> xml := URL with("http://kodumaro.blogspot.com/") fetch asXML
Io> links := xml elementsWithName("a") map(attributes at("href"))
Io> links foreach(link, link println)


Referência: Io Programming Guide.

[]'s
Cacilhas, La Batalema

segunda-feira, 2 de junho de 2008

Potências ótimas

Peço desculpas antecipadamente por fazer uma postagem fazendo propaganda de um artigo alheio. =)

Convido todos a darem uma olhada atenta no artigo potências ótimas no Brain Dump.

O autor comenta sobre técnicas de cálculo de potência usadas em C/C++.

Boa leitura!

[]'s
Cacilhas, La Batalema

domingo, 1 de junho de 2008

Cálculo da variância com linguagem funcional

Paradigma funcional A implementação de cálculos básicos de estatística em linguagens funcionais é tremendamente mais simples do que usando linguagens imperativas, como a tradicional C, muito usada devido a sua abstração matemática¹.

Escolhi como exemplo o cálculo da variância, que determina o grau de dispersão dos elementos de um conjunto ou vetor.

Para o cálculo da variância é preciso calcular a média dos elementos do vetor.

Média


Em quase todos os textos que li sobre variância, covariância e outras operações estastísticas, é aconselhado usar a média quadrada dos elementos, mas meu professor de estatística diz pra usar a média aritmética.

Então vamos implementar as duas.

Média aritmética


Média aritmética consiste no somatório de todos os elementos dividido pelo número de elementos.

Em C a implementação é:
double arithmetic_mean(double *v, int len) {
double sum = 0;
int i;
for (i = 0; i < len; ++i)
sum += v[i];
return sum / len;
}


Em Common Lisp o mesmo algoritmo é implementado assim:
(defun arithmetic-mean (a-list)
(/ (reduce '+ a-list) (length a-list)))


Desconsiderando a implementação em duas linhas contra seis ou sete em C, podemos citar algumas vantagens:
  1. Em C é preciso informar o tamanho do vetor, enquanto em Common Lisp não – em C++ usando STL também não seria necessário.
  2. Em C usamos diversar variáveis que mudam de estado em ciclos. Em Common Lisp usamos funções e retornos, numa relação 1:1 com a Matemática – por exemplo, Σx vira (reduce '+ x).
  3. Realmente… duas linhas em Lisp contra seis ou sete em C. =)


Média quadrada


Média quadrada ou RMS consiste na raiz quadrado da razão do somatório dos quadrados dos elementos pela quantidade:
double root_mean_square(double *v, int len) {
double sum = 0;
int i;
for (int i = 0; i < len; ++i)
sum += v[i] * v[i];
return sqrt(sum / len);
}


Observação: para usar sqrt() é preciso incluir o cabeçalho math.h.

Agora vamos fazer a mesma coisa em Common Lisp:
(defun root-mean-square (a-list)
(sqrt
(/
(reduce '+ (mapcar (lambda (e) (* e e)) a-list))
(length a-list))))


[update 2008-06-14]O código acima foi alterado segundo a sugestão do Pedro – veja comentários abaixo.[/update]


Esse ficou maiorzinho, no entanto mantém uma relação muito mais próxima com a expressão matemática do que C. No caso o form loop criou um novo vetor contendo os quadrados dos elementos, que foi reduzido por reduce e '+ – Σ.

Escolhendo uma média


Se você escolher a média aritmética, faça:
#define mean(v, len) arithmetic_mean(v, len)


Em Lisp:
(defun mean (a-list)
(arithmetic-mean a-list))


E se escolher média quadrada:
#define mean(v, len) root_mean_square(v, len)

(defun mean (a-list)
(root-mean-square a-list))


Numerador da variância


Há dois tipos de variância: populacional e da amostra. O cálculo é similar, mudando apenas o denominador. Portanto vamos calcular primeiro o numerador, idêntico para os dois tipos de variância.

Em C, o cálculo do numerador é:
double varnum(double *v, int len) {
double mean_x = mean(v, len);
double sum = 0;
int i;
for (i = 0; i < len; ++i)
sum += pow(v[i] - mean_x, 2.);
return sum;
}


Observação: para usar pow() é preciso incluir o cabeçalho math.h.

Agora em Common Lisp:
(defun var-num (a-list)
(reduce #'+
(mapcar (lambda (e) (expt (- e (mean a-list)) 2)) a-list)))


[update 2008-06-14]O código acima foi alterado segundo a sugestão do Pedro – veja comentários abaixo.[/update]


É claro, para quem está acostumado a ver códigos e mais códigos em linguagens derivadas de C o código em Lisp pode parecer confuso, mas se você for tentar explicar a um matemático sem conhecimento de C, verá que programação funcional se encaixa melhor à Matemática pura.

Variância populacional


A variância populacional consiste na razão do numerador calculado pela quantidade de elementos e é usada quando o vetor representa todos os elementos do universo desejado.
double populational_variance(double *v, int len) {
return varnum(v, len) / len;
}


Em Common Lisp:
(defun populational-variance (a-list)
(/ (var-num a-list) (length a-list)))


Variância da amostra


A variância da amostra consiste na razão do numerador calculado pela quantidade de elementos menos um e é usada quando o vetor representa apenas uma amostragem do universo desejado.
double sample_variance(double *v, int len) {
return varnum(v, len) / (len - 1);
}


Em Common Lisp:
(defun sample-variance (a-list)
(/ (var-num a-list) (-(length a-list) 1)))


Conclusão


Para operações estatísticas ou puramente matemáticas, linguagens funcionais podem ser uma alternativa mais eficiente do que linguagens imperativas.

[update 2008-06-07]Versão em Ruby pelo Tiago no Programando sem cafeína![/update]
[update 2008-06-10]Versão em Python pelo LKRaider no LKVenia! =)[/update]


[]'s
Cacilhas, La Batalema

¹Abstração matemática: quis dizer abstração de alto nível em busca de uma representação mais matemática.