E07 Paciência e LIS eficientes
Este enunciado supõe que você conhece o Exercício Teórico T09. Em particular, você deve, inicialmente, reler o programa PatiencePlain.java (dado naquele exercício e também abaixo) e estudar o programa TestPatiencePlain.java, dado abaixo. O programa TestPatiencePlain.java serve para verificar o tempo de execução do algoritmo implementado em PatiencePlain.java.
Neste exercício, você deve implementar uma solução mais eficiente que aquela implementada em PatiencePlain.java. Seu programa deve chamar-se Patience.java. Basicamente, bastará você alterar a implementação de uma única função em PatiencePlain.java: você deverá trocar a função
private int pilePlain(int x, Stack<Card>[] dec, int p)
por uma função de assinatura
private static int pile(int x, Stack<Card>[] dec, int p)
que computa o mesmo valor que pilePlain(), mas de forma mais eficiente. Naturalmente, será necessário você trocar a linha
int j = pilePlain(s[i], dec, p);
em PatiencePlain.java por
int j = pile(s[i], dec, p);
em seu programa Patience.java.
Geradores de instâncias. Podemos gerar sequências de inteiros com os programas RandomPerm.java e RandomSeqNS.java fornecidos abaixo. Dado um inteiro \(N\), o programa RandomPerm.java gera uma permutação aleatória dos inteiros $0,\dots,N-1$. Dado um inteiro $N$, o programa RandomSeqNS.java gera uma sequência com $N$ inteiros que é "quase-ordenada", isto é, uma sequência que é próxima da sequência $0,1,\dots,N-1$, mas em que cada elemento é alterado por um valor "pequeno" aleatório (fornecemos o valor máximo dessa perturbação aleatória de cada elemento como parâmetro). Estude as implementações de RandomPerm.java e RandomSeqNS.java para entender seu funcionamento.
Exemplos de execução TestPatiencePlain.java. Estude os exemplos de execução de TestPatiencePlain.java abaixo:
$ java-introcs RandomPerm 10 8888
8 10 5 1 3 2 7 9 4 6
$ java-introcs RandomPerm 10 8888 | java-introcs TestPatiencePlain 3
Decomposition in DSs:
0: 8 5 1
1: 10 3 2
2: 7 4
3: 9 6
A LIS (4 elements):
1 2 4 6
Time to read data: 0.029
Time to compute decomposition & LIS: 0.003
$ java-introcs RandomPerm 10 8888 | java-introcs TestPatiencePlain 2
A LIS (4 elements):
1 2 4 6
Time to read data: 0.023
Time to compute decomposition & LIS: 0.002
$ java-introcs RandomPerm 10 8888 | java-introcs TestPatiencePlain 1
Decomposition in DSs:
0: 8 5 1
1: 10 3 2
2: 7 4
3: 9 6
Time to read data: 0.023
Time to compute decomposition & LIS: 0.001
$ java-introcs RandomPerm 10 8888 | java-introcs TestPatiencePlain
4
Time to read data: 0.022
Time to compute decomposition & LIS: 0.001
$ java-introcs RandomPerm 100000 8888 | java-introcs TestPatiencePlain
623
Time to read data: 0.156
Time to compute decomposition & LIS: 0.048
$ java-introcs RandomPerm 1000000 8888 | java-introcs TestPatiencePlain
1976
Time to read data: 4.079
Time to compute decomposition & LIS: 1.46
$ java-introcs RandomSeqNS 100000 100 8888 | java-introcs TestPatiencePlain
12971
Time to read data: 0.183
Time to compute decomposition & LIS: 1.703
$ java-introcs RandomSeqNS 200000 100 8888 | java-introcs TestPatiencePlain
25919
Time to read data: 0.298
Time to compute decomposition & LIS: 5.758
$
Exemplos adicionais, que mostram que o algoritmo em PatiencePlain.java "não escala", são dados no arquivo example_runs_Plain.txt.
Exemplos de execução TestPatience.java. O programa TestPlain.java, fornecido abaixo, executa o mesmo teste que TestPatiencePlain.java executa, mas com o programa Patience.java (que você escreverá). Exemplos que mostram que o algoritmo que você implementará em Patience.java "escala" são dados no arquivo example_runs.txt. Você deverá observar tempos de execução grosso modo comparáveis com seu Patience.java.
A função pile(). A função pilePlain() em PatiencePlain.java encontra a pilha na qual devemos inserir o próximo elemento $x_i$ da sequência de entrada $s=(x_0,\dots,x_{N-1})$ fazendo uma busca sequencial. Em sua função pile(), você deve implementar uma variante apropriada de busca binária.
Observação importante. Verifique que, em cada instante da execução do algoritmo guloso, os últimos elementos das sequências $d_i$ em $d$ estão em ordem crescente (veja o arquivo top_cards_increase.pdf dado abaixo).
Entrega. Entregue apenas seu programa Patience.java.
- 26 novembro 2023, 21:39 PM
- 26 novembro 2023, 21:39 PM