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:
1-
int a=10,b=15;
a=b+a;
b=a-b;
a=a-b;
2-
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:
[code]#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;
}[/code]
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?