E06 Hashing
Várias implementações de tabelas de símbolos. Conhecemos várias formas de implementar tabelas de símbolos. Temos duas versões com árvores rubro-negras:
1. ST.java
2. RedBlackBST.java
Temos também algumas implementações baseadas em tabelas de hashing (tabelas de espalhamento):
3. SeparateChainingLiteHashST.java
4. SeparateChainingHashST.java
5. LinearProbingHashST.java
As versões (3) e (4) usam resolução de colisões por encadeamento (separate chaining). A versão "lite" (versão (3)) não usa doubling e halving (nessa implementação, o tamanho fixo do vetor de listas ligadas é 997); a versão (4) implementa doubling e halving. A tabela de (4) começa com 4 listas ligadas.
A versão (5) usa resolução de colisões por linear probing. Esta implementação usa doubling e halving (a tabela começa com 4 entradas).
A função hashCode() do Java para strings é boa, mas há sugestões de funções "melhores". Uma sugestão é a seguinte função (aqui chamada de função de hashing universal):
// universal hashing function from "Algorithms in C, Third Edition,"
// by Robert Sedgewick, Addison Wesley Longman, 1998.
private int hashU(Key key, int M) {
int h = 0, a = 31415, b = 27183;
String s = (String) key;
for (int i = 0; i < s.length(); i++, a = a*b % (M-1))
h = ((a*h + s.charAt(i)) & 0x7fffffff) % M;
return h;
}
A implementação
6. LinearProbingHashUHST.java
é como (5), mas usa a função de hashing universal acima.
Veja agora a 2a. pergunta no arquivo 478.pdf abaixo. (Observe que a resposta a essa pergunta tem uns erros; em particular, os primos da tabela são os maiores primos menores ou iguais às potências de dois dadas.)
As implementações
7. LinearProbingHashPrimesST.java
8. LinearProbingHashPUHST.java
são como (5) e (6), mas usam funções de hashing cujos contradomínios são sempre o conjunto {0, 1, ..., p - 1} para algum primo p (de fato, p = primes[k] para algum k, onde primes[k] é como no arquivo 478.pdf).
Tabelas de frequências. Temos usado um programa para determinar tabelas de frequências de palavras em textos para ilustrar o uso de tabelas de símbolos. Por exemplo, lembre-se do programa
9. FrequencyTable.java
Naturalmente, podemos usar qualquer implementação de tabela de símbolos em FrequencyTable.java. Temos assim 7 variantes desse programa:
10. FrequencyTableRB.java
11. FrequencyTableSC.java
12. FrequencyTableSCL.java
13. FrequencyTableLP.java
14. FrequencyTableLPUH.java
15. FrequencyTableLPP.java
16. FrequencyTableLPUHP.java
Comparação de tempos de execução. Podemos comparar os tempos de execução dos programas de (9) a (16), usando o programa
17. Timer.java.
Essa comparação pode ser feita usando-se arquivos de dados como aqueles em
https://www.ime.usp.br/~yoshi/DATA/LEIPZIG/
https://www.ime.usp.br/~yoshi/DATA/Gutenberg/
Ademais, podemos usar o programa
18. MGenerator.java
dado abaixo para gerar entradas artificias para Timer.java. De fato, o programa (18) serve para gerar entradas "maldosas" para Timer.java (mais precisamente falando, para alguns dos frequency tables considerados em Timer.java). Estude cuidadosamente os exemplos de execução nos arquivos some_experiments*.out abaixo. São dados dois arquivos some_experiments*.out, produzidos em máquinas diferentes.
Note que, nos casos de entradas "naturais" (e não "artificiais"), o uso de hashing resulta em tempos melhores (ou bem melhores). São particularmente rápidas as implementações com linear probing e linear probing com tabelas de tamanho primo (FrequencyTableLP e FrequencyTableLPP).
Sua primeira tarefa. Apesar de linear probing e linear probing com tabelas de tamanho primo sejam em geral os melhores, é possível gerar entradas artificias que tornam o desempenho dessas tabelas de hashing ineficientes. Isso está ilustrado nos arquivos some_experiments*.out. Sua tarefa geral neste exercício é entender por que o tempo de execução é às vezes ruim quando usamos tabelas de hashing.
Para tanto, você deve escrever um programa que produz histogramas como aquele na p. 14 das transparências
https://www.ime.usp.br/~yoshi/Sedgewick/Algs4th/Slides/34HashTables.pdf
Seu programa deve chamar-se HashingProfile.java. Seu programa deve comportar-se como descrito a seguir. Seguem algumas possíveis execuções de seu programa:
$ cat DATA/tinyTale.txt | java-algs4 HashingProfile 3 -2 -s . .
$ head -n6 DATA/leipzig100k.txt | java-algs4 HashingProfile 5 -2 -s .
$ head -n6 DATA/leipzig100k.txt | java-algs4 HashingProfile 5 -p -s .
$ head -n6 DATA/leipzig100k.txt | java-algs4 HashingProfile 5 -2 -u .
$ head -n6 DATA/leipzig100k.txt | java-algs4 HashingProfile 5 -p -u .
$ head -n10000 DATA/leipzig100k.txt | java-algs4 HashingProfile 7 -2 -s .
A execução
$ cat DATA/tinyTale.txt | java-algs4 HashingProfile 3 -2 -s . .
deve produzir a saída
M = 8
M log M = 16.635532333438686
N = 20
N/M = 2.5
[ 5] 1:
belief
epoch
the
was
wisdom
[ 3] 3:
it
season
worst
[ 4] 4:
best
despair
hope
incredulity
[ 3] 5:
darkness
spring
winter
[ 2] 6:
light
times
[ 3] 7:
age
foolishness
of
hits = 6
Além disso, ela deve gerar a imagem tinyTale.png abaixo.
Os argumentos de HashingProfile.java devem são interpretados da seguinte forma: "3" significa que queremos que o contradomínio da função de hashing seja {0, ..., 7} (que tem cardinalidade 2^3 = 8). O "-s" significa que queremos usar a função de hashing padrão (como implementada em, por exemplo, SeparateChainingLiteHashST.java).
As primeiras 4 linhas da saída acima são claras: M é o tamanho da tabela e N é o número de palavras distintas na entrada tinyTale.txt.
[ 5] 1:
belief
epoch
the
was
wisdom
significa que têm valor de hashing 1 as cinco palavras belief, ..., wisdom.
[ 2] 6:
light
times
significa que têm valor de hashing 6 as 2 palavras light e times. Vemos da saída acima que não há palavras na entrada com valor da função de hashing igual a 0 ou a 2.
hits = 6
significa que é 6 a cardinalidade da imagem da função de hashing com a entrada tinyTale.txt (de fato, a imagem é {1, 3, 4, 5, 6, 7}).
A execução
$ cat DATA/tinyTale.txt | java-algs4 HashingProfile 3 -2 -s .
deve produzir a saída
M = 8
M log M = 16.635532333438686
N = 20
N/M = 2.5
hits = 6
A imagem com o histograma também deve ser produzida. Ademais, a execução
$ cat DATA/tinyTale.txt | java-algs4 HashingProfile 3 -2 -s
deve produzir a saída
M = 8
M log M = 16.635532333438686
N = 20
N/M = 2.5
hits = 6
mas nenhuma imagem deve ser produzida.
Vamos agora considerar as variantes de execução em que "-2" e "-s" são alterados. Se damos como argumento "-u" em vez de "-s", a função de hashing universal acima deve ser usada.
$ cat DATA/tinyTale.txt | java-algs4 HashingProfile 3 -2 -u
M = 8
M log M = 16.635532333438686
N = 20
N/M = 2.5
hits = 7
Se damos como argumento "-p" em vez de "-2", queremos que se tenha um contradomínio com cardinalidade prima para a função de hashing. Supondo que o primeiro argumento é k, queremos usar o maior primo menor ou igual a 2^k como o tamanho do contradomínio da função de hashing (veja, por exemplo, LinearProbingHashPrimesST.java).
$ cat DATA/tinyTale.txt | java-algs4 HashingProfile 3 -p -s
M = 7
M log M = 13.621371043387192
N = 20
N/M = 2.857142857142857
hits = 7
$ cat DATA/tinyTale.txt | java-algs4 HashingProfile 3 -p -u
M = 7
M log M = 13.621371043387192
N = 20
N/M = 2.857142857142857
hits = 6
Os histogramas gerados pelas execuções a seguir são fornecidos abaixo.
$ cat DATA/bible_KJ.txt | java-algs4 HashingProfile 7 -2 -s .
$ cat DATA/bible_KJ.txt | java-algs4 HashingProfile 7 -p -s .
$ cat DATA/bible_KJ.txt | java-algs4 HashingProfile 7 -2 -u .
$ cat DATA/bible_KJ.txt | java-algs4 HashingProfile 7 -p -u .
$ cat DATA/leipzig1m.txt | java-algs4 HashingProfile 13 -2 -s .
$ cat DATA/leipzig1m.txt | java-algs4 HashingProfile 12 -p -u .
ENTREGA
Neste exercício, você deve entregar seu programa HashingProfile.java. Além disso, você deve entregar, em um arquivo separado, suas respostas para as seguintes duas perguntas.
Pergunta 1. Hashing em geral tem tempos de execução melhores ou consideravelmente melhores que árvores nos exemplos em some_experiments*.out. Entretanto, algo diferente ocorre na execução
java-algs4 MGenerator 50000 20 Aa BB 201905 | java-algs4 Timer - ++.+++++
Explique por que isso ocorre.
Pergunta 2. A função de hashing universal dada acima parece bastante "aleatória". Entretanto, considere a execução
$ java-algs4 MGenerator 1000000 20 ABC DEF 201905 | java-algs4 Timer - ++.+++++
Observe que temos as seguintes linhas na saída da execução da linha acima (veja some_experiments*.out):
Time to build FrequencyTableLPUH: 220.259 (some_experiments1.out)
Time to build FrequencyTableLPUH: 746.276 (some_experiments2.out)
Claramente há algo anômalo quando usamos tabelas de hashing com linear probing e a função de hashing universal sugerida acima. Note que algo semelhante ocorre nas execuções
$ java-algs4 MGenerator 50000 20 ABCD BBBB 201905 | java-algs4 Timer - ++.+++++
$ java-algs4 MGenerator 100000 20 ABCD BBBB 201905 | java-algs4 Timer - ++.+++++
Use seu programa HashingProfile.java para descobrir a fonte do problema (diga como você usou HashingProfile.java).
Você consegue reproduzir esse problema com outras entradas? (Por exemplo, com a execução de MGenerator.java com outros parâmetros.)
Pergunta 3 (opcional). Nos exemplos dados em some_experiments*.out, FrequencyTableLPUHP.java comportou-se bastante bem, embora não tenha sido o mais rápido. Você consegue gerar um exemplo de entrada para forçar FrequencyTableLPUHP.java ter um tempo de execução consideravelmente pior que os outros FrequencyTable*.java? (Se você conseguir, envie uma mensagem para mim.)
- 2 June 2021, 4:05 PM
- 2 June 2021, 4:05 PM