E12 HashSET
Neste exercício, você implementará o tipo HashSET, para representar conjuntos de um dado tipo genérico Key, com a seguinte API:
public class HashSET<Key> implements Iterable<Key>
--------------------------------------------------
public HashSET()
public int size()
public boolean isEmpty()
public boolean contains(Key key)
public void add(Key key)
public void delete(Key key)
public Key selectRandom()
public Iterator<Key> iterator()
Note que a API acima é basicamente a mesma de SET:
https://www.ime.usp.br/~yoshi/Sedgewick/Algs4th/Slides/35SearchingApplications.pdf
(veja página 3). Veja também
https://algs4.cs.princeton.edu/code/javadoc/edu/princeton/cs/algs4/SET.html
https://algs4.cs.princeton.edu/35applications/
e páginas 489 e 490 de S&W.
HashSET, comparado com SET, tem as seguintes diferenças: em HashSET (a) Key não é necessariamente um comparable e (b) há o método selectRandom(): se \(s\) é um HashSET com $N>0$ elementos, s.selectRandom() devolve um elemento de $s$ escolhido uniformemente ao acaso dentre todos os elementos de $s$ (isto é, cada elemento de $s$ tem probabilidade $1/N$ de ser devolvido).
Você deve usar uma tabela de hashing para implementar HashSET, resolvendo colisões usando linear probing. Para implementar selectRandom(), você deve usar StdRandom.java.
Dois clientes. Nos Exercícios E09 e E10, você usou o programa RandomOps.java para gerar operações aleatórias para estudar ABBs e ARNEs. Estude RandomOps.java; você verá que aquele programa precisa manter um conjunto de inteiros. RandomOps.java usa RedBlackBST.java enquanto que RandomOpsHash.java, abaixo, usa HashSET.java.
O programa Compare.java compara o desempenho de SET.java e HashSET.java diretamente, usando saídas produzidas por RandomOps.java/RandomOpsHashSET.java.
Experimente sua implementação de HashSET.java usando os clientes RandomOpsHash.java e Compare.java.
Exemplos de execução
$ time java-algs4 RandomOps 128 1000000 1000000 > /dev/null
real 0m6.740s
user 0m14.284s
sys 0m0.750s
$ time java-algs4 RandomOpsHash 128 1000000 1000000 > /dev/null
real 0m4.271s
user 0m6.924s
sys 0m0.605s
$ time java-algs4 RandomOps 128 10000000 10000000 > /dev/null
real 1m34.254s
user 4m54.007s
sys 0m6.787s
$ time java-algs4 RandomOpsHash 128 10000000 10000000 > /dev/null
real 0m39.931s
user 1m20.385s
sys 0m4.293s
$ java-algs4 RandomOpsHash 128 1000000 1000000 > tmp
$ java-algs4 Compare < tmp
Time SET took: 1.488
Time HashSET took: 0.286
SET and HashSET are equal (as they should be).
$ rm -f tmp; java-algs4 RandomOpsHash 128 10000000 10000000 > tmp
$ java-algs4 Compare < tmp
Time SET took: 26.003
Time HashSET took: 6.094
SET and HashSET are equal (as they should be).
$ rm tmp
$
Os exemplos acima mostram que o uso de hashing leva a programas consideravelmente mais rápidos que programas baseados em ARNEs. Não havendo perigo de entradas maldosas ou funções de hashing pobres, o uso de hashing em geral leva a programas mais eficientes.
Sugestão. Para implementar HashSET.java, estude LinearProbingHashST.java. Seu HashSET.java pode ser produzido a partir de LinearProbingHashST.java com um conjunto simples de modificações.
Desempenho. Espera-se que RandomOpsHash.java e Compare.java, com sua implementação de HashSET.java, tenham desempenho comparável ao ilustrado nos exemplos acima.
Entrega. Basta entregar seu programa HashSET.java.
- 26 junho 2022, 03:54 AM
- 26 junho 2022, 03:54 AM