Desafio

O grupo que apresentar o melhor EP vai receber como prêmio a média final 10,0. Supõe-se que o melhor produza resultados corretos para o conjunto de testes de avaliação. Para a escolha do melhor serão realizados os seguintes testes: Dados três conjuntos de dados, os programas que obtiverem o melhor desempenho em quatro máquinas homogêneas serão classificados para a fase final.

Na fase final, os programas serão executados três vezes para cada conjunto de testes. Será considerado o tempo de execução médio. O programa que obtiver o maior número de melhores tempos médios será considerado vencedor. Os dados de desempenho serão divulgados na página da disciplina. Para eventuais desempates, no caso de desempenhos muito semelhantes, serão usados cenários com mais máquinas, ou mesmo máquinas não homogêneas.

Testes

Três conjuntos de dados foram escolhidos de forma que pudessem avaliar o desempenho dos programas em diferentes situações. O teste1 , com grande quantidade de números (1000) e tamanho pequeno das combinações (2),  avalia os programas em uma situação de muitas combinações (~500.000). O teste2 , com pequena quantidade de números (20) e tamanho grande das combinações (10), avalia o desempenho para combinações grandes. E o teste3 , avalia os programas para uma quantidade pequena de combinações.

Teste	Quant. Números	Tam. Combinações	Quant. Combinações
1	1.000	2	499.500
2	20	10	184.756
3	50	3	19.600

O ambiente de testes utilizado foi o cluster Biowulf do IME, cujas configurações de hardware podem ser obtidas em http://www.vision.ime.usp.br/~cage/Beowulf/.
 

Dados de Desempenho - Fase Classificatória

Os trabalhos incluídos no desafio foram os que apresentaram resultados corretos para um conjuntos de testes preliminar. Alguns trabalhos não participaram do desafio por não permitir leitura da entrada a partir de um arquivo.

Classificação	Alunos	Teste1 (ms)	Teste2 (ms)	Teste3 (ms)
1º	Roger Araújo & Marcel Hiroshi	191,168	147,093	38,357
2º	Tiago Jorge & Luciana Dias	5144,393	832,391	541,798
3º	Rafael Barroso & Francisco Sobral	6273,308	1518,484	244,925
4º	Marcelo Takeshi	2755,99	2779,24	2705,97
5º	Daniel Ribeiro	632584,163	259097,314	26920,304

Dados de Desempenho - Fase Final

Classificação	Alunos	Teste1 (ms)	Teste2 (ms)	Teste3 (ms)
1º	Roger Araújo & Marcel Hiroshi	189,70	146,66	37,89
2º	Tiago Jorge & Luciana Dias	5148,32	836,53	544,53
3º	Rafael Barroso & Francisco Sobral	5587,26	1516,88	262,73

Análise das Soluções Finalistas

Para a análise das soluções dos finalistas, vamos analisar três características que foram implementadas de forma diferente por cada equipe. As características analisadas foram: a ordenação dos números, a geração das combinações e a verificação da primalidade da soma dos elementos de cada combinação.

Na implementação do medalha de bronze, a ordenação foi feita na sequência inteira no nó master, usando o algoritmo bucketSort. A geração das combinações foi distribuída pelos processadores e a verificação da primalidade foi feita usando o algoritmo de Monte Carlo.

Na implementação do medalha de prata, a ordenação foi feita no momento da verificação da propriedadae média-mediana, sendo feita nos elementos da combinação usando quickSort. A geração das combinações foi distribuída pelos processadores e a verificação da primalidade foi feita usando um vetor com 1 milhão de números primos, que foi gerado em cada nó.

O vencedor, medalha de ouro, fez a ordenação da sequência inteira no nó master, usando o algoritmo bubleSort. A geração das combinações foi distribuída pelos processadores e a verificação da primalidade foi feita usando um método simples e eficiente para números de até 32 bits. Esse método, chamado de "Crivo de Erastótenes", trata os casos especiais primeiro, depois os números pares positivos (que não são primos) e finalmente testa os divisores ímpares indo de 3 até a raiz quadrada do número.

Diante das soluções apresentadas pelos melhores trabalhos e as diferenças de tempos de execução podemos concluir que: (1) o método usado na ordenação não teve tanta influência no resultado visto que a quantidade de números é pequena em relação à quantidade de combinações; (2) a distribuição da geração das combinações foi fator importante no bom desempenho dos programas (os três o fizeram), visto a grande quantidade destas; (3) a implementação da verificação da primalidade foi o fator determinante na diferença dos tempos de execução dos programas.