Trabalho Prático 1 - Classificação e Pesquisa de Dados

Prévia do material em texto

Trabalho Prático 1 - Classificação e Pesquisa de Dados 
Rodrigo Nogueira Wuerdig 
Universidade Federal do Rio Grande do Sul 
 
 
Este trabalho demonstra um série de comparações entre os algoritmos de ordenação 
apresentados em aula. 
 
Introdução 
Para o desenvolvimento deste trabalho, foi utilizado a linguagem de programação 
C e o equipamento utilizado para os testes foi: 
 
Processador AMD FX(tm)-6300 Six-Core Processor 
RAM 8GB 
Armazenamento SSD 520MB/s RW 
OS Ubuntu 16.04 
 
 Para automatização dos testes foi desenvolvido o seguinte Shell Script: 
 
 
 
 
Onde “Rounds” é o parâmetro responsável pelo número de repetições, onde atua 
no laço do intervalo 9-19, o primeiro laço (7-39) é responsável pelo controle do 
tamanho do vetor, assim alterando o valor de “VectorSize”. Cada algoritmo pode 
receber como parâmetros o tamanho do vetor e o ​seed (ambos são controlados pelo 
script). O intervalo 21-35 é responsável por calcular a media e excluir os arquivos 
temporários, após isto os valores são armazenados no arquivo “result.cvs”, linha 37. 
 
 
Desenvolvimento do RodrigoSort 
 Tendo as fórmulas para o maior e o menor número. 
 
aior M = 2
[(A+B) + |A−B|] 
 
enor A ) aiorM = ( + B − M 
 
 
Desenvolvi um algoritmo que se ​assemelha ao BubbleSort, porém sem as 
comparações. 
 
O algoritmo funciona basicamente percorrendo o vetor e sempre escrevendo o 
maior valor no final do mesmo, porém ele “diminui” o lugar de parada do vetor, 
assim preenchendo o vetor de forma ordenada. 
Funcionamento: 
 
 
 
 
 
 
 
 
 
 
6 3 5 4 10 
I++ 
3 6 5 4 10 
I++ 
3 5 6 4 10 
I++ 
3 5 4 6 10 
J--; ​I=0; 
3 5 4 6 10 
I++ 
3 4 5 6 10 
Apesar de estar tudo ordenado, ele tem de fazer todo o procedimento de troca… 
3 4 5 6 10 
J--;​ I=0; 
3 4 5 6 10 
I++ 
3 4 5 6 10 
J--; ​I=0; 
3 4 5 6 10 
J--; ​I=0; 
3 4 5 6 10 
 
FIM DO ALGORITMO 
 
 
 
 
 
 
 
 
 
 
 
 
Execução dos Seis Algoritmos 
 
Tendo o Script que foi demonstrado durante a introdução, foi basicamente só 
executar o mesmo e aguardar aproximadamente 1h, para ter 100 resultados para 
cada tamanho de vetor e algoritmo. 
 
 
Após a execução do mesmo é gerado um arquivo “.cvs” que pode ser aberto no 
Google Sheets e foi possível conseguir a seguinte tabela: 
 
VectorSiz
e (a) IS (b) ISBIN 
(c1) 
ISBINCP 
(c2) 
ISBINMV (d) SS 2. QS 
(e) 
RodrigoSort 
Mais 
Rapido 
50 7 14 16 17 9 12 44 IS 
100 20 31 30 29 19 20 134 SS 
200 70 91 61 54 41 36 657 QS 
400 267 292 139 123 102 133 2.094 SS 
800 1.007 985 340 282 231 227 8.645 QS 
1600 3.455 2.973 875 681 514 375 21.283 QS 
3200 9.978 7.726 1.895 1.232 841 582 82.561 QS 
6400 34.478 26.675 5.839 3.177 1.694 955 328.729 QS 
12800 135.654 103.599 21.090 10.067 3.884 1.838 1.322.331 QS 
25600 553.661 415.990 81.785 36.054 9.324 3.890 5.301.581 QS 
51200 2.227.170 1.670.080 322.709 134.030 23.347 8.244 21.359.545 QS 
124000 13.105.033 9.706.495 1.847.432 738.746 44.725 21.454 124.805.283 QS 
 TEMPO EM µs! 
 
(a) IS = a) Inserção direta; 
(b) ISBIN = b) Inserção direta com busca binária fazendo os deslocamentos elemento a 
elemento; 
(c1) ISBINCP e (c2) ISBINMV = c) Inserção direta com busca binária fazendo os deslocamentos 
usando um bloco de memória, evitando, assim, copiar um elemento por vez; 
(d) SS = d) Métodos dos Incrementos decrescentes (Shellsort); 
(e) RodrigoSort = e) Implemente um algoritmo para ordenação que explore a seguinte observação 
discutida em sala: dados dois números reais A e B, o maior e o menor valor entre eles podem ser 
obtidos como Maior = [(A+B)+|A-B|]/2 e menor = (A+B)-Maior = [(A+B)-|A-B|]/2. 
 
Resultados 
 
O resultado já era esperado, porém o impacto visual é grande. Mesmo sabendo 
que o algoritmo que eu desenvolvi não fosse tão bem aprimorado, achava que ele 
ficaria mais próximo da Inserção Direta. Porém para melhorar averiguar o 
desempenho dos algoritmos plotei o gráfico distribuídos em segmentos do tamanho 
do vetor. 
 
 
 
 
Comparação entre o memcpy() e o memmove()​:
 
Acredito que o ​memcpy tenha tido um desempenho pior que o ​memmove pelo fato 
de eu ter usado um vetor auxiliar para realizar o deslocamento. 
 
 
memcpy() 
 
memmove()