TS implementada com busca binária

Livro de Sedgewick e Wayne: sec.3.1, p.362.  Website do livro: resumo sec.3.1, slides.  Código fonte, documentação, e dados de teste de todos os programas do livro: veja algs4.cs.​princeton.edu/​code/.

TSs ordenadas

• Suponha que as chaves de uma TS são comparáveis (menor, igual, maior)  e  o tipo Key tem um método compareTo().   Exemplos: Key igual a Integer, ou Double, ou String etc.
• Dizemos então que a TS é ordenada (ordered).  Nossas convenções gerais para TSs continuam valendo em TSs ordenadas.
• O posto (rank) de qualquer objeto k do tipo Key (que pode ou não estar na TS) é o número de chaves da TS que são estritamente menores que k.  Convém acrescentar a operação rank() à API da classe ST no caso de TSs comparáveis:

  int	rank(Key key)	número de chaves menores que key

Exercícios 1

1. Escreva um método recursivo limpa() que receba um vetor crescente a[0..n-1] e elimine os elementos repetidos do vetor, deixando o resultado limpo em a[0..m-1].

Implementação de TS em vetor ordenado

• Nossa implementação de TS ordenada vai usar dois vetores paralelos: um para as chaves, outro para os valores associados.
• Rastreamento de implementação de ST em vetor ordenado:

  

• [Algoritmo 3.2]  Classe BinarySearchST: implementação de tabela de símbolos em vetor ordenado:

  public class BinarySearchST <Key extends Comparable<Key>, Value> {
  
     private Key[] keys;
     private Value[] vals;
     private int N;
  
     public BinarySearchST(int capacity) { // construtor
        keys = (Key[]) new Comparable[capacity];
        vals = (Value[]) new Object[capacity];
     }
  
     public Value get(Key key) {
        int i = rank(key);
        if (i < N && keys[i].compareTo(key) == 0) 
           return vals[i];
        else return null;
     }
  
     public void put(Key key, Value val) {
        int i = rank(key);
        if (i < N && keys[i].compareTo(key) == 0) { 
           // acerto de busca
           vals[i] = val; 
           return; 
        }
        // falha de busca
        for (int j = N; j > i; j--) { 
           keys[j] = keys[j-1]; 
           vals[j] = vals[j-1]; 
        }
        keys[i] = key; 
        vals[i] = val;
        N++;
     }
  
     // devolve o posto de key
     public int rank(Key key) {
        int lo = 0, hi = N-1;
        while (lo <= hi) {
           int mid = lo + (hi - lo) / 2;
           int cmp = key.compareTo(keys[mid]);
           if (cmp < 0) hi = mid - 1;
           else if (cmp > 0) lo = mid + 1;
           else return mid;
        }
        return lo;
     }
  }
  

• Cada put começa com uma busca igual à de get;  se a busca for malsucedida, um novo item é acrescentado à  TS.
• Funciona corretamente mesmo com tabela vazia (bom sinal!).
• Para que funcione com tabela cheia, acrescente redimensionamento do vetor.

Exercícios 2

1. No livro de SW (p.379), a primeira linha do código de get() diz

         if (isEmpty()) return null;
   

   Isso é necessário?
2. Escreva uma implementação do método contains().
3. Implemente o método Iterable<Key> keys().
4. (SW 3.1.25) Caching em software. A implementação padrão de contains() chama get(). Assim, o loop interno

        if (!st.contains(word)) st.put(word, 1);
        else st.put(word, st.get(word) + 1);
   

   de FrequencyCounter resulta em duas ou três buscas para a mesma chave. Para evitar isso sem mudar o código de FrequencyCounter, podemos usar a técnica de software caching: armazenamos a localização da chave mais recentemente encontrada em uma variável de instância. Faça isso em BinarySearchST.

5. (SW 3.1.3)  Escreva uma implementação OrderedSequentialSearchST de TS baseado em um lista ligada ordenada. Quais as vantagens e desvantages?

Desempenho de BinarySearchST

• Veja as observações gerais sobre estimativa de desempenho de implementações de TSs.
• O método put() de BinarySearchST faz no máximo lg N + 1 comparações entre chaves, sendo N o número de chaves.
• Aplique BinarySearchST a uma lista com N chaves.  Na execução de get(k), uma chave da TS é tocada quando comparada com k.  Na execução de put(k,v), uma chave da TS pode ser tocada em duas ocasiões:
  • quando comparada com k durante a busca binária,
  • e, mais tarde, quando é deslocada para a direita para criar espaço para (k,v).
• Quantas das N chaves são tocadas durante um put()?  quantas durante um get()? 

  	número máximo de toques em comparações	número máximo de toques em deslocamentos
  get()	lg N	—
  put()	lg N	N

  A operação de busca é, portanto, muito rápida.  Mas a operação de inserção é muito lenta no pior caso.

• Consequência: Inserir N chaves distintas numa TS de vetor ordenado inicialmente vazio consome  N²  unidades de tempo no pior caso.
• O número médio de chaves tocadas por put() é a metade:  apenas N/2.
• Exemplo: O livro aplicou FrequencyCounter com BinarySearchST no lugar de ST às palavras de comprimento 8 ou mais no arquivo tale.txt.  Segue o gráfico do número de chaves tocadas por cada chamada de put(). Os pontos vermelhos dão a média corrente:

  

• Embora tale.txt não seja aleatório, o comportamento indicado pelo gráfico é semelhante ao de um arquivo de chaves aleatórias.

Exercícios 3

1. (SW 3.1.15)  Suponha que buscas são 1000 vezes mais frequentes que inserções em um cliente de BinarySearchST. Estimate a porcentagem do tempo total que é gasta em inserções quando o número de buscas é 10³, 10⁶, e 10⁹.
2. (SW 3.1.28) Inserções ordenadas. Modifique BinarySearchST de modo que a inserção de uma chave maior que todas as que estão na TS consuma tempo constante (de modo a construção de uma TS a partir de dados que estão em ordem crescente consuma tempo linear).
3. Acrescente um método a BinarySearchBST que calcule o custo médio de uma busca bem-sucedida, supondo que todas as chave têm a mesma probabilidade de ser buscada.
4. Acrescente um método a BinarySearchST que calcule o custo médio de uma busca malsucedida (supondo que todos os intervalos entre chaves da TS são igualmente prováveis).
5. (SW 3.1.38, p.394) Gráficos de custo amortizado. Aparelhe FrequencyCounter e BinarySearchST para produzir gráficos como os vistos acima (eles mostram o custo de cada put() ao longo da computação).
6. (SW 3.1.39, p.394) Tempo real.  Aparelhe FrequencyCounter com Stopwatch e StdDraw para fazer um gráfico em que o eixo x corresponde às sucessivas chamadas de get() e put() e o eixo y é o tempo total de execução. Um ponto é marcado no gráfico para representar o tempo acumulado depois de cada chamada. Rode o seu programa com tale.txt usando BinarySearchST. Discuta os resultados. (Observação: Saltos acentuados na curva podem ser explicados pelo caching, coisa que está além do escopo deste exercício.)

Resumo

• Resumo de custos das duas implementações básicas — SequentialSearchST e BinarySearchST — de tabela de símbolos:

  algoritmo	pior caso (tabela com N chaves)		caso médio (tabela com N chaves aleatórias)		operações ordenadas eficientes?
  	busca	insere	busca (acerto)	insere
  busca sequencial (lista ligada)	N	N	N/2	N	não
  busca binária (vetor ordenado)	lg N	2N	lg N	N	sim

Exercícios 4

1. (SW 3.1.13)  Qual das implementações de TS você usaria para uma aplicação que faz 10³ puts e 10⁶ gets, misturadas aleatoriamente?
2. (SW 3.1.14)  Qual das implementações de TS você usaria para uma aplicação que faz 10⁶ puts e 10³ gets, misturadas aleatoriamente?
3. (SW 3.1.31 simplificado) Testes de desempenho. Escreva um programa que preencha uma TS com N chaves aleatórias e depois faça buscas aleatórias de modo que cada chave na TS seja encontrada (busca bem-sucedida) aproximadamente 10 vezes e haja aproximadamente o mesmo número de buscas malsucedidas. Repita o experimento muitas vezes, dobrando o valor de N sucessivamente. Meça o tempo de cada experimento e imprima um gráfico do crescimento do tempo médio em função de N.