Método de pesquisa com melhor desempenho de computação

ATPS – Classificação e Pesquisa – Etapa 1

Adilson Pavan RA:0901346828

Gino Cezar da Rosa Ciocari RA:901413776

Marcos A. Stecca RA:926435313

Robson J. Silva RA:901382362

Thiago Henrique da Silva RA:991002855

Campinas

2010

1 Método de busca com o melhor desempenho computacional

Considerando os parâmetros de testes definidos no ATPS, foi possível identificar que o melhor método de busca sem a ordenação dos dados é o linear com sentinela, porém se o valor procurado não estiver no vetor, o tempo e a quantidade de testes realizados serão exatamente iguais ao da busca linear, pois a chave será localizada apenas no final da base de dados.

O calculo de tempo foi realizado através da quantidade de ciclos do processador (clock), mas como a base utilizada nos testes é pequena o processo é muito rápido para realizar uma comparação precisa entre os algoritmos, alem disso foi possível notar que os valores definidos para busca no ATPS não estão disponíveis após a geração dos números aleatórios e dessa forma os algoritmos de busca não localizarão os valores o que forçara percorrer o vetor até o final.

2 Desempenho da busca binária x busca linear x busca linear com sentinela

Após a ordenação dos dados fica claro que o melhor método de busca é a binária como mostra a Figura 1, pois tanto o tempo quanto a quantidade de processamento é muito menor do que as outras técnicas de busca.

O principal ponto é se a ordenação da base de dados é viável para aplicar esse tipo de técnica, pois dependendo do tamanho da base a ordenação pode se tornar muito lenta e exigir muito processamento.

A ordenação através de algoritmos como bubblesort e seleção demonstraram bons resultados, mas ainda assim exigem mais processamento do que as buscas em bases que não foram ordenadas, porem se a ordenação for realizada periodicamente ou no momento em que os dados são inseridos a busca binária torna-se viável, pois a localização e o tempo de processamento são muito mais rápidos do que as demais técnicas.

|Tipo de teste |Tamanho Vetor |Quantidade de testes |

|Busca Linear |1.000 |1.000 |

|Busca Linear com Sentinela |1.000 |1.000 |

|Busca Binária |1.000 |9 |

|Bubble Sort |1.000 |244.968 |

|Seleção |1.000 |56.738 |

Figura 1 – Resultados dos testes realizados com os algoritmos de busca após a ordenação da base

3 Conclusão

Após a realização das baterias de testes foi possível concluir que existem algoritmos de localização e ordenação mais eficientes do que outros, porém a aplicação e a utilização de cada um depende da situação e principalmente do tamanho da base de dados que será manipulada.

Considerando os parâmetros utilizados nesses testes observamos que o melhor comportamento dos algoritmos de ordenação e seleção foram obtidos pelo método seleção e a busca binária, mas isso não significa que são os melhores para todas as situações, pois todos possuem suas particularidades e deficiências.

Anexo I

Código completo para realizar a bateria de testes descritas abaixo.

/*

Name: ATPS - Classificação e Pesquisa

Description: Bateria de testes de busca linear, linear com sentinela e binária

ordenação bubble sort e seleção

*/

#include

#include

#include

#include

#define tempo 2000

#define search_p 87

#define search_s 100001

//prototipos das funções

void bateria_testes(int tam, int t);

void linear(int n, int t, int *p_int, double *p);

void linear_sentinela(int n, int t, int *p_int, double *p);

void binaria(int n, int t, int *p_int, double *p);

void bubblesort(int n, int t, int *p_int, double *p);

void selecao(int n, int t, int *p_int, double *p);

double unif(long int *seed, double low, double high);

int inteiros_unif(long int *seed, int