E09 LZW ajustado
Comportamento pelo menos quase-quadrático. Como vimos nas aulas, a implementação do algoritmo de compactação LZW de S&W, que foi escrita antes do Java 6, update 7, tem comportamento pelo menos quase-quadrático, a partir dessa versão do Java, em entradas "naturais".
Neste exercício, você fará pequenas modificações na implementação de S&W para obter uma versão que roda em tempo linear.
Versão modificada de longestPrefixOf(). Sua primeira tarefa é adicionar um método de assinatura
public String longestPrefixOf(String query, int t)
ao programa TST.java. Essa versão de TST.java com esse método adicional deve chamar-se TSTb.java. O método acima deve devolver o mesmo string que o método longestPrefixOfLazy() dado abaixo devolve.
public String longestPrefixOfLazy(String query, int t) {
return longestPrefixOf(query.substring(t));
}
Entretanto, sua versão "não-lazy" deve rodar em tempo proporcional ao comprimento do string devolvido (a versão lazy gasta tempo proporcional a query.length() - t).
Adaptação de LZW.java. Com o método longestPrefixOf() que você escreveu acima, é fácil evitar em LZW.java o uso de substring() na linha
input = input.substring(t); // Scan past s in input.
que ocorre no fim do corpo do laço principal de compress(). Sua tarefa é fazer as modificações necessárias em LZW.java para evitar o uso dessa chamada de substring(). Sua versão modificada de LZW.java deve chamar-se LZWFixed.java.
Note que LZWFixed.java não deve usar TST.java. Ele deve usar TSTb.java.
Desempenho. As execuções abaixo servem para ilustrar (grosso modo) os tempos de execução esperados.
$ head -c500000 DATA/LEIPZIG/leipzig1m.txt | time java-algs4 LZW - | md5
2.56 real 2.62 user 0.26 sys
69ab8a133b784d220a5d0ba15cfbd801
$ head -c1000000 DATA/LEIPZIG/leipzig1m.txt | time java-algs4 LZW - | md5
8.83 real 10.35 user 0.67 sys
eb1e1de170a3931442005ac3d0cceb3d
$ head -c2000000 DATA/LEIPZIG/leipzig1m.txt | time java-algs4 LZW - | md5
32.61 real 40.83 user 1.77 sys
4862ff1d60497cc37968e29f5c40cdbf
$ head -c4000000 DATA/LEIPZIG/leipzig1m.txt | time java-algs4 LZW - | md5
124.61 real 156.50 user 5.40 sys
42d18554f0f51d5ee63b0c498fae90a0
$ head -c500000 DATA/LEIPZIG/leipzig1m.txt | time java-algs4 LZWFixed - | md5
0.41 real 0.46 user 0.06 sys
69ab8a133b784d220a5d0ba15cfbd801
$ head -c1000000 DATA/LEIPZIG/leipzig1m.txt | time java-algs4 LZWFixed - | md5
0.55 real 0.60 user 0.07 sys
eb1e1de170a3931442005ac3d0cceb3d
$ head -c2000000 DATA/LEIPZIG/leipzig1m.txt | time java-algs4 LZWFixed - | md5
0.83 real 0.88 user 0.09 sys
4862ff1d60497cc37968e29f5c40cdbf
$ head -c4000000 DATA/LEIPZIG/leipzig1m.txt | time java-algs4 LZWFixed - | md5
1.32 real 1.37 user 0.08 sys
42d18554f0f51d5ee63b0c498fae90a0
$ wc DATA/LEIPZIG/leipzig1m.txt
1000000 21191455 129644798 DATA/LEIPZIG/leipzig1m.txt
$ time java-algs4 LZWFixed - < DATA/LEIPZIG/leipzig1m.txt > /dev/null
real 0m32.299s
user 0m32.259s
sys 0m0.249s
$
Entrega. Você deve entregar os programas TSTb.java e LZWFixed.java.
Leia mais sobre a mudança do método substring(). Visite
Java Performance Tuning Guide
Changes to String internal representation made in Java 1.7.0_06
http://java-performance.info/changes-to-string-java-1-7-0_06/
De fato, para os experts, o site
Java Performance Tuning Guide
http://java-performance.info
parece trazer várias dicas interessantes sobre o Java.
Entretanto, tem algo dito por Knuth que é bom sempre ter em mente:
"The real problem is that programmers have spent far too much time worrying about efficiency in the wrong places and at the wrong times; premature optimization is the root of all evil (or at least most of it) in programming."
The Art of Computer Programming
Donald E. Knuth
https://www-cs-faculty.stanford.edu/~knuth/taocp.html
Veja mais:
Program optimization
https://en.wikipedia.org/wiki/Program_optimization