Mais sobre reiteração

A reiteração ou iteração é um dos mais efetivos algoritmos para para processamento de sequências, mas sua eficiência não se limita a processamento de conjuntos prontos, essa técnica de algoritmo também pode ser usada para processamento de amostragens em plena coleta.

Vamos a um algoritmo bem simples, a média aritmética:


O algoritmo reiterativo pode ser expresso da seguinte forma:

(defun mean ((a-list list))
  (/
    (apply #'+ a-list)
    (length a-list)))

Agora imagine que você tem o registro contínuo do comportamento de um dado específico ao longo do tempo e gostaria de manter sua média sem preocupação como os valores em si (acho um caso pouco provável, mas…).

Se reparando bem, há dois dados importantes para o cálculo da média aritmética: a própria média e a quantidade de elementos. Basta que a função receba esses valores além dos novos valores que serão usados para atualizar a média anterior.

Assim é possível armazenar apenas a média atual e a quantidade de elementos avaliados:

(defun update-mean ((the-mean hash-table) (a-list list))
  (let ((*count* (+ (gethash 'count the-mean) (length a-list))))
    (setf (gethash 'mean the-mean)
      (/
        (+
          (apply #'+ a-list)
          (* (gethash 'mean the-mean) (gethash 'count the-mean)))
        *count*))
    (setf (gethash 'count the-mean) *count*)
    the-mean))

Então, além de receber a lista com os dados mais recentes (segundo parâmetro), a função recebe como primeiro parâmetro um hash com os dados de média anteriores.

O formato inicial do hash deve ser:

#s(hash-table :test fasthash-eql (count . 0) (mean . 0))

Ou seja, 'mean zero (0) e 'count zero (0). O hash será atualizado e retornado:

(setq *mean*
  (make-hash-table
    :initial-contents (list
      (cons 'count 0)
      (cons 'mean 0))))

Na próxima falarei em variância on-line.

[]'s
Cacilhas, La Batalema