domingo, 22 de janeiro de 2012

Média harmónica

Poliedro Já que falávamos de variâncias e médias, um dos cálculos mais belos de média é a média harmónica.

Vou roubar
a explicaçãoo exemplo da Wikipédia por pura preguiça… :-/

[update]
Roubar a explicação não… roubei o exemplo. Para a explicação deixei o apontador para o artigo na Wikipédia – mais preguiçoso ainda!
[/update]


Você se lembra do colégio, quando tinha de calcular a velocidade média percorrida por um carro, certo? Imagine que um carro faz uma viagem de x horas, tendo percorrido metade do tempo a 40Km/h e a outra metade a 60Km/h.

Calcular a velocidade média é bem fácil, não?

(40Km/h + 60Km/h) / 2 = 50Km/h


Então o carro percorreu a distância a uma velocidade média de 50Km/h, tornando fácil calcular, por exemplo, a distância: se o carro andou por 3h, percorreu 150Km.

Porém imagine que a proposição do problema não fosse quanto ao tempo, mas quanto à distância…

O carro percorreu metade do percurso (não do tempo) a 40Km/h e outra metade a 60Km/h. Qual a velocidade média?

Para obter esse resultado, precisamos da média harmónica:

2 / ((1 / 40Km/h) + (1 / 60Km/h)) = 48Km/h


Então é o equivalente a percorrer todo o trajeto a 48Km/h.

Isso também se aplica a diversos outros ramos, como a matemática financeira: se um investidor aplica um mesmo valor em compra de ações todos os meses, no final o preço médio das ações será a média harmónica dos preços das ações em cada mês.

Mãos à massa


Conversamos até agora sobre matemática, agora é hora de ver o código! Usarei novamente Scheme.

Vamos nos concentrar primeiro no cálculo do denominador. Novamente apelaremos para map/reduce.

O map será usado para inverter cada um dos elementos, para tanto usaremos a função lambda (λx.(1/x))xi:
(map (lambda (x) (/ 1 x)) *list*)


Feito isso, precisaremos de um somatório desses elementos, portanto usaremos reduce novamente com #'apply e #'+:
(apply +
       (map (lambda (x) (/ 1 x)) *list*))


O numerador é fácil, é a quantidade de elementos, ou tamanho da lista:
(length *list*)


Basta dividirmos um pelo outro e, quase sem querer, já temos o cálculo da média harmónica!
(define harmonic-mean
  (lambda (*list*)
    (/
      (length *list*)
      (apply +
             (map (lambda (x) (/ 1 x)) *list*)))))


Se quiser testar com os valores do exemplo (40Km/h e 60Km/h):
(let ((params '(40 60)))
  (display (harmonic-mean params))
  (newline))


[update]
Ainda esperando o pessoal do Prettify corrigir o syntax highlighting para LISP.
[/update]


[]’s
Cacilhας, La Batalema

segunda-feira, 16 de janeiro de 2012

Dissecando a variância

Paradigma funcional Este artigo dá seguimento ao artigo sobre variância amostral.

A variância pode ser entendida como a média aritmética dos quadrados dos desvios de cada elemento da população.

O desvio de um elemento é a diferença entre o elemento e seu valor esperado. Quando lidamos com um conjunto, o valor esperado é a média dos elementos.

Então o desvio do elemento xi é xi - x.

A variância populacional pode ser descrita como:
σ²x=1/n Σ(xi - xm)


Na maioria dos casos, não se tem disponível todos os elementos de um conjunto, mas apenas uma amostra. Nesses casos, calculamos a variância de amostra ou variância amostral.

A diferença no cálculo é que, em vez de dividirmos pelo número total de elementos da amostra no cálculo da média, dividimos pelo número total menos um, o que aumenta o resultado do desvio padrão, compensando não conhecermos todos os elementos do conjunto.

Então o cálculo muda para:
s²x=1/(n - 1) Σ(xi - xm)


Em Erlang, para calcular o somatório dos desvios, primeiros usamos list comprehension para gerar uma lista dos quadrados desvios:
[math:pow(Xi - Xm, 2) || Xi <- List]


O que este código diz é: retorne a lista dos quadrados (math:pow/2) das diferenças entre cada elemento (Xi) da lista (Xi <- List) e sua média (Xm, calculado anteriormente).

Depois ele usa math:sum/1 para gerar um somatório e retorna a divisão do resultado do somatório pelo tamanho da lista menos um (Num / Demon).

Volte ao artigo anterior para ver como fica o código.

Em Scheme, a lógica é quase a mesma, mas em vez de list comprehension, é usado map/reduce. O #'map roda a função anónima (lambda) em cada elemento, extraindo os quadrados dos desvios.

[update]
Troquei o link para map/reduce, que apontava para um arcabouço do Google, quando as referências reais seriam encontradas no segundo parágrafo do texto referenciado.
[/update]


A função usada foi (λx.(x - x)²)xi, ou: (lambda (x) (expt (- x xm) 2)) em LISP.

Para o reduce (#'apply) é usado somatório (#'+), aplicado ao conjunto resultante.

Novalmente, volte ao artigo anterior para ver o código.

[]’s
Cacilhας, La Batalema

domingo, 15 de janeiro de 2012

Variância

Glider Uma das operações mais importantes e necessárias da matemática é a variância de amostra. É usada, por exemplo, para o cálculo do desvio padrão e da regressão linear.

Usando linguagens funcionais, a implementação fica muito mais elegante.

Erlang


Em Erlang, a função para o cálculo da variância toma o seguinte formato:
variance(List) ->
Xm = mean(List),
Num = lists:sum([math:pow(Xi - Xm, 2) || Xi <- List]),
Denom = length(List) - 1,
Num / Denom.


É preciso ainda definir a função de média, mean/1:
mean(List) ->
lists:sum(List) / length(List).


LISP


Em Scheme a implementação é um pouco mais verbosa, mas ainda assim elegante.

Segue o código em R⁵RS:
(define variance
(lambda (*list*)
(let ((xm (mean *list*)))
(/
(apply +
(map (lambda (x) (expt (- x xm) 2)) *list*))
(- (length *list*) 1)))))


Também precisamos implementar a média:
(define mean
(lambda (*list*)
(/
(apply + *list*)
(length *list*))))


Paradigma imperativo


Para comparação, segue a implementação de variância em uma linguagem imperativa, C:
double variance(int length, double *list) {
double x_mean = mean(length, list);
double sum = 0;
int i;

for (i=0; i<length; ++i)
sum += pow(list[i] - x_mean, 2.);

return sum / (length - 1);
}


É preciso incluir o cabeçalho math.h. Segue a implementação da função mean():
double mean(int length, double *list) {
double sum = 0;
int i;

for (i=0; i<length; ++i)
sum += list[i];

return sum / length;
}


Perceba a mudança de estado, o que não ocorre nos códigos funcionais.

Escolhi C em vez de Python, porque Python também suporta bem o paradigma funcional, enquanto C é quase necessariamente imperativa.

[]’s
Cacilhας, La Batalema