ATPS Classificaçao E Pesquisa
Exames: ATPS Classificaçao E Pesquisa. Pesquise 862.000+ trabalhos acadêmicosPor: unixjbc • 30/5/2013 • 1.490 Palavras (6 Páginas) • 696 Visualizações
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
...