relatorio.txt 7.21 KB
Newer Older
Felipe's avatar
Felipe committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74
Objetivos e métodos:

O objetivo desse trabalho era a utilização de vários tipos de algoritmos diferentes para realizar pesquisa e ordenação de vetores, para um jogo chamado MegaQuadra, onde o próprio jogador tem controle das suas ações nas apostas.

O desafio era a otimização máxima de cada algoritmo diferente de pesquisa e ordenação para uma possível comparação no final de quais são mais eficientes em vetores de tamanho grande. Testes sempre foram realizados em quanto era implementado o programa e nem sempre batiam com o esperado. Porém com a maior eficiência em cada algoritmo atingimos um resultado aceitável com o esperado.

O programa começa sempre atualizando os dados do tamanho do vetor e valor máximo para ser gerado, tudo realizado dentro da função Setup. Como a especificação pede para um controle constante do programa, já é pedido uma forma de ordenação daquele vetor nas seguintes opção: SelectSort, BubbleSort, QuickSort recursivo e QuickSort iterativo. Após isso entramos no menu principal do programa. O vetor ordenado e desordenado pode ser sempre visualizado pelo jogador. Quando é selecionado a opção para apostar os quatro valores, o programa utiliza os algoritmos da Pesquisa Sequencial (PesqSec) e Pesquisa Binaria (PesqBin) para checar os acertos do jogador. Como é especificado que deveria ser realizado a pesquisa com ambos algoritmos, sempre é checado se o resultado encontrado pela PesqSec é o mesmo de PesqBin para mostrar a funcionalização de ambos.

Dificuldades na implementação:

Para um tratamento mais fácil no vetor, concordamos em utilizar a proposta dada em sala de aula que é deixar o primeiro elemento livre e trabalhar num vetor que vai de índice 1 até o tamanho N.

QuickSort iterativo foi o maior desafio do trabalho, precisando implementar do zero, a pilha foi a solução mais viável para um melhor desempenho. Ainda testamos a pilha com alocação estática de memoria, e os resultados de tempo foram catastróficos com quase 10 vezes mais atraso que BubbleSort e SelectSort.

Medições de tempo:

O programa possui a opção de gerar 10000 vetores diferentes e ordená-los pelos 4 algoritmos diferentes e ainda mostrar o tempo de execução de cada um. Deve ser levado em consideração que o tempo gasto para gerar cada vetor é o mesmo para o teste de cada algoritmo portanto não influencia no tempo, porém mostra que os algoritmos podiam ser mais eficientes se não precisasse gerar sempre vetores diferentes. Outro ponto é que não são os mesmo 10000 vetores para cada algoritmo, portanto pode acontecer que um algoritmo tenha mais vetores próximos do seu melhor caso aumentando o seu desempenho por isso foi realizado uma media para um melhor resultado.

Como visto nas aulas de implementação de cada algoritmo e nas aulas de complexidade. Era esperado que o BubbleSort fosse o pior algoritmo de busca seguido pelo SelectSort já que o numero de comparações e de mudanças de elementos da memoria é constante. Entre os QuickSort era difícil saber qual teriam um desempenho melhor, mas o chute era que o melhor algoritmo de ordenação seria o QuickSort recursivo.

os resultados atingiram as expectativas quando se trata de vetores grandes. Porém em vetores pequenos e médio a diferença chega a ser zero, isso quando até mesmo SelectSort em algumas vezes era o melhor algoritmo em execução. Abaixo temos uma media para vetores de 1000 elementos:

SelectSort - 42,6697514 s
BubbleSort - 98,4465192 s
QuickSort recursivo - 3,2145512 s
QuickSort iterativo - 4,1072872 s

Media para vetores de 100 elementos:

SelectSort - 0,623631 s
BubbleSort - 0,970758 s
QuickSort recursivo - 0,2953262 s
QuickSort iterativo - 0,3973928 s

Media para vetores de 10 elementos:

SelectSort - 0,064077 s
BubbleSort - 0,0769892 s
QuickSort recursivo - 0,0770102 s
QuickSort iterativo - 0,0809688 s

Observações comentadas no código C:

1- A função Limpa foi criada para limpar o buffer do teclado sempre que for necessário. Se existir algo na memoria do teclado, eventualmente, esse conteúdo poderia ser copiado em algum scanf. Portanto sempre antes de realizar a leitura de algo no teclado essa função foi chamada. Com a preocupação de que os scanfs pudessem copiar mais informação do que deveriam, limpamos o buffer.

2- A função ToLogFile é sempre chamada para a inserção dos passos seguidos no código para o log. O log será criado num arquivo a parte para melhor legibilidade do código enquanto ele é executado. O desafio que essa função gerou era que apenas strings podiam ser lidas para o log, portanto valores float/double como o tempo gasto em cada ordenação não era representado no log. Então foi criado um vetor strings auxiliar (buffer) que passava qualquer valor float/double para o formato string, com a receita de código abaixo:

sprintf (buffer, "%.2f", variavel.float);   //aqui a variável float será convertida para o vetor string buffer.

ToLogFile(buffer);   //agora passa o buffer formato string para o log.

3- Na função do QuickSort Recursivo, sempre que calculava o índice da mediana naquele caso. Era colocado o pivô na posição 1 do vetor, posição chamada de esq (esquerda), e assim a função tratava o vetor para a ordenação.

4- As implementações mostradas em sala de aula, sempre retornavam o valor que era procurado na pesquisa. Nesse caso, era preciso saber apenas se o vetor contém aquele elemento, portanto no main quando é chamada as pesquisas as funções de pesquisa são atribuídas a uma variável que checa o numero de acertos do jogador. Se fosse retornado o valor do elemento achado, seria impossível controlar o números de acertos.

5- A medição de tempo para os testes de 40 mil ordenações, para um valor mais preciso dos resultados foi feito em double. As variáveis inicio e fim controlam o clock quando são chamadas. Para calcular o tempo gasto nas ordenações é feito uma conta simples de (fim - inicio) onde cada variável guardou o valor do clock quando foi chamado. Ainda é divido pela macro CLOCKS_PER_SEC que pertence a biblioteca time.h para transformar o resultado de ns para segundos. O calculo segue a receite de codigo abaixo:

inicio = clock();						//marca o valor que era do clock quando foi chamado

/* codigo que quer ser calculado tempo*/

fim = clock();			
tempo_gasto = (double)(fim - inicio) / CLOCKS_PER_SEC;		//calcula o tempo entre as marcações do clock e calcula em segundos
printf("Tempo: %lf", tempo_gasto);

6- Como foi pedido na especificação, sempre que preciso, devia ser informado o vetor desordenado. Portanto sempre era duplicado o vetor desordenado e no seu auxiliar sempre ocorria as ordenações

7- Função já existente na linguagem C para randomizar números com um valor limite

8- Para uma visualização mais limpa e clara no terminal, decidimos sempre dar um clear na tela para um novo comando ser executado. Para isso utilizamos a função 'System("clean");' inclusa na biblioteca STDLIB.

9- A biblioteca time.h foi incluída para que toda vez que o programa fosse iniciado, no log, fosse escrito o horário de início do programa. Tornando o log ainda mais informativo e organizado para a pessoa que utilizar o programa, uma vez que se pode checar as diferentes execuções pelos horários que o programa foi executado.