ATPS Classificaçao E Pesquisa

1º Etapa do ATPS

PASSO 1

O desafio proposto ao grupo foi desenvolver um programa que realiza de acordo com a escolha do usuário buscas com algoritmos diferentes na mesma tabela de dados.

O desafio possui duas funções que geram números aleatórios do tipo DOUBLE e do tipo INTEIRO, portanto as duas tabelas distintas a serem preenchidas.

Abaixo temos as linhas de códigos que invocam essas funções gerando números para preencher a totalidade das tabelas.

Laço de repetição para preencher as duas tabelas do desafio

for (i = 0; i < MAX; i++)

{

/*Chamada da função que gera números Double*/

resultadoDouble = unif(&seed, lowDouble, highDouble);

tabelaDouble[i] = resultadoDouble;

/*Chama da função que gera número Inteiros*/

resultadoInt = inteiros_unif(&seed, lowInt, highInt);

tabelaInt[i] = resultadoInt;

}

for (i = 0; i < MAX; i++)

{

/*Chamada da função que gera números Double*/

resultadoDouble = unif(&seed, lowDouble, highDouble);

tabelaDouble[i] = resultadoDouble;

/*Chama da função que gera número Inteiros*/

resultadoInt = inteiros_unif(&seed, lowInt, highInt);

tabelaInt[i] = resultadoInt;

}

Uma forma bem comum, as tabelas serão preenchidas de acordo com o laço de repetição a quantidade de repetições será definida através da linha #define MAX 100 onde esse valor será alterado no decorrer da resolução para que testes com tabelas maiores sejam possíveis, sem necessidade de alterar profundamente o programa.

O desafio possui uma tabela onde define alguns parâmetros para testar os algoritmos um deles é o tamanho das duas tabelas sendo os valores de 100, 1000, 10000 e 100000000. O argumento a ser encontrado sempre será o número 87.

Vamos iniciar os testes com o tamanho da tabela em 100 posições. Para isso precisamos apenas definir MAX 100.

Menu inicial do programa

No menu inicial do programa o usuário vai escolher entre as buscas que ele deseja realizar. Vamos supor que o mesmo usuário vai realizar os testes por ordem, portanto vamos escolher a opção 1- Busca Sequencial.

Novo menu apresentado após escolhermos 1- Busca Sequencial

Feito as nossa escolha o programa irá exibir um novo menu, agora solicitando o tipo de valor que deseja buscar. Importante ressaltar que nesse ponto as tabelas já estão preenchidas com os dados, conforme o código mostrado no início desse documento. Vamos procurar o argumento na tabela com valores Double.

Resultado da busca pelo argumento na tabela Double

Como já esperávamos o argumento não existe na tabela Double. Podemos verificar também o número de comparações feitas pelo algoritmo que é o tamanho total da nossa tabela (100). Nesse exemplo de devido ao tamanho pequeno, a busca não demorou em ser realizada. Notamos isso na diferença de tempo impressa na tela. O processo aconteceu tão rapidamente que o programa nem conseguiu cronometrar o tempo entre a chamada da função de busca e seu retorno.

Vamos repetir o passo anterior, mas escolhendo busca de valores inteiros.

Resultado da busca pelo argumento na tabela de inteiro

Nesse exemplo o argumento também não foi encontrado e da mesma maneira como aconteceu na tabela Double, não foi possível marcar o tempo da execução do programa.

Nesse ponto o grupo fez uma observação. Com o tamanho das tabelas contendo 100 posições o resultado sempre será o mesmo. Se usando o algoritmo de busca mais simples e menos eficaz os resultados permaneceram em zero. Realizar testes com busca sequencial com sentinela ou busca binária é totalmente desnecessário já que com poucos dados o primeiro algoritmo resolveu muito bem o problema e de forma instantânea.

Vamos passar para o próximo número que a tabela do desafio propõe onde o tamanho das tabelas int e double sejam de 1000 posições. E vamos realizar novos testes.

Mesmo cm a tabela maior, o resultado se mantem o mesmos

Mesmo modificando o tamanho das tabelas para 1000 a busca mais simples nos mostrou os mesmo resultados. Chegamos a conclusão que, mesmo com o tamanho dez vezes maior em relação ao teste anterior, o número 1000 ainda não é o suficiente para vermos diferença nos algoritmos de busca.

Vamos aumentar o tamanho das tabelas para 10000 e realizar novos testes.

Ainda assim com 10 a busca mais simples ainda continua sendo eficiente

Mesmo com tabelas com 10 posições, a busca mais simples ainda continua sendo eficaz.

Vamos passar para o último tamanho descrito no desafio 100 posições.

Resultado da busca sequencial com 100 posições

Se olharmos o tempo de busca, ainda continua sendo muito rápido para que haja tempo de calcular diferença. Porém agora notamos que o argumento existe na tabela. E isso também implica na eficiência da busca.

Se olhar o resultado da imagem acima, quando realizamos a busca por um argumento inteiro o mesmo foi encontrado na posição 14410, porém o algoritmo fez 100 comparações, mesmo após ter encontrado o argumento. Isso mostra que apesar de funcionar bem a busca sequencial por si só executa um trabalho desnecessário.

Vamos executar a mesma pesquisa com a busca sequencial com sentinela.

Busca sequencial com sentinela

Com esse algoritmo podemos

...