Performance em ordenação em C ANSI - com e sem variável auxiliar

24 de abril de 2010 8 respostas

Jokabeludoido 24 de abril de 2010

Sou monitor de uma disciplina de algoritmos e surgiu uma dúvida em relação diferentes abordagens para troca de valores entre duas variáveis - com e sem utilização de variável auxiliar. Mesmo sabendo que o uso de variável auxiliar é aconselhável, uma vez que facilita a leitura do código, fiquei pensando em relação à performance das duas abordagens. Em uma delas, a troca ocorre através de 3 operações aritméticas (uma soma e duas subtrações), na segunda ocorre através da movimentação de valores entre 3 variáveis. Seguem as duas abordagens:

int a=10,b=15;
a=b+a;
b=a-b;
a=a-b;

int a=10,b=15,aux;
aux = a;
a = b;
b = aux;

Para medir a performance dessas abordagens de trocas de variáveis, resolvi testá-las em um contexto em que elas são realizadas muitas vezes. Nada melhor que o bom e velho bubble sort para isso :-)
Segue abaixo o código que fiz:

#include <time.h>
#include <stdlib.h>
#include <stdio.h>

#define TAMANHO 10000
#define VALOR_MAXIMO 10

int main()
{
    clock_t inicio,fim;
    double total1,total2;
    int a[TAMANHO],copia1[TAMANHO],copia2[TAMANHO];
    int i,j,aux,r;
    
    srand(time(0)); //gera uma nova cadeia de n?meros aleat?ria
    
    printf("Produzindo numeros aleatorios\n");
    
     for(i = 0; i < TAMANHO; i++)
     {
         r = (int) (rand() / (double) RAND_MAX * (VALOR_MAXIMO + 1));   
         a[i] = r;
     }
    
    printf("\tNumeros aleatorios produzidos\n");
     
     printf("Fazendo duas copias\n");
     
     for(i = 0; i < TAMANHO; i++)
     {
         copia1[i] = copia2[i] = a[i];
     }
     printf("\tCopias feitas\n");
     
     printf("Ordenacao sem variavel auxiliar\n");
     
     inicio = clock(); 
     for(i=0; i < TAMANHO; i++)
     {
         for(j=i+1 ; j<TAMANHO; j++)
         {
             if (copia1[j]<copia1[i])
             {
                copia1[i]=copia1[j]+copia1[i];
                copia1[j]=copia1[i]-copia1[j];
                copia1[i]=copia1[i]-copia1[j];
             }                         
         }
     }
     fim = clock();
     total1 = (double)((double)(fim-inicio)/(double)(CLOCKS_PER_SEC/1000.0));
     
     printf("\tOrdenacao sem variavel auxiliar demora %.0f \n",total1);
     
     printf("Ordenacao com variavel auxiliar\n");
       
     inicio = clock(); 
     for(i=0; i < TAMANHO; i++)
     {
         for(j=i+1 ; j<TAMANHO; j++)
         {
             if (copia2[j]<copia2[i])
             {
                aux = copia2[j];
                copia2[j] = copia2[i];
                copia2[i] = aux;   
             }                         
         }
     }
     fim = clock();
     total2 = (double)((double)(fim-inicio)/(double)(CLOCKS_PER_SEC/1000.0));
     
     printf("\tOrdenacao com variavel auxiliar demora %.0f \n",total2);
    
    system("pause>>null");
    return 0;
}

Notem que tentei usar a tomada de tempo em milissegundos, a partir da função clock() do C e da variável CLOCKS_PER_SEC. Não sei se está correto.
A minha surpresa foi que às vezes executo e a primeira abordagem é mais rápida, às vezes a segunda é muito mais rápida, às vezes a diferença entre ambas é despezível. Por que isso ocorre? Errei a forma de tomar o tempo de execução?

Logicamente falando, em termos de arquitetura, qual das abordagens deveria ser mais rápida?

8 Respostas

Adelar 24 de abr. de 2010

Olá,
a primeira abordagem está incorreta. Ela funciona para valores pequenos, mas para valores grandes (que se aproximam do limite do tipo) pode haver overflow. Há uma forma de fazer a troca sem variável auxiliar (não me lembro agora como era - depois vou dar uma procurada daí posto aqui), mas não é recomendada por depender de tipos inteiros do C.

Att.

Adelar 24 de abr. de 2010

Olá,
como havia dito, há uma forma de fazer swap sem o uso de variável auxiliar. Segue o código:

#include <stdio.h>

int main(){
	int a = 1;
        int b = 2;
	printf("%d %d\n", a, b);
        a = a ^ b;
        b = a ^ b;
        a = a ^ b;
	printf("%d %d\n", a, b);
}

Att.

peczenyj 24 de abr. de 2010

Ola

Compare o assembly de cada opção, quantas operações vc tem em cada forma?

Quantos acessos a memoria? a variavel temporaria é proxima a ponto de cair no cache L3?

Isso tudo conta, mas acredito que o impacto é minimo em um problema trivial.

Jokabeludoido 24 de abr. de 2010

Adelar:

Olá, como havia dito, há uma forma de fazer swap sem o uso de variável auxiliar. Segue o código:

#include <stdio.h>

int main(){
	int a = 1;
        int b = 2;
	printf("%d %d\n", a, b);
        a = a ^ b;
        b = a ^ b;
        a = a ^ b;
	printf("%d %d\n", a, b);
}

Att.

É mesmo! Bem lembrado! Eu havia esquecido desta forma de swap. Valeu.
Além disso, não tinha me dado conta do problema de overflow na representação de inteiros, usando a abordagem baseada em operações aritméticas, quando os valores estão próximos ao limite...Valeu mesmo!

Jokabeludoido 24 de abr. de 2010

peczenyj:
Ola

Compare o assembly de cada opção, quantas operações vc tem em cada forma?

Quantos acessos a memoria? a variavel temporaria é proxima a ponto de cair no cache L3?

Isso tudo conta, mas acredito que o impacto é minimo em um problema trivial.

Parece-me que essas abordagens que não usam variável auxiliar precisam necessariamente:
1-Mover o valor da posição de memória de uma das variáveis para um registrador.
2-Mover o segundo valor, da memória para outro registrador.
3-Operar conteúdos de ambos registradores
4-Mover o resultado do acumulador para o endereço de memória que acumulará a soma.

Isso para cada uma das operações entre variáveis. Enquanto para a operação com uso de variável auxiliar eu realizo 3 movimentos de valores entre endereços de memória.

É isso?

Mesmo assim, não sei qual das operações é mais cara.

Outra coisa. Meu método de tomada de tempo está correto? Cada vez que executo a relação de perfomance entre as abordagens muda. Às vezes a primeira é mais rápida que a segunda, às vezes, vice-versa…Como normalizar isso?

Grato pela atenção!

Jokabeludoido 26 de abr. de 2010

entanglement 26 de abr. de 2010

10000 é um tamanho muito pequeno para você fazer tal benchmark (mesmo para um método tosquíssimo de ordenação, como o bubblesort). Benchmarks bem feitos precisam de tratamento estatístico, como qualquer medição que se preze. Rodar um benchmark 1 vez só simplesmente não leva a absolutamente nenhuma conclusão.
No seu caso em particular, eu diria que (se ligarmos a otimização do compilador) o tempo gasto seria o mesmo em média.

Jokabeludoido 26 de abr. de 2010

entanglement:
10000 é um tamanho muito pequeno para você fazer tal benchmark (mesmo para um método tosquíssimo de ordenação, como o bubblesort). Benchmarks bem feitos precisam de tratamento estatístico, como qualquer medição que se preze. Rodar um benchmark 1 vez só simplesmente não leva a absolutamente nenhuma conclusão.
No seu caso em particular, eu diria que (se ligarmos a otimização do compilador) o tempo gasto seria o mesmo em média.

Sei disso meu amigo…Minha intenção não era fazer um benchmark estrito…Quer dizer, querer até quero, mas não tenho tempo pra isso. Então rodei meu teste várias vezes e vi que em todas elas a versão que usa manipulação aritmética. Sem dúvidas não é suficiente para determinar a diferença de performance no caso geral, mas dá uma boa sugestão, indicando esta abordagem como a mais rápida em todos os testes.

Mas minhas dúvidas permanecem…Usei um método adequado para tomada de tempo? Não tenho tanta familiaridade assim com a linguagem C.

Além disso…Não consegui entender por que a utilização de operações aritméticas confere mais velocidade que a utilização de operações XOR (mesma quantidade) e que a utilização de transferência de valores para uma variável auxiliar…Em termos de arquitetura, alguém está por dentro de por que isto acontece?

Grato…

Criado 24 de abril de 2010

Ultima resposta 26 de abr. de 2010

Respostas 8

Participantes 4

8 Respostas

Topicos relacionados