E08 Three sum
Nas aulas de 5/10/2021 e 7/10/2021, discutimos o Problema 3SUM: dada uma sequência de números \((a_i)_{0\leq i<N}\), determinar o número de triplas $(i, j, k)$ com $i<j<k$ e $a_i+a_j+a_k=0$. Um algoritmo elementar para resolver 3SUM é implementado no programa ThreeSum.java que vimos (também dado abaixo). Esse algoritmo tem complexidade de tempo $\Theta(N^3)$.
Vimos como resolver 3SUM de forma consideravelmente mais eficiente, usando busca binária. É fácil ver que o algoritmo resultante tem complexidade de pior caso $O(N^2\log N)$. Também não é muito difícil ver que sua complexidade de pior caso é $\Omega(N^2\log N)$. Assim, o programa ThreeSumDeluxe.java, que implementa esse algoritmo, tem complexidade de pior caso $\Theta(N^2\log N)$.
Comentamos em sala que existe um algoritmo de complexidade de tempo $\Theta(N^2)$ para 3SUM. Neste exercício, você implementará tal algoritmo. Seu programa deve chamar-se ThreeSumSuper.java. O main() de seu programa ThreeSumSuper.java deve ser igual ao main() de ThreeSum.java e ThreeSumDeluxe.java. Você deve implementar seu algoritmo quadrático na função count() de seu programa ThreeSumSuper.java.
O algoritmo quadrático. Para conceber o algoritmo quadrático para 3SUM, estude o Exercício Teórico T05 Busca em A + A. Com aquele exercício em mente, será fácil desenvolver um algoritmo quadrático para 3SUM.
Elementos repetidos. É necessário que valha uma hipótese importante para o funcionamento correto de ThreeSumDeluxe.java: a entrada de ThreeSumDeluxe.java não deve conter elementos repetidos; com entradas com repetição, ThreeSumDeluxe.java pode ter saída incorreta (por quê?).
Importante. Seu algoritmo para 3SUM deve funcionar corretamente mesmo que haja repetições na entrada.
Integer overflow. Tanto no programa ThreeSum.java como ThreeSumDeluxe.java, não nos preocupamos com integer overflow. Da mesma forma, você não precisa se preocupar com integer overflow em seu programa ThreeSumSuper.java.
Gerador de entradas. Para gerar entradas com as quais experimentar seu programa ThreeSumSuper.java, você pode usar os programas RandomInts.java e RandomIntsPlain.java. O programa RandomInts.java gera sequências sem repetição, enquanto que RandomIntsPlain.java gera sequências sem restrição quanto a repetições.
$ java-algs4 RandomInts 10 20 121
-17 -8 -4 5 7 8 9 11 12 17
$ java-algs4 RandomIntsPlain 10 20 121
-8 17 7 9 17 -17 8 11 12 -4
$
Nos exemplos acima, 10 indica que queremos 10 inteiros e 20 indica que queremos números aleatórios uniformemente distribuídos no intervalo $[-20, 20]$. Esses programas recebem no terceiro argumento uma semente para o gerador de números aleatórios.
Observação. O programa RandomInts.java usa o tipo de dado SET, que ainda não estudamos.
Exemplos de execução
$ java-algs4 RandomInts 10 20 121 | java-algs4 ThreeSum
3
-17 5 12
-17 8 9
-8 -4 12
$ java-algs4 RandomInts 10 20 121 | java-algs4 ThreeSumDeluxe
3
-17 5 12
-17 8 9
-8 -4 12
$ java-algs4 RandomInts 10 20 121 | java-algs4 ThreeSumSuper
3
-17 8 9
-17 5 12
-8 -4 12
$
ThreeSumSuper.java deve ser muito mais rápido que ThreeSum.java.
$ java-algs4 RandomIntsPlain 5000 10000000 121 | time -p java-algs4 ThreeSum
756
real 21.67
user 21.62
sys 0.11
$ java-algs4 RandomIntsPlain 5000 10000000 121 | time -p java-algs4 ThreeSumSuper
756
real 0.34
user 0.39
sys 0.06
$
Embora a diferença entre $\Theta(N^2\log N)$ e $\Theta(N^2)$ seja em geral perceptível somente para valores grandes de $N$, em meus experimentos vejo o seguinte:
$ java-algs4 RandomInts 4000 10000000 121 | time -p java-algs4 ThreeSumDeluxe
362
real 0.53
user 0.56
sys 0.07
$ java-algs4 RandomInts 4000 10000000 121 | time -p java-algs4 ThreeSumSuper
362
real 0.34
user 0.38
sys 0.07
$
Com um valor maior de $N$, temos uma diferença maior:
$ java-algs4 RandomInts 50000 10000000 121 | time -p java-algs4 ThreeSumDeluxe
780515
real 48.10
user 48.09
sys 0.17
$ java-algs4 RandomInts 50000 10000000 121 | time -p java-algs4 ThreeSumSuper
780515
real 4.48
user 4.62
sys 0.11
$
Note que, acima, usamos RandomInts.java (e não RandomIntsPlain.java), para que não haja repetições na entrada de ThreeSumDeluxe.java.
Implementei uma versão de ThreeSumDeluxe.java que lida corretamente com entradas com repetição, chamado ThreeSumImproved.java. O algoritmo em ThreeSumImproved.java é também baseado em busca binária, e tem complexidade $\Theta(N^2\log N)$. Espera-se que seu programa ThreeSumSuper.java seja mais rápido que ThreeSumImproved.java. Os exemplos a seguir ilustram essa diferença.
$ java-algs4 RandomIntsPlain 10000 10000000 121 | time -p java-algs4 ThreeSumImproved
6282
real 5.26
user 5.26
sys 0.10
$ java-algs4 RandomIntsPlain 10000 10000000 121 | time -p java-algs4 ThreeSumSuper
6282
real 0.48
user 0.56
sys 0.07
$ java-algs4 RandomIntsPlain 20000 1000000000 121 | time -p java-algs4 ThreeSumImproved
503
real 21.63
user 21.60
sys 0.13
$ java-algs4 RandomIntsPlain 20000 1000000000 121 | time -p java-algs4 ThreeSumSuper
503
real 1.01
user 1.12
sys 0.08
$ java-algs4 RandomIntsPlain 20000 100000 121 | time -p java-algs4 ThreeSumImproved
5006256
real 22.83
user 22.71
sys 0.15
$ java-algs4 RandomIntsPlain 20000 100000 121 | time -p java-algs4 ThreeSumSuper
5006256
real 0.98
user 1.08
sys 0.08
$ java-algs4 RandomIntsPlain 50000 10000000 121 | time -p java-algs4 ThreeSumImproved
780536
real 144.29
user 144.02
sys 0.28
$ java-algs4 RandomIntsPlain 50000 10000000 121 | time -p java-algs4 ThreeSumSuper
780536
real 4.36
user 4.51
sys 0.10
$
Entrega. Neste exercício, basta você entregar seu programa ThreeSumSuper.java.
Observação (adicionada em 16/10/2021). Os arquivos experiments.txt e experimentsGNU.txt foram adicionados abaixo. Os experimentos iniciais nesses arquivos são como no enunciado acima, mas alguns experimentos novos aparecem nesses arquivos. Em particular, os experimentos finais nesses arquivos mostram que o printAll() em ThreeSumSuper.java é também rápido.
- 10 de octubre de 2021, 21:12
- 10 de octubre de 2021, 21:12
- 16 de octubre de 2021, 14:49
- 16 de octubre de 2021, 14:49