Desempenho amortizado e gráficos de média corrida

Livro de Sedgewick e Wayne: sec.1.2, p.94.  Website do livro: resumo sec.1.2.

Gráficos de média corrida

• O livro faz gráficos interessantes para exibir o desempenho médio de programas.
• Os gráficos são produzidos pela classe Visual​Accumulator (que implementa o ADT descrito na página 95 do livro) e suas variações.  A classe permite examinar uma sequência de números e exibir dois pontos no gráfico para cada número examinado: 
  • um ponto cinza para representar o número e
  • um ponto vermelho para representar a média dos números lidos até agora.

  

• O código de VisualAccumulator depende da classe StdDraw do livro, mas é muito simples:

  public class VisualAccumulator {
  
     private double total;
     private int N;
  
     public VisualAccumulator(int X, double Y) {
        StdDraw.setCanvasSize(1000, 500);
        StdDraw.setXscale(0, X);
        StdDraw.setYscale(0, Y);
        StdDraw.setPenRadius(.005);
     }
  
     public void addDataValue(double val) {
        N++;
        total += val;
        StdDraw.setPenColor(StdDraw.DARK_GRAY);
        StdDraw.point(N, val);
        StdDraw.setPenColor(StdDraw.RED);
        StdDraw.point(N, mean());
     }
  
     public double mean() { 
        return total/N; 
     }
  
     public String toString() { 
        return "(" + N + " numeros) "  
               + "media: " + String.format("%4.2f", mean()); 
     }
  }
  

• Documentação:
  • A variável de instância N diz quantos números foram examinados até o momento. A variável total acumula a soma de todos os números examinados até o momento.
  • O método construtor VisualAccumulator() cria uma janela de 1000 pixels por 500 e nela define uma tela com eixo horizontal preparado para representar o intervalo [0,X] e eixo vertical preparado para representar o intervalo [0,Y].
  • O método addDataValue() recebe um número val, adiciona esse número ao acumulador e desenha um ponto cinza com coordenadas (N, val) e um ponto vermelho com coordenadas (N, total/N).
  • O método toString() devolve uma string que resume o estado do acumulador.
• O seguinte exemplo mostra como Visual​Accumulator pode ser usado para fazer um gráfico da média corrida de uma sequência de T números aleatórios entre 0 e 1:

  public class TestVisualAccumulator {
  
     public static void main(String[] args) {
        int T = Integer.parseInt(args[0]);
        VisualAccumulator acc = new VisualAccumulator(T, 1.0);
        for (int t = 0; t < T; t++) {
           double val = StdRandom.random();
           acc.addDataValue(val);
        }
        StdOut.println(acc); // invoca método toString de acc
     }
  
  }
  

• Resultado de um teste:

  % java TestVisualAccumulator 2000
  (2000 numeros) media: 0.509789
  

  

• Testes de TestVisual​Accumulator com 50, 100, e 1000 números aleatórios no intervalo [0,1].

Exercícios 1

1. Escreva um programa que receba uma sequência de inteiros pela entrada padrão e faça um gráfico da média corrente dos números. Use uma fila e uma variante de Visual​Accumulator com janela de tamanho diferente de 1000 por 500 pixels. (É claro que antes de desenhar o gráfico você deve examinar os números todos para calcular a escala do eixo x e a escala do eixo y.)  Use os arquivos randBints10K.txt, randGauss5K.txt, randExp5K.txt, randPoisson5K.txt, randGeom5K.txt, randLogA5K.txt, randLogB5K.txt, randLogC5K.txt. (Todos foram gerados com auxílio da classe StdRandom do livro.)

Desempenho amortizado

• Nos ADTs implementados em vetor com redimensionamento,
  • a maioria das operações é executada rápidamente mas
  • algumas são muito lentas.
• Digamos que o custo de uma operação é o número de acessos ao vetor durante a operação  (esse número é proporcional ao tempo que a operação consome).   O custo amortizado de uma operação é o custo médio da operação quando considerada em uma sequência de operações do ADT  (não se trata, portanto, da média de um conjunto arbitrário nem aleatório de execuções da operação).
• Exemplo: Considere a implementação de saco em vetor com redimensionamento. O custo amortizado da operação add() é muito baixo, pois cada ocorrência de uma execução lenta de add() é precedida por muitas ocorrências de execuções rápidas.
• Gráfico do custo (ponto cinza) e da média corrida dos custos (pontos vermelhos) em uma sequência de 128 execuções de add() para um saco implementado em vetor com redimensionamento:

  

• O custo amortizado não depende do número de operações!
• Verifique com lápis e papel que o custo amortizado das operações add() nunca passa de 5.

Exercícios 2

1. Considere a implementação StackRA de uma pilha em um vetor com redimensionamento. Faça um gráfico do custo amortizado da operação push().  (Sugestão: acrescente à classe StackRA uma variável de instância para contar o número de acessos ao vetor; acrescente um método para consultar essa variável; escreva um programa cliente que faça uma sequência de pushes na pilha assim aparelhada).
2. Considere a implementação StackRA de uma pilha em um vetor com redimensionamento. Verifique, com lápis e papel, que o custo total de N pushes não passa de 5N.  Portanto, o custo amortizado de um push não passa de 5.