MAC338 - Experimentos computacionais

• Algoritmos de ordenação
  • Mergesort
    
    1. Etapa 1: Implemente uma versão simples do mergesort, como a da aula, por exemplo. Teste essa versão com a declaração do vetor auxiliar dentro do intercala (v0) contra a versão em que a declaração está fora da recursão (v1), como indicado na aula das dicas. Determine qual é em média a diferença entre o tempo de execução das versões (v0) e (v1).
    2. Etapa 1c: Produza uma versão de (v1) com o corte para vetores pequenos: modifique (v1), acionando o insertion_sort para vetores de tamanho no máximo M, e determine qual é o melhor valor de M para a sua modificação. Chame a modificação otimizada de (v1c). Determine qual é em média a diferença entre o tempo de execução das versões (v1) e (v1c).
    3. Etapa 2: Produza uma versão (v2) de (v1) que inclui o teste de ordenação: execute o intercala apenas se o vetor não está já ordenado, como explicado em aula. Determine qual é em média a diferença entre o tempo de execução das versões (v1) e (v2).
    4. Etapa 2c: Produza uma versão (v2c) de (v2) com o corte para vetores pequenos, como na Etapa 1. Determine qual é em média a diferença entre o tempo de execução das versões (v2) e (v2c).
    5. Etapa 3: Produza uma versão (v3) de (v1) que alterna o uso do vetor original e do vetor auxiliar no intercala, como explicado em aula. Determine qual é em média a diferença entre o tempo de execução das versões (v1) e (v3).
    6. Etapa 3c: Produza uma versão (v3c) de (v3) com o corte para vetores pequenos, como na Etapa 1c. Determine qual é em média a diferença entre o tempo de execução das versões (v3) e (v3c).
    7. Etapa 4: Produza uma versão (v4) de (v1) implementando o teste de ordenação e o uso alternado do vetor original e auxiliar. Determine qual é em média a diferença entre o tempo de execução das versões (v1), (v2), (v3) e (v4). Chame de (v*) a melhor dentre estas quatro versões.
    8. Etapa 4c: Produza uma versão (v4c) de (v4) com o corte para vetores pequenos, como na Etapa 1c. Determine qual é em média a diferença entre o tempo de execução das versões (v1), (v1c), (v2c), (v3c), (v4c) e (v*).
    9. Etapa 5: Conclua qual é a melhor versão do mergesort que você obteve destes experimentos, e escreva um breve relatório justificando a sua conclusão.

  • Quicksort
    
    1. Etapa 1: Implemente uma versão simples do quicksort aleatorizado, como a da aula, por exemplo. Teste essa versão (v0) contra a versão (v1) sem recursão de cauda (que mantem a chamada recursiva para a metade menor da partição). Determine qual é em média a diferença entre o tempo de execução das versões (v0) e (v1).
    2. Etapa 1c: Produza uma versão (v1c) de (v1) com o corte para vetores pequenos, como na Etapa 1c do Mergesort. Determine qual é em média a diferença entre o tempo de execução das versões (v1) e (v1c).
    3. Etapa 2: Produza uma versão (v2) de (v1) que usa como pivô a mediana de três, como explicado em aula. Determine qual é em média a diferença entre o tempo de execução das versões (v1) e (v2).
    4. Etapa 2c: Produza uma versão (v2c) de (v2) com o corte para vetores pequenos, como na vEtapa 1c do Mergesort. Determine qual é em média a diferença entre o tempo de execução das versões (v2) e (v2c).
    5. Etapa 3: Produza uma versão (v3) de (v1) que triparticiona o vetor, excluindo todas as chaves iguais ao pivô da recursão, como explicado em aula. Determine qual é em média a diferença entre o tempo de execução das versões (v1) e (v3).
    6. Etapa 3c: Produza uma versão (v3c) de (v3) com o corte para vetores pequenos, como na Etapa 1c do Mergesort. Determine qual é em média a diferença entre o tempo de execução das versões (v3) e (v3c).
    7. Etapa 4: Produza uma versão (v4) de (v1) implementando o uso da mediana de três como pivô e o triparticionamento. Determine qual é em média a diferença entre o tempo de execução das versões (v1), (v2), (v3) e (v4). Chame de (v*) a melhor dentre estas quatro versões.
    8. Etapa 4c: Produza uma versão (v4c) de (v4) com o corte para vetores pequenos, como na Etapa 1c do Mergesort. Determine qual é em média a diferença entre o tempo de execução das versões (v1), (v1c), (v2c), (v3c), (v4c) e (v*).
    9. Etapa 5: Conclua qual é a melhor versão do quicksort que você obteve destes experimentos, e escreva um breve relatório justificando a sua conclusão.

  • Heapsort
    
    1. Etapa 1: Implemente uma versão simples do heapsort, como a da aula (com o desce-heap recursivo). Teste essa versão (v0) contra a versão (v1) sem recursão de cauda (com o desce-heap não recursivo). Determine qual é em média a diferença entre o tempo de execução das versões (v0) e (v1).
    2. Etapa 2: Produza uma versão (v2) de (v1) que, após remover o máximo do heap e substitui-lo pela última chave do heap, desce esta chave no heap, sem compará-la às demais, até uma folha (sem destruir o heap), e depois executa um sobe-heap nesta folha, como explicado em aula. Determine qual é em média a diferença entre o tempo de execução das versões (v1) e (v2).
    3. Etapa 3: Conclua qual é a melhor versão do heapsort que você obteve destes experimentos, e escreva um breve relatório justificando a sua conclusão.

• Testes experimentais

  Por segurança, mantenha sempre após a ordenação um teste que confirma que o vetor foi ordenado, ou aborta o programa com uma mensagem de erro adequada.

  Para concluir fatos sobre a média, faça algo na seguinte linha. Gere 10 vetores aleatórios dos tamanhos N = 1000, 10000, 100000, 1000000, execute os algoritmos em cada um dos 10 vetores de um tamanho e tire a média do tempo de execução dos 10 vetores, obtendo 4 médias (uma para cada valor de N).

  Faça testes com vetores sem repetição (permutações de 1 a n escolhidas uniformemente), e testes com vetores com chaves repetidas, preenchidos com valores escolhidos aleatoriamente de algum intervalo de inteiros. Altere a porcentagem de elementos repetidos diminuindo ou aumentando o tamanho desse intervalo, e veja como isso afeta os seus testes.

  Faça mais testes. Por exemplo, tente ver o efeito do tamanho do cache da sua máquina nos algoritmos implementados. Faça mais implementações (por exemplo, implemente o mergesort não recursivo e o compare também). Enfim, divirta-se e aprenda o máximo com os seus experimentos.