Temps d'execution : theorie et pratique

Bonjour

J'ai codé selon deux algorithmes (le naïf et le "non naïf") un problème
classique (expliqué ci-après) et nécessitant de comparer des entiers. Le
naïf effectue 2*n comparaisons et le non naïf en effectue 25% de moins
(ie 1.5*n comparaisons). Les codes C sont simples et très similaires et
pourtant le naïf est plus rapide sur tous les tests que j'ai faits (et
pas qu'un peu : c'est de l'ordre de 50% plus rapide).

Le problème dont je parlais est le suivant : on a un tableau t de n
entiers et on veut retourner _à la fois_ le minimum et le maximum de t.

*) la méthode naïve consiste à parcourir t et
1) à comparer le minimum courant m de t à l'élément courant t[i] à
mettre à jour m si besoin
1) à comparer le maximum courant M de t à l'élément courant t[i] à
mettre à jour M si besoin
Cela fait 2 comparaisons d'entiers faites n fois donc 2*n comparaisons.
Cela fait aussi 2*n affectations au pire (en fait, n au pire).

*) la méthode astucieuse consiste à regrouper les éléments de t par
paires de deux éléments successifs, disons t[2*i] et t[2*i+1] puis
1) à comparer t[2*i] et t[2*i+1] ce qui permet de déterminer le plus
petit (mini) et le plus grand (maxi) des deux ;
2) à comparer le minimum courant m de t à mini et à mettre à jour m s'il
est "amélioré" ;
3) à comparer le maximum courant M de t à maxi et à mettre à jour M
s'il est "amélioré".
Cela fait 3 comparaisons faites n/2 fois donc 1.5*n comparaisons. Cela
fait aussi 2*n/2=n affectations au pire.


Voici le code C :


/* ==================== debut min_max_fclc.c ===================== */


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

void naif(int t[], int n, int *min, int *max)
{
int i;

int mini = t[0], maxi = t[0];

for (i = 0; i < n; i++)
{
if (t[i] < mini)
mini = t[i];
if (t[i] > maxi)
maxi = t[i];
}
*min = mini;
*max = maxi;
}

void non_naif(int *t, int n, int *min, int *max)
{
int mini = t[0], maxi = t[1];
int k = 0;

for (k = 0; k < n - 1; k += 2)
{
if (t[k] < t[k + 1])
{
if (t[k] < mini)
mini = t[k];
if (t[k + 1] > maxi)
maxi = t[k + 1];
}
else
{
if (t[k + 1] < mini)
mini = t[k + 1];
if (t[k] > maxi)
maxi = t[k];
}
}

*min = mini;
*max = maxi;
}

void test(int n)
{
int i;
int *t = malloc(n * sizeof *t);
int min, max;
clock_t now;

if (t != NULL)
{
/* Génération d'un tableau aléatoire */
srand(time(NULL));
for (i = 0; i < n; i++)
t[i] = rand();

/* Temps du naif */
now = clock();
naif(t, n, &min, &max);
printf("min=%d, max=%d\n", min, max);
printf("Temps CPU naif : %.2lf seconde.\n\n",

(double) (clock() - now) / CLOCKS_PER_SEC);


/* Temps du non naif */
now = clock();
non_naif(t, n, &min, &max);
printf("min=%d, max=%d\n", min, max);
printf("Temps CPU non naif : %.2lf seconde.\n",

(double) (clock() - now) / CLOCKS_PER_SEC);
free(t);
}
}


int main(void)
{
/* je suppose n pair pour simplifier le code de non_naif() */
test(1 << 26);
return 0;
}

/* ==================== fin min_max_fclc.c ===================== */


Voici la compilation et l'exécution :

$ gcc -O2 -W -Wall -std=c99 -pedantic -o x min_max_fclc.c
$ ./x
min=9, max=2147483640
Temps CPU naif : 0.28 seconde.

min=9, max=2147483640
Temps CPU non naif : 0.44 seconde.
$


Qui pourrait m'expliquer pourquoi le premier code est pas loin de 50%
plus rapide que le second alors que ce dernier effectue 25% de moins de
comparaisons et pas plus d'affectations (et qu'il n'y a rien d'autre
comme opérations, par exemple le nombre d'instructions if est moindre
dans le 2ème algo que dans le premier) ?