Tabelas dinâmicas

Muitos algoritmos empregam tabelas para armazenar dados durante o processamento. Em geral, o tamanho da tabela depende dos dados de entrada. Mas muitas vezes é impossível prever o tamanho da tabela no início da execução do algoritmo. Nesses casos, podemos recorrer a uma tabela que incha e encolhe, conforme a necessidade, ao longo da execução do algoritmo.

Esta página trata de algoritmos de manipulação de tabelas dinâmicas, com foco no consumo de tempo amortizado desses algoritmos. A página é inspirada na seção 17.4 de CLRS.

Introdução

Nesta página, as tabelas serão representadas por vetores. Uma tabela dinâmica (= dynamic table = unboundbed array) é uma vetor, digamos A[1.. m .. t], sujeito a expansões e contrações. As primeiras m posições do vetor estão ocupados com dados relevantes e as demais estão livres. Diremos que m é a carga (= load) da tabela e t é o tamanho (= size) da tabela. É claro que m ≤ t. Se m = 0, diremos que a tabela está vazia. Se m = t, a tabela está cheia.

1 m t
11 22 33 44 55 66 77 88 99

Para expandir a tabela, multiplicaremos o tamanho t por 2. Para contrair a tabela, dividiremos o tamanho t por 2. Adotada essa política, é natural supor que t é uma potência de 2, ou seja, que t = 2p para algum número natural p (e portanto t ≥ 1).

Tabela sujeita a inserções

Considere o comportamento da tabela A[1.. m .. t] submetida à operação de inserção de um novo objeto. (Imagine, por exemplo, que dados estão sendo lidos de um arquivo de tamanho desconhecido.) Se a tabela já estiver cheia, será necessário expandi-la antes de fazer a inserção.

Se t ≥ 1, a operação de inserção de um objeto a na posição m+1 da tabela pode ser descrita assim:

Insira-na-Tabela ( a)   t ≥ 1
1 . se m = t
2 .ooo então B := Aloque-Tabela ( 2 t)
3 .ooo então para k de 1 até m faça
4 .oooooo então B[k] := A[k]
5 .ooo então Desaloque-Tabela ( A)
6 .ooo então A := B
7 .ooo então t := 2 t
8 . m := m + 1
9 . A[m] := a

A linha 2 aloca uma nova tabela de tamanho 2t. As linhas 2 a 7 produzem uma expansão da tabela; as linhas 3 e 4, em particular, realocam A[1 .. m] para B[1 .. m]. Na linha 5, o espaço ocupado pela tabela original é liberado. Na linha 6, a nova tabela B substitui a tabela original.

Observe que A, t e m não aparecem na lista de parâmetros de Insira-na-Tabela. Essas três variáveis são consideradas globais. Além disso, você deve imaginar que A é uma referência à tabela (ou seja, um ponteiro para o vetor que armazena a tabela).

Consumo amortizado de tempo

É evidente que cada execução de Insira-na-Tabela consome Ο(1) unidades de tempo no melhor caso (isto é, quando m < t), e Ο(m) unidades de tempo no pior caso (isto é, quando m = t). Mas o consumo de tempo de uma execução isolada de Insira-na-Tabela é menos relevante que o consumo de tempo de uma sequência de execuções de Insira-na-Tabela, com cada execução trabalhando sobre a tabela produzida pela execução anterior:

20 . A := Aloque-Tabela (1)
21 . leia a
22 . A[1] := a
23 . m := t := 1
24 . para i de 1 até n faça
25 .ooo leia a
26 .ooo Insira-na-Tabela ( a)

(Por que a primeira inserção, nas linhas 21 a 23, foi feita em separado, antes do processo iterativo? Apenas porque assim os cálculos a seguir ficam mais limpos.)  No início de cada iteração (linha 25), o valor de t é uma potência de 2 e

t/2 < mt.

Para estimar o consumo de tempo da sequência de n inserções (linhas 24 a 26) usaremos o seguinte truque. Suporemos que cada execução de uma instrução do tipo A[*] := * ou B[*] := * (linhas 4 e 9 de Insira-na-Tabela) custa 1 moeda e calcularemos o custo total das n inserções. Não é difícil entender que esse custo em moedas será proporcional ao consumo de tempo das n inserções.

Algumas inserções são baratas e outras são caras. Se m < t, a inserção custa apenas 1 moeda. Se m = t, a inserção custa m+1 moedas. Qual é, então, o custo total das n inserções?

Para fazer os cálculos, usaremos o seguinte protocolo de pagamentos adiantados. Antes de cada inserção (início da linha 26) faremos um pagamento de 3 moedas. Na maioria das vezes, apenas uma dessas moedas será usada para pagar pela inserção; as moedas restantes formarão uma poupança, que usaremos para pagar pelas inserções caras no futuro. Não é difícil constatar que no início de cada iteração (linha 25) a poupança terá

pelo menos 2m − t moedas.

Como m > t/2 no começo de cada iteração, a poupança é suficiente para pagar por uma inserção barata. Agora considere uma inserção cara. Imediatamente antes de uma tal inserção temos m = t e portanto a poupança tem pelo menos m moedas. Essa quantia, somada às 3 moedas que recebemos ao começar a inserção, é suficiente para pagar o custo m+1 da inserção. Isso mostra que nosso protocolo de pagamentos adiantados garante o custeio das n inserções. Portanto, o custo total das n inserções não passa de

3 n moedas.

Podemos dizer então que cada execução de Insira-na-Tabela custa 3 moedas no sentido amortizado(A explicação intuitiva para as 3 moedas é a seguinte: a primeira das três moedas é usada para pagar a atribuição A[m] := a na linha 9; a segunda moeda será usada futuramente para pagar pela realocação de A[m] na linha 4; e a terceira será usada futuramente para pagar pela realocação de algum dos elementos de A[1 .. m−1].)  Tudo se passa como se o custo de uma execução de Insira-na-Tabela fosse sempre o mesmo, quaisquer que sejam m e t.

Esse resultado pode ser reformulado em termos de consumo de tempo: cada execução de Insira-na-Tabela consome Ο(1) unidades de tempo no sentido amortizado. Tudo se passa como se o consumo de tempo fosse independente da carga e do tamanho da tabela.

Exercícios 1

  1. O algoritmo Insira-na-Tabela funciona corretamente se t não for uma potência de 2?
  2. Suponha que t ≥ 1 e t/2 < mt quando Insira-na-Tabela é invocado. Mostre que t/2 < mt no fim da execução de Insira-na-Tabela.
  3. Mostre que no início de cada iteração (linha 25) a poupança tem pelo menos 2mt moedas.  [Solução]
  4. Mostre que no início de cada execução da linha 24 temos t = 2p para algum número natural p ≥ 0.
  5. Troque 2t por t+10 nas linhas 2 e 7 de Insira-na-Tabela. Qual o consumo de tempo do fragmento de código nas linhas 24 a 26?
  6. Troque 2t por 3t nas linhas 2 e 7 de Insira-na-Tabela. Qual o consumo de tempo do fragmento de código nas linhas 24 a 26?
  7. ★ Considere o algoritmo Insira-na-Tabela. Qual a diferença entre consumo médio de tempo e consumo amortizado de tempo?

Tabela sujeita a inserções e remoções

Como a tabela dinâmica A[1.. m .. t] se comporta sob a operação de remoção (= deletion)?  A operação consiste em remover da tabela o elemento que está na posição m e contrair a tabela se o novo valor de m ficar muito menor que t. A contração da tabela consistirá em reduzir o tamanho da tabela à metade.

A primeira ideia que vem à mente é contrair a tabela se m ficar menor que t/2. Feito isso, a tabela estaria cheia ou quase cheia. Se acontecer uma inserção logo em seguida, a contração seria desfeita por uma expansão. Essas idas e voltas tornariam a tabela muito ineficiente. Portanto, a ideia de usar t/2 como limiar não é boa.

Adotaremos t/4 como limiar: a tabela será contraída à metade se m ficar menor que ou igual a t/4 depois da remoção. A operação de remoção pode então ser descrita como segue:

Remova-da-Tabela ( )
11 . a := A[m]
12 . m := m − 1
13 . se mt/4
14 .ooo então B := Aloque-Tabela (t/2)
15 .ooo então para k de 1 até m faça
16 .oooooo então B[k] := A[k]
17 .ooo então Desaloque-Tabela (A)
18 .ooo então A := B
19 .ooo então t := t/2
10 . devolva a

Vamos supor que Remova-da-Tabela só é invocado se t = 2p para algum número natural p ≥ 1. Desse modo, t/2 é inteiro e t/4 é inteiro exceto no caso extremo em que t = 2. Vamos supor também que

m > t/4 

(donde m ≥ 1) sempre que Remova-da-Tabela é invocado. Graças a estas condições, no fim da execução de Remova-da-Tabela a propriedade m > t/4 continua valendo com os novos valores de mt, exceto no caso extremo em que m = 0.

Consumo amortizado de tempo

Suponha que a tabela A[1.. m .. t] é submetida a uma sequência arbitrária de inserções e remoções. Para ser mais concreto, considere o seguinte processo iterativo em que cada iteração consiste em uma inserção ou uma remoção.

31 . para i de 1 até n faça
32 .ooo se L = true
33 .oooooo então a := Remova-da-Tabela ( )
34 .oooooo então imprima a
35 .oooooo senão leia a
36 .oooooo senão Insira-na-Tabela (a)

Na linha 32, L é alguma condição booleana. Vamos supor que m ≥ 1 sempre que L = true, de modo que a remoção faça sentido.

Para simplificar os cálculos, suporemos que no início da primeira iteração temos t = 2p para algum número natural p ≥ 1 e

t/4 < mt.

Essas condições também valerão no início das iterações subsequentes enquanto L = true implicar em m ≥ 2.

1 t/4 m t
11 22 33 44 55 66 77 88 99 88

Para estimar o consumo de tempo da sequência de n operações de inserção e remoção usaremos o truque que já empregamos acima. Vamos supor que cada execução de uma instrução do tipo A[*] := *, B[*] := *, ou * := A[*] (linhas 4 e 9 de Insira-na-Tabela e linhas 1 e 6 de Remove-da-Tabela) custa 1 moeda. Adotada essa convenção, vamos calcular o custo total da execução do bloco de linhas 31 a 36. Não é difícil entender que esse custo em moedas será proporcional ao consumo de tempo das n operações.

Dependendo das condições, uma operação pode ser barata ou cara. Se t/4 + 1 < m < t, qualquer operação custa 1 moeda. Se m = t, uma inserção custa m+1 moedas mas uma remoção custa 1 moeda. Se t/4 + 1 = m, uma remoção custa m moedas enquanto uma inserção custa 1 moeda. Qual o custo total das n operações (linhas 32 a 36)?

Para fazer a contabilidade, usaremos o protocolo de pagamentos adiantados. Antes de cada remoção (início da linha 33), faremos um pagamento adiantado de 3 moedas. Da mesma forma, antes de cada inserção (início da linha 36), faremos um pagamento adiantado de 3 moedas. Em geral, apenas uma das moedas será usada para pagar pela operação, sendo as moedas restantes acrescentadas a uma poupança. Não é difícil constatar que no início de cada iteração (linha 25) a poupança terá pelo menos

Observe que a poupança nunca é negativa.

Se t vale 2 ou 4, é fácil verificar que essa poupança, junto com as 3 moedas, é suficiente para pagar por qualquer das operações. Suponha então, daqui em diante, que t ≥ 8 e portanto t/4 + 1 < t/2 < t.

Considere incialmente as iterações em que a operação é de inserção. Se m = t então a poupança de m moedas, somada com as 3 moedas, é suficiente para pagar pela inserção, pois esta custa m+1 moedas. Se m < t então as 3 moedas são suficientes pagar pela inserção, pois esta custa 1 moeda.

Agora considere as iterações em que a operação é de remoção. Se t/4 + 1 < m, então as 3 moedas são suficentes para pagar pela remoção, pois esta custa 1 moeda. Se t/4 + 1 = m então a poupança de m−1 moedas, mais as 3 moedas, é suficiente para pagar pela remoção, pois esta custa m moedas.

Resumindo: em qualquer iteração, a poupança somada com as 3 moedas é suficiente para pagar por uma operação. Isso mostra que nosso protocolo de pagamentos adiantados garante o custeio das n operações. Portanto, o custo total das n operações não passa de

3 n moedas.

Podemos dizer então que cada execução de Insira-na-Tabela e cada execução de Remove-da-Tabela custa 3 moedas no sentido amortizado. Tudo se passa como se o custo de uma execução de qualquer dos dois algoritmos fosse sempre o mesmo, independentemente dos valores de mt.

Esse resultado pode ser reformulado em termos de consumo de tempo: cada execução de Insira-na-Tabela e cada execução de Remova-da-Tabela consome Ο(1) unidades de tempo no sentido amortizado. Tudo se passa como se o consumo de tempo fosse sempre o mesmo, qualquer que seja a carga e o tamanho da tabela.

Exercícios 2

  1. Adote a seguinte política de administração de uma tabela A[1 .. m .. t] sob inserção e remoção: o tamanho da tabela dobra sempre que ficar cheia e cai pela metade sempre que a carga cair abaixo da metade do tamanho. Qual o custo amortizado de uma operação numa sequência arbitrária de inserções ou remoções?
  2. Examine o funcionamento de Remova-da-Tabela no caso em que t = 2 (e portanto m é 1 ou 2). Examine o funcionamento de Remova-da-Tabela no caso em que t = 4 (e portanto m é 2, 3, ou 4).
  3. Suponha que t ≥ 4 e m = t/4 + 1 no momento em que Remova-da-Tabela é invocado. Mostre que t/4 < mt/2 depois da execução de Remova-da-Tabela.
  4. ★ Mostre que no início de cada iteração do processo nas linhas 31 a 36, o número de moedas na poupança é pelo menos 2mt se m ≥ t/2 e pelo menos t/2−m se m < t/2. 
  5. ★ Defina f(m) assim: se m ≥ t/2 então f(m) = 2m − t e se m < t/2 então f(m) = t/2 − m. Faça um gráfico da função f.