E11 Métodos adicionais para TSTs
Eficiência de tabelas de símbolos implementadas com TSTs. Vimos que tabelas de espalhamento com resolução de colisões por linear probing são muito eficientes. Os exemplos de execução abaixo de nosso teste simples padrão ilustra esse ponto (como você pode lembrar, FrequencyCounterRB.java é baseado em ARNEs e FrequencyCounterLP.java é baseado em hashing com linear probing):
$ time java-algs4 FrequencyCounterRB 1 < DATA/LEIPZIG/leipzig1m.txt
the 1160105
distinct = 534580
words = 21191455
real 0m14.452s
user 0m15.629s
sys 0m0.158s
$ time java-algs4 FrequencyCounterLP 1 < DATA/LEIPZIG/leipzig1m.txt
the 1160105
distinct = 534580
words = 21191455
real 0m4.920s
user 0m5.833s
sys 0m0.188s
Vimos como usar ternary search tries (TSTs) para implementar tabelas de símbolos cujas chaves são strings. O programa FrequencyCounterTST.java usa TSTs:
$ time java-algs4 FrequencyCounterTST 1 < DATA/LEIPZIG/leipzig1m.txt
the 1160105
distinct = 534580
words = 21191455
real 0m8.920s
user 0m9.996s
sys 0m0.177s
$
Note que, nos exemplos acima, o desempenho de TSTs foi melhor que o desempenho de ARNEs, embora tenha sido pior que o desempenho de hashing com linear probing.
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. 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. Neste exercício, não é necessário entender o funcionamento de ContainsPatternRE.java em detalhe. 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, muito provavelmente, 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: 0.999
Time to compute the max: 1.008
5a78caec3ea5bb3fd39c2f68ba80dcea
$ java-algs4 Generator 100 .3 abcdefgh 3232021 | java-algs4 TimerMinMaxPlus 1M.txt | md5
Time to compute the min: 0.007
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 -p java-algs4 ContainsPatternLazy DATA/Pwords | md5
real 75.14
user 73.02
sys 3.43
82add9c1a1f4a4d57db4d2017189bdd2
$ java-algs4 GeneratorForPatterns 200 5 .6 aeiou 888 | time -p java-algs4 ContainsPatternRE DATA/Pwords | md5
real 44.76
user 43.35
sys 4.66
82add9c1a1f4a4d57db4d2017189bdd2
$ java-algs4 GeneratorForPatterns 200 5 .6 aeiou 888 | time -p java-algs4 ContainsPattern DATA/Pwords | md5
real 13.50
user 12.45
sys 3.42
82add9c1a1f4a4d57db4d2017189bdd2
$
Entrega. Você deve entregar dois programas: TSTPlus.java e ContainsPattern.java.
Outros métodos adicionais. É um exercício bastante interessante 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.
- 16 junho 2024, 19:12 PM
- 16 junho 2024, 19:12 PM