Grupo de Estudos em Haskell da UFABC > Estruturas de Dados Puramente Funcionais > Análise Amortizada

Análise Amortizada

Playlists

Desta aula: …
Do curso: https://www.youtube.com/playlist?list=PLYItvall0TqJ25sVTLcMhxsE0Hci58mpQ

1 Análise amortizada

Figuras: trinityscsp e Wikipedia

A análise do odômetro binário é muito parecida com o decimal.

Pode ser visto como uma série de incrementos sucessivos.
Cada mudança de dígito tem um custo real que vamos convencionar como sendo $1$ .

Figura: [CLRS]

Note que o custo acumulado nunca é maior que o dobro de operações.
Poderíamos até considerar que sendo o contador de $k$ bits, o custo por incremento será $O (k)$ e para uma sequência de $n$ incrementos, será $O (n k)$ .
O problema é que estamos exagerando, a maior parte das operações nem toca em todos os bits!

O bit 0 é modificado a cada incremento
O bit 1 é modificado a cada 2 incrementos
O bit 2 é modificado a cada 4 incrementos
…

Logo para uma sequência de $n$ ( $n \leq 2^{k}$ ) incrementos (com o contador a partir do $0$ ) o total de modificações é:

$\sum_{i = 0}^{⌊ \lg n ⌋} ⌊ \frac{n}{2^{i}} ⌋ < n \sum_{i = 0}^{\infty} \frac{1}{2^{i}} = 2 n$

1.1 Análise amortizada

A noção da análise amortizada vem da seguinte observação:
- Dada uma sequência de operações, estamos interessados no tempo total de execução da sequência e não de cada operação individualmente.
Em outras palavras, queremos que a execução da sequência toda de $n$ operações seja, por exemplo, $O (n)$ mas não nos importamos se alguma das operações não for $O (1)$ .
Em outras palavras, o custo médio de cada operação e, portanto, o custo amortizado de cada operação é $O (1)$ .

1.2 Revisitando filas

Há dois métodos consagrados para a análise amortizada:
- O método do banqueiro ou de contabilidade;
- O método do físico ou potencial.

Vamos apresentar uma estrutura de dados para filas e exemplificar como podemos empregar o método do banqueiro¹.

A implementação funcional mais comum de filas envolve o uso de duas listas f e r.

f contém os elementos no início (front) da fila
- Mantém os elementos na mesma ordem da fila
r contém os elementos do final (rear) da fila
- Mantém os elementos na ordem inversa da fila

--              f    r
type Fila a = ([a], [a])

A cabeça da lista está localizada em f, então tanto a função head quanto a função tail operam neste ponto

head :: Fila a -> a
head (x:f, r) = x

tail :: Fila a -> Fila a
tail (x:f, r) = (f, r)

De maneira semelhante, o último elemento da fila é o primeiro elemento de r, logo snoc² simplesmente adiciona um elemento à r.

snoc :: Fila a -> a -> Fila a
snoc (f, r) x = (f, x : r)

1.3 O invariante

Elementos são adicionados em r e retirados de f.
Assim, em algum momento eles tem que ser migrados.
Faremos a migração se após uma operação houver ao menos um elemento na fila mas f estiver vazio (ou seja, há elementos em r).
O objetivo é manter o seguinte invariante: f estará vazio se e somente se r também estiver vazio (ou seja, a fila toda está vazia).
- Note que se isso não fosse verdade, se f estivesse vazio e r não, então o primeiro elemento da fila seria o último elemento de r (acesso em tempo $O (n)$ ).
- Este invariante garante que head (e tail) sempre rodam em tempo $O (1)$ .

Mantendo o invariante

Para isso precisaremos adaptar as funções que alteram a fila (tail e snoc). Vamos usar uma função auxiliar que faz o trabalho:

check :: Fila a -> Fila a
check ([], r) = (rev r, [])
check q = q

snoc :: Fila a -> a -> Fila a
snoc (f, r) x = checkf (f, x : r)

tail :: Fila a -> Fila a
tail (x:f, r) = checkf (f, r)

1.4 O método do Banqueiro

Para provar um limite amortizado, é preciso definir o custo amortizado de cada operação e provar que, para qualquer sequência de operações, o custo total amortizado das operações é um limite superior no custo total real.

$\sum_{i = 1}^{n} a_{i} \geq \sum_{i = 1}^{n} t_{i}$

Onde $a_{i}$ é o custo amortizado da operação $i$ , $t_{i}$ é o custo real da operação $i$ e $n$ é o número total de operações.

Na verdade na prática acabamos quase sempre provando algo mais forte que é:

$\sum_{i = 1}^{j} a_{i} \geq \sum_{i = 1}^{j} t_{j}$

Onde $j \leq n$ indica que a qualquer momento a soma das operações amortizadas é um limite superior ao custo real acumulado.

Poupança

A diferença entre o custo amortizado total acumulado e o custo real total acumulado é chamado de poupança acumulada (en: accumulated savings).
Ocasionalmente o custo de uma operação vai ser maior que o seu custo amortizado. Neste caso, retiramos a diferença da poupança.
- Tais operações são denominadas caras (en: expensive).
- As que tem custo real igual ou inferior ao amortizado são chamadas de baratas (en: cheap).
A chave é mostrar que operações caras só ocorrem quando a diferença do custo pode ser paga pela poupança!

Créditos

O método do banqueiro associa créditos a cada elemento/posição da estrutura de dados.
Quando essas posições forem acessadas, esses créditos pagarão a diferença no custo.

Invariante

Todo crédito precisa ser alocado antes de ser usado e nenhum crédito pode ser usado mais de uma vez!
Normalmente para usar o método do banqueiro, define-se um invariante que garante que quando uma operação cara ocorrer então, há dinheiro suficiente na poupança para cobrir o custo.

1.5 O método do Banqueiro e a Fila

head tem custo amortizado 1 (e real também!)
snoc
- O invariante para a nossa análise é de que cada elemento em r está associado com $1$ crédito.
- Quando ocorre um snoc, gastamos um crédito para colocar o elemento em r e outro para deixar associado ao elemento propriamente dito.
  - Assim, uma lista r com $n$ elementos tem $n$ créditos associados.
  - O custo amortizado de uma operação snoc é portanto $2$

tail
- Se tail não precisar inverter a lista, ele custa 1 crédito
- Se tail precisar inverter a lista, ele precisará fazer $n + 1$ passos, onde $n$ é o tamanho da lista.
  - A poupança neste caso tem $n$ créditos
  - Após a execução de tail, a poupança estará vazia e tail terá tido um custo amortizado de $1$ ( $n + 1 - n = 1$ )

Logo, como todas as operações têm custo amortizado $\leq 2$ , então qualquer sequência com $n$ operações terá custo amortizado $\leq 2 n = O (n)$ .

Não mostramos diretamente, mas é fácil mostrar que de fato $\sum_{i = 1}^{j} a_{i} \geq \sum_{i = 1}^{j}$ vale.

1.6 Revisitando os Heaps Binomiais

Mostramos que a inserção em heaps binomiais leva tempo $O (\lg n)$ .
É possível mostrar que a inserção leva tempo $O (1)$ amortizado
Lembre-se do odômetro!
- O número de árvores no heap é equivalente ao número de $1 s$ na sua representação em binário
- Inserção precisa de $k + 1$ passos onde $k$ é o número de chamadas a função link.
- Se mantivermos um crédito por árvore, o custo amortizado de insert (descontados os créditos da poupança) passa a ser O(1).

2 Referências

2.1 Livros

[CO]
Purely Functional Data Structures
- Por Chris Okasaki

[CLRS]
Introduction to Algorithms
- Por Thomas H. Cormen & Charles E. Leiserson & Ronald L. Rives/t & /Clifford Stein

3 Disclaimer

Estes slides foram preparados para os cursos de Paradigmas de Programação e Desenvolvimento Orientado a Tipos na UFABC.

Este material pode ser usado livremente desde que sejam mantidos, além deste aviso, os créditos aos autores e instituições.

Os método do banqueiro e do físico são equivalentes, mas por motivos de tempo nos concentraremos aqui apenas no método do banqueiro. Caso queira saber mais sobre o método cheque os livros [CO] e [CLRS]. Para a mesma demonstração que fazemos aqui para filas veja o capítulo 5 de [CO]. ↩︎
snoc vem de cons na ordem inversa. Ninguém sabe exatamente quando isso surgiu, mas há papers da década de 70 que já usam essa nomenclatura. ↩︎