Jump to content
telele97

Eficiencia de programas

Recommended Posts

telele97

Pretendo fazer um programa que faça a intersecção dos produtos comuns que existem em 2 supermercados e depois quero genralizar para vários. Esses produtos são representados por uma lista com numeros. O código que eu tenho é o seguinte:

 lista * in2(lista *lista1, lista * lista2){
 lista * inter=NULL;
 lista *aux;
 lista *aux2;
 if(lista1==NULL || lista2==NULL)
   return NULL;
 for(aux=lista1;aux!=NULL;aux=aux->proxima){
   for(aux2=lista2;aux2!=NULL;aux2=aux2->proxima){
     if(aux->indice==aux2->indice){
       inter=insere(aux->indice, inter);
       break;
     }
   }
 }
 return inter;
}

lista * intk(lista **tabela listas, int k){
 int i;
 lista *inter;
 if(k==1)
   return *tabela[0];
 for(i=0;i<k;i++){
   inter=in2(*tabela[i], *tabela[i+1]);
 }
 return inter;
}

gostava que alguem me pudesse ajudar e me indique se existe alguma maneira de fazer isto de uma forma mais eficiente e mais rápida.

Outra questão, vi em alguns sitios para ver isto da eficiencia se costuma calcular a complexidade temporal alguem me pode dar umas dicas em relação a este assunto?

Edited by Rui Carlos
geshi

Share this post


Link to post
Share on other sites
HappyHippyHippo

Pretendo fazer um programa que faça a intersecção dos produtos comuns que existem em 2 supermercados e depois quero genralizar para vários. Esses produtos são representados por uma lista com numeros. O código que eu tenho é o seguinte:

gostava que alguem me pudesse ajudar e me indique se existe alguma maneira de fazer isto de uma forma mais eficiente e mais rápida

se tiveres as listas ordenadas só necessitas de percorrer as listas uma vez e ao mesmo tempo, logo consegues ter um algoritmo de ordem O(n)

Outra questão, vi em alguns sitios para ver isto da eficiencia se costuma calcular a complexidade temporal alguem me pode dar umas dicas em relação a este assunto?

http://pt.wikipedia.org/wiki/Complexidade_computacional


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
telele97

se tiveres as listas ordenadas só necessitas de percorrer as listas uma vez e ao mesmo tempo, logo consegues ter um algoritmo de ordem O(n)

http://pt.wikipedia.org/wiki/Complexidade_computacional

Certo, mas no meu caso as listas não estão ordenadas e o meu algoritmo tem complexidade O(n²) certo? Compensará ordená-las e depois aplicar esse algoritmo que tu disseste?

Outra coisa o meu algoritmo para intersectar as várias lista pode ser feito assim?

Share this post


Link to post
Share on other sites
HappyHippyHippo

Certo, mas no meu caso as listas não estão ordenadas e o meu algoritmo tem complexidade O(n²) certo? Compensará ordená-las e depois aplicar esse algoritmo que tu disseste?

sim


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
telele97

sim

Sim para as duas perguntas? Só não percebi como é que posso percorrer as lista apenas uma vez :S. Imagina "fixo" o primeiro elemento de uma lista e depois vou procurar na outra se também existe? E se encontrar passo para o outro elemento?

Share this post


Link to post
Share on other sites
HappyHippyHippo

sim para a primeira, a segunda só verificando o código

algoritmo de intersecção de listas ordenadas

indice1 = 0
indice2 = 0
enquando (indice1 < tamanho da lista1) e (indice2 < tamanho da lista2)
 distancia = lista1[indice1] - lista2[indice2]
 se distancia == 0
   adicionar o valor à lista de interseção
   incrementar indice1
   incrementar indice2
 se distancia < 0
   incrementar indice1
 se distancia > 0
   incrementar indice2


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
telele97

sim para a primeira, a segunda só verificando o código

algoritmo de intersecção de listas ordenadas

indice1 = 0
indice2 = 0
enquando (indice1 < tamanho da lista1) e (indice2 < tamanho da lista2)
 distancia = lista1[indice1] - lista2[indice2]
 se distancia == 0
   adicionar o valor à lista de interseção
   incrementar indice1
   incrementar indice2
 se distancia < 0
   incrementar indice1
 se distancia > 0
   incrementar indice2

Certo acho que conseguir fazer mais ou menos esse código:

lista * interseccao2(lista *lista1, lista * lista2){
 lista *inter=NULL;
 lista *aux=lista1;
 lista *aux2=lista2;
 int dist=0;
 while(aux->proxima!=NULL){
   aux=aux->proxima;
 }
 while(aux2->proxima!=NULL){
   aux2=aux2->proxima;
 }
 mergesort(lista1,lista1->indice,aux->indice);
 mergesort(lista2,lista2->indice,aux2->indice);
 if(lista1==NULL || lista2==NULL)
   return NULL;
 aux=lista1;
 aux2=lista2;
 while(aux!=NULL && aux2!=NULL){
   dist=(aux->indice)-(aux2->indice);

   if(dist==0){
     inter=insere(aux->indice, inter);
     aux=aux->proxima;
     aux2=aux2->proxima;
   }else if(dist<0){
     aux=aux->proxima;
   }else {
     aux2=aux2->proxima;
   }
 }
 return inter;
}

agora tenho é um problema para escolher o algoritmo de ordenação em causa.

Suponhamos que uso o

-quicksort: -pior caso O(n2) e caso médio O(n log(n))

No pior fico com: O(2n2) da ordenação das duas listas mais O(n) do meu algoritmo de intersecção. Não sei se estou a fazer isto bem mas neste caso dava O(2n2+n) que é pior do que eu tinha.

Agora no caso médio tinha O(2nlogn)+O(n) que é bastante melhor do que eu tinha

-mergesort- este foi o melhor algoritmo que eu consegui encontrar mas também foi o que dá mais trabalho a implementar. Este algoritmo tem como pior caso e caso médio O(nlogn) ficando assim igual ao caso médio do quicksort.

Será que a melhoria é significativa na ordenação?

Gostava de uma pequena ajuda para ver se aquelas análises que fiz ali em cima se encontram correctas.

Share this post


Link to post
Share on other sites
Rui Carlos

O quicksort é normalmente mais eficiente que o mergesort (apesar da complexidade ser ligeiramente pior).

Uma outra alternativa passa pela utilização de tabelas de hash.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.