E07 Métodos adicionais para TSTs, Parte A
TSTs são alternativas muito boas. O seguinte aparece em some_experiments1.out, que é um arquivo fornecido no enunciado do Exercício E06 Hashing.
$ java-algs4 Timer DATA/leipzig1m.txt ++.+++++
Time to build FrequencyTable: 10.526
Time to build FrequencyTableRB: 13.873
Time to build FrequencyTableSC: 6.623
Time to build FrequencyTableLP: 1.82
Time to build FrequencyTableLPP: 1.867
Time to build FrequencyTableLPUH: 3.222
Time to build FrequencyTableLPUHP: 3.233
Vimos como usar ternary search tries (TSTs) para implementar tabelas de símbolos cujas chaves são strings. Assim, podemos escrever FrequencyTableTST.java (i.e., FrequencyTable implementada com TSTs) e verificar seu desempenho. O resultado é muito bom:
$ java-algs4 TimerTST DATA/leipzig1m.txt
Time to build FrequencyTableTST: 6.438
Note que, de fato, nesse exemplo, o desempenho de TSTs é melhor que o desempenho de árvores rubro-negras (ST.java e RedBlackBST.java), embora seja pior que o desempenho de tabelas de espalhamento.
Temos, entretanto, duas vantagens quando usamos TSTs em vez de tabelas de espalhamento: TSTs são compatíveis com operações ordenadas, e não há dificuldades envolvendo funções de hashing, dificuldades que são inerentes ao uso de tabelas de espalhamento. Ademais, lembre que, com TSTs, é possível implementar métodos como
public String longestPrefixOf(String query)
public Iterable<String> keysWithPrefix(String prefix)
public Iterable<String> keysThatMatch(String pattern)
Neste exercício, você irá implementar mais três métodos de natureza semelhante.
Métodos adicionais para TSTs. Adicione ao programa TST.java de S&W os métodos
public String maxWithPrefix(String prefix)
public String minWithPrefix(String prefix)
public Iterable<String> keysThatStartWith(String pattern)
Seu programa, com esses três novos métodos, deve chamar-se TSTPlus.java. Os métodos acima devem comportar-se da seguinte forma.
- public String maxWithPrefix(String prefix)
A chamada maxWithPrefix(prefix) deve devolver a chave s presente na TST que tem as seguintes duas propriedades: (1) s deve ter prefix como prefixo e (2) dentre todas as chaves que satisfazem (1), a chave s deve ser a maior delas em ordem alfabética.
Caso não haja nenhuma chave na TST que tenha prefixo prefix, o método deve devolver null. O tempo de execução de maxWithPrefix() deve ser proporcional ao comprimento da resposta; em particular, não deve depender de quantas chaves na TST têm prefixo prefix.
- public String minWithPrefix(String prefix)
A chamada minWithPrefix(prefix) deve devolver a chave s presente na TST que tem as seguintes duas propriedades: (1) s deve ter prefix como prefixo e (2) dentre todas as chaves que satisfazem (1), a chave s deve ser a menor delas em ordem alfabética.
Caso não haja nenhuma chave na TST que tenha prefixo prefix, o método deve devolver null. O tempo de execução de minWithPrefix() deve ser proporcional ao comprimento da resposta; em particular, não deve depender de quantas chaves na TST têm prefixo prefix.
- public Iterable<String> keysThatStartWith(String pattern)
Lembre que a chamada keysThatMatch(pattern) devolve um Iterable<String> com todas as chaves presentes na TST que estão de acordo com o padrão pattern. Em particular, as chaves devolvidas por keysThatMatch(pattern) tem o mesmo comprimento que pattern. A chamada keysThatStartWith(pattern) deve devolver um Iterable<String> com todas as chaves presentes na TST que têm um prefixo que está de acordo com pattern. Dito de outra forma, se pattern tem comprimento l, então as chaves devolvidas pela chamada keysThatStartWith(pattern) devem ser exatamente aquelas cujos prefixos de comprimento l concordam com pattern. Naturalmente, as chaves devolvidas por keysThatStartWith() devem estar em ordem crescente.
Exemplos. Abaixo você encontra o programa TSTPlusClientLite.java, que pode ser usado para experimentar seus métodos. Alguns exemplos de execução seguem no arquivo examplesLite.txt. Usamos como lista de palavras shellsST.txt e
https://www.ime.usp.br/~yoshi/DATA/Pwords
Palavras que contém um dado padrão. Além de TSTPlus.java, você deve escrever um programa chamado ContainsPattern.java, que pode ser usado para selecionar, das palavras dadas na entrada padrão, aquelas que contém um dado padrão (em qualquer lugar). Lembre que keysThatStartWith(pattern) seleciona as palavras que começam com o padrão pattern. Aqui, estamos interessados em permitir que pattern apareça em qualquer lugar da palavra.
$ java-algs4 ContainsPattern DATA/Pwords < 2patterns.txt
Words that contain .a.b.c.d. (4)
embasbacada
embasbacadas
embasbacado
embasbacados
- * - * -
Words that contain .a.e.i.o. (24)
agradecidos
alfabetizou
aparecidos
baleeiros
carecidos
compadecidos
comparecidos
desaparecidos
desfalecidos
desvanecidos
embravecidos
encarecidos
esclarecidos
esvanecidos
falecidos
fortalecidos
padecidos
parabenizou
paralelizou
parecidos
permanecidos
prevalecidos
reaparecidos
transparecidos
- * - * -
Abaixo segue ContainsPatternRE.java, um programa que resolve esse problema usando mecanismos do Java para lidar com expressões regulares. Seu programa ContainsPattern.java deve ter exatamente a mesma saída que ContainsPatternRE.java quando executado da mesma forma. Ademais, seu programa deve resolver esse problema usando o método keysThatStartWith() de seu programa TSTPlus.java.
Sugestão. Veja o Exercise 5.2.15, Substring matches, de S&W: https://algs4.cs.princeton.edu/52trie/
Observação. Vamos estudar expressões regulares e tópicos relacionados mais à frente no semestre. Neste momento, não é necessário entender o funcionamento de ContainsPatternRE.java. Apenas use esse programa para verificar a correção de seu programa ContainsPattern.java.
Desempenho de seus métodos. Algumas ideias simples levam a versões não muito rápidas dos métodos maxWithPrefix(), minWithPrefix() e keysThatStartWith() e do programa ContainsPattern.java. Veja os programas TSTMinus.java e ContainsPatternLazy.java fornecidos abaixo. Soluções como implementadas nesses programas não serão aceitas.
Exemplos mostram que as soluções simplificadas mencionadas acima podem ter tempo de execução bastante piores. Isso é ilustrado a seguir. Para gerar instâncias grandes, usamos o programa Generator.java, dado abaixo. Também seguem abaixo os programas TimerMinMaxMinus.java e TimerMinMaxPlus.java, que usam TSTMinus.java (fornecido) e TSTPlus.java (que você deve escrever). O programa md5 é usado para verificar se as saídas produzidas são iguais. O fato de o mesmo valor ser produzido pelo md5 indica que as saídas são, com altíssima probabilidade, iguais. (No GNU/Linux, use o programa md5sum.)
$ java-algs4 Generator 1000000 .05 abcdefgh 323 . > 1M.txt
$ md5 1M.txt
MD5 (1M.txt) = 688c34504ffa84a8aaadfe989737cd9e
$ java-algs4 Generator 100 .3 abcdefgh 3232021 | java-algs4 TimerMinMaxMinus 1M.txt | md5
Time to compute the min: 1.666
Time to compute the max: 1.666
5a78caec3ea5bb3fd39c2f68ba80dcea
$ java-algs4 Generator 100 .3 abcdefgh 3232021 | java-algs4 TimerMinMaxPlus 1M.txt | md5
Time to compute the min: 0.002
Time to compute the max: 0.002
5a78caec3ea5bb3fd39c2f68ba80dcea
Desempenho de ContainsPattern.java. As execuções abaixo ilustram o desempenho de ContainsPatternRE.java e ContainsPatternLazy.java e o desempenho esperado de ContainsPattern.java que você escreverá. O programa GeneratorForPatterns.java segue abaixo.
$ java-algs4 GeneratorForPatterns 200 5 .6 aeiou 888 | time java-algs4 ContainsPatternLazy DATA/Pwords | md5
118.51 real 116.96 user 3.90 sys
82add9c1a1f4a4d57db4d2017189bdd2
$ java-algs4 GeneratorForPatterns 200 5 .6 aeiou 888 | time java-algs4 ContainsPatternRE DATA/Pwords | md5
70.75 real 77.80 user 4.25 sys
82add9c1a1f4a4d57db4d2017189bdd2
$ java-algs4 GeneratorForPatterns 200 5 .6 aeiou 888 | time java-algs4 ContainsPattern DATA/Pwords | md5
18.85 real 21.48 user 4.07 sys
82add9c1a1f4a4d57db4d2017189bdd2
Entrega. Você deve entregar dois programas: TSTPlus.java e ContainsPattern.java.
Parte B. A parte B desse exercício pedirá para você implementar e adicionar os métodos
public String floor(String query)
public String ceiling(String query)
ao seu programa TSTPlus.java. Naturalmente, queremos implementações eficientes desses métodos, com tempo de execução proporcional ao comprimento das palavras envolvidas.
- 4. Juni 2021, 22:05
- 4. Juni 2021, 22:05