Tabelas de símbolos (TSs)

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/.

Resumo:

Pré-requisitos:

Introdução

Exemplo: dois clientes simples de TS

Dados para testes

Exercícios 1

  1. Qual a saída de FrequencyCounter se todas as palavras tiverem comprimento menor que minlen letras? Essa saída é razoável?
  2. (SW 3.1.19)  Modifique FrequencyCounter de modo que o programa devolva todas as palavras que têm frequência máxima. (Use uma fila.)
  3. Modifique FrequencyCounter de modo que o programa imprima o número total de palavras lidas e o número de palavras distintas.
  4. Otimização miúda.  Reescreva a parte final de FrequencyCounter de modo a não inserir a palavra vazia max em st.
  5. Otimização miúda.  Reescreva o loop interno de FrequencyCounter de modo que as expressões st.get e st.put apareçam só uma vez cada e st.contains desapareça.
  6. Repita os experimentos do livro de SW para confirmar os números da tabela acima.
  7. Quantas palavras de 5 letras ou mais há no livro Quincas Borba de Machado de Assis?  (Pontos extra se sua contagem não fizer distinção entre maiúsculas e minúsculas e ignorar os sinais de pontuação.)
  8. Acrescente código a FrequencyCounter de modo que o programa imprima uma amostra aleatória de 50 das palavras que estão na TS.
  9. (SW 3.1.9)  Acrescente código a FrequencyCounter de modo que o programa imprima a última palavra inserida na TS e o número total de palavras processadas antes da última inserção. Qual a resposta para tale.txt com minlen igual a 1, 8, e 10?
  10. Dedup.  Escreva um programa cliente que filtre as palavras repetidas da entrada padrão.

TS implementada com lista sequencial não ordenada

Exercícios 2

  1. Escreva um método recursivo limpa() que receba uma lista ligada e elimine os elementos repetidos da lista.
  2. Escreva uma implementação do método contains().
  3. (SW 3.1.2)  Escreva uma implementação ArrayST de tabela de símbolos baseado em um vetor não ordenado. Quais as vantagens e desvantages?
  4. Implemente o método Iterable<Key> keys().

Como estimar o desempenho de uma implementação de TS?

Desempenho de SequentialSearchST

Exercícios 3

  1. Acrescente um método a SequentialSearchST que calcule o custo de uma busca aleatória bem-sucedida, supondo que todas as chave têm a mesma probabilidade de ser buscada.
  2. Acrescente um método a SequentialSearchST que calcule o custo de uma busca aleatória malsucedida.
  3. (SW 3.1.38, p.394) Gráficos de custo amortizado. Aparelhe FrequencyCounter e SequentialSearchST para produzir gráficos como os vistos acima.

Exercícios 4

  1. (SW 3.1.22, p.391) Self-organizing search. Um busca é auto-organizada se rearranja os itensda 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.
  2. (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.

  3. (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 SequentialSearchST. Discuta os resultados. (Observação: Saltos acentuados na curva podem ser explicados pelo caching, coisa que está além do escopo deste exercício.)

Perguntas e respostas

Valid CSS! Valid HTML 4.01 Strict