Tabelas de símbolos elementares

Vejam as páginas Tabelas de símbolos (PF), TS implementada com busca binária (PF), Operações adicionais em TS (PF) e Elementary Symbol Table.

Vocês andaram implementando várias tabelas de símbolos. Algumas em MAC0216, outras em MAC0121 e no EP01 e EP03 vocês implementaram tabelas de símbolos.

Atenção, as nossas tabelas de símbolos não tem chaves repetidas, não tem null como chave, As implementações dos EP01 e EP03 foram simples, mas tinham os seu objetivos. Tabelas de símbolos podem ser ordenadas e não ordenadas. A do EP01 utilizava um vetor, redimensionamento e era não ordenada. Por ser não ordenadas a parte administrativa da tabela se apoiava no método equals():

public class ST {
    private String[] keysT; // = null;
    private int[]    valsT; // = null;
    [...]
    // Does this symbol table contain the given key?
    // Throws  java.lang.NullPointerException - if key is null
    public boolean contains(String key) {
        if (key == null) {
            throw new java.lang.NullPointerException("ST.contains(): key is null");
        }
        for (int i = 0; i < n; i++) {
            if (key.equals(keysT[i])) {
                return true;
            }
        }
        return false;
    }

Já a tabela de símbolos do EP3 era ordenada, as chaves eram Comparable e vocês usavam o método compareTo() para administrar a tabela. Além disso, essa tabela utilizava listas ligadas, generics e iteradores, ou seja, havia um método keys() que retornava as chaves como iteradores (poderíamos colocar, por exemplo, as chaves em um objeto da classe Queue<Keys> e retorná-lo:

public class LinkedListST<Key extends Comparable<Key>, Value> {
    // atributos de estado 
    private Node first;
    private Node last;
    private int n = 0;   // number of key-value pairs in the ST

    private class Node {
        Key   key;
        Value val;
        Node next;

        public Node() {
        }
        
        public Node(Key key, Value val, Node next) {
            this.key  = key;
            this.val  = val;
            this.next = next;
        }
    }
    
    [...]
    /** Returns all keys in the symbol table as an Iterable.
     * To iterate over all of the keys in the symbol table named st, use the
     * foreach notation: for (Key key : st.keys()).
     */
    public Iterable<Key> keys() {
        [...]
    }

Em ST ordenadas podemos implementar métodos min(), max(), select() que usam a ordenação da ST para fazer o seu trabalho em tempo constante).

Em aula implementamos tabelas de símbolos em listas ligadas não-ordenadas e em vetores ordenados. Vetores ordenados nos permitem usam busca binária, por isso o nome da classe era BinarySearchST.

Na última aula começamos a trabalhar com ST ordenadas implementadas em árvores binárias de busca, a classe BST. Em termos de desempenho experimental, até agora, a campeã éBST, seguida daBinarySearchST` e seguida, como uma certa distância, pelas demais.

Em árvores binárias, vimos os percursos manjados, pré-ordem, in-ordem e pós-ordem.

Vocês devem ter noções sobre o consumo de tempo de cada uma dessas implementações.

Aqui vão alguns exercícios.

• Exercises: 1, 3 e 5 (ainda veremos 16 e 17)

Os exercícios a seguir foram copiados da página Tabela de Símbolos (PF):

• (SW 3.1.22, p.391) Self-organizing search. Um busca é auto-organizada se rearranja os itens da tabela de modo que aqueles mais frequentemente usados sejam mais fáceis de encontrar. Modifique a implementação do Exercício 3.1.2 da seguinte maneira: a cada busca bem-sucedida, coloque o item (chave,valor) encontrado no começo do vetor e desloque os outros itens uma posição para a direita. Esse procedimento é conhecido como move-to-front heuristic.

• (SW 3.1.25) Caching em software. A implementação padrão de contains() chama get(). Assim, o loop interno de FrequencyCounter

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

  resulta em duas ou três buscas pela 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 SequentialSearchST.