MAC0323 - Algoritmos e Estruturas de Dados II (2021i)

Ternary search tries (TSTs).  No E07 Métodos adicionais para TSTs, Parte A, você adicionou os métodos

public String longestPrefixOf(String query)
public Iterable<String> keysWithPrefix(String prefix)
public Iterable<String> keysThatMatch(String pattern)

ao programa TST.java, e assim produziu o programa TSTPlus.java. Neste exercício, você deve adicionar os seguintes dois métodos ao seu programa TSTPlus.java:

public String floor(String query)
public String ceiling(String query)

Seu novo programa deve ter o mesmo nome, TSTPlus.java. O comportamento desses métodos deve ser igual ao comportamento dos métodos

public Key floor(Key key)
public Key ceiling(Key key)

em RedBlackBST.java, quando Key é String.

Para verificar o funcionamento de seus métodos, você pode usar o programa TSTPlusClient.java, dado abaixo.

Desempenho.  TSTPlusClient.java será útil para você depurar seus métodos. Para verificar a velocidade de seus métodos, você pode usar TSTFloorClient.java e TSTCeilingClient.java. Para comparar o desempenho de seus métodos floor() e ceiling() e o desempenho dos método floor() e ceiling() em RedBlackBST.java, você pode usar os programas RBSTFloorClient.java e RBSTCeilingClient.java.

Exemplos de execução. Nos exemplos abaixo, usamos arquivos em

https://www.ime.usp.br/~yoshi/DATA/GUTENBERG/
https://www.ime.usp.br/~yoshi/DATA/LEIPZIG/

$ java-algs4 TSTFloorClient DATA/LEIPZIG/leipzig1m.txt < DATA/GUTENBERG/anna.txt | md5
time to read in DATA/LEIPZIG/leipzig1m.txt: 10.858
time to process stdin: 0.919
58922447e573f0695235ebf5cd5eb10a
$ java-algs4 RBSTFloorClient DATA/LEIPZIG/leipzig1m.txt < DATA/GUTENBERG/anna.txt | md5
time to read in DATA/LEIPZIG/leipzig1m.txt: 13.475
time to process stdin: 0.649
58922447e573f0695235ebf5cd5eb10a
$ java-algs4 TSTFloorClient DATA/LEIPZIG/leipzig1m.txt < DATA/LEIPZIG/leipzig200k.txt | md5
time to read in DATA/LEIPZIG/leipzig1m.txt: 10.945
time to process stdin: 9.142
c904336f72353d12afe3f0627059f2bc
$ java-algs4 RBSTFloorClient DATA/LEIPZIG/leipzig1m.txt < DATA/LEIPZIG/leipzig200k.txt | md5
time to read in DATA/LEIPZIG/leipzig1m.txt: 13.708
time to process stdin: 7.345
c904336f72353d12afe3f0627059f2bc

Observe que os desempenhos são comparáveis, mas as versões para árvores rubro-negras são melhores. (Talvez você consiga implementar floor() e ceiling() para TSTs de forma mais eficiente; envie-me uma mensagem caso você conseguir.)

O fato de floor() e ceiling() para TSTs ser um pouco menos eficiente (nas implementações usadas nos exemplos acima) não é um grande problema. Dado que TSTs são, no geral, mais eficientes, caso você tenha uma aplicação em que floor() e ceiling() não sejam muito usados, TSTs ainda são uma ótima escolha para implementar tabelas de símbolos cujas chaves são strings.

Geradores de exemplos artificias.  O programa GeneratorTST.java pode ser usado para gerar instâncias para TSTFloorClient.java, TSTCeilingClient.java, RBSTFloorClient.java e RBSTCeilingClient.java.

Exemplos de execução

$ java-algs4 GeneratorTST 1000000 .05 ab 323 . > 1M.txt
time to produce list: 3.066
$ md5 1M.txt
MD5 (1M.txt) = 77f24bfebe575a3926a7f095fbdc36b0
$ java-algs4 GeneratorTST 1000000 .1 ab 888 > 1Mb.txt
time to produce list: 0.377
$ md5 1Mb.txt
MD5 (1Mb.txt) = 846b6fd730b1da1da278bd089471b6e3
$ java-algs4 TSTFloorClient 1M.txt < 1Mb.txt | md5
time to read in 1M.txt: 2.367
time to process stdin: 3.309
879229aff1baca61f94d839a656ecadd
$ java-algs4 RBSTFloorClient 1M.txt < 1Mb.txt | md5
time to read in 1M.txt: 6.829
time to process stdin: 3.4
879229aff1baca61f94d839a656ecadd
$ java-algs4 TSTCeilingClient 1M.txt < 1Mb.txt | md5
time to read in 1M.txt: 2.353
time to process stdin: 2.753
c0c95f102756d173cd6624603854e042
$ java-algs4 RBSTCeilingClient 1M.txt < 1Mb.txt | md5
time to read in 1M.txt: 6.81
time to process stdin: 3.363
c0c95f102756d173cd6624603854e042

Nos exemplos acima, examinando o tempo de processamento da entrada padrão, vemos que floor() e ceiling() para TSTs foram até um pouco mais rápidos que floor() e ceiling() para árvores rubro-negras. Examinando o tempo para processar o arquivo 1M.txt, vemos que a construção das tabelas de símbolo com TSTs foi consideravelmente mais rápida do que a construção das tabelas de símbolos com árvores rubro-negras.

Observação. Note que GeneratorTST.java, quando chamado com mais de 4 argumentos, gera strings sem repetição. Isso é implementado com o uso de uma TST para manter o conjunto dos strings já gerados até cada instante. Naturalmente, podemos também usar SET.java para isso. O programa GeneratorSET.java é uma tal versão de GeneratorTST.java. Lembre que SET.java usa uma árvore rubro-negra. A diferença de desempenho é considerável:

$ java-algs4 GeneratorTST 1000000 .1 ab 888 . | md5
time to produce list: 3.089
98c4b165dead7e5ee61da13d80efce0d
$ java-algs4 GeneratorSET 1000000 .1 ab 888 . | md5
time to produce list: 12.134
98c4b165dead7e5ee61da13d80efce0d

Isto é mais uma ilustração da efetividade de TSTs.

Tratamento de erros.  Os programas disponibilizados contém código (simplificado) para tratamento de "exceptions" (grosso modo, "erros") em Java. Você pode ler um pouco sobre essas coisas em, por exemplo,

https://en.wikibooks.org/wiki/Java_Programming/Throwing_and_Catching_Exceptions

Entrega.  Neste exercício, você deve entregar sua nova versão de TSTPlus.java, contendo agora os métodos floor() e ceiling(). A eficiência de suas implementações de floor() e ceiling() será comparada com a eficiência de floor() e ceiling() em árvores-rubro negras, executando TSTFloorClient.java etc, como acima.