MELANGER N'IMPORTE QUOI

Commentaire de hoiby le 10/12/2003 19:14:34

Salut, moi j'ai trouvé une autre solution (je pense qu'elle est plus perfomante en terme de vitesse, mais j'en suis pas sûr).

#include <stdlib.h>

int compare( const void* arg1, const void* arg2 ){ return (rand()+1)<<31; }

int main(int argc, char* argv[]){

  int nIndex[]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31};

  qsort(nIndex,sizeof(nIndex)/sizeof(*nIndex),sizeof(*nIndex),compare);
  return 0;
}

Commentaire de garslouche le 11/12/2003 08:25:20

Ah ... en fait c'est plus vicieux que je croyais...
D'abord j'avais fait ce test en debug en pas en release. Et en release on arrivait à une vitesse équivalente.
Par contre j'ai oublié de mettre un truc très important pour optimiser mon algo : le mot clé 'inline' (que j'ai ajouté dans la mise à jour de la source). Pour ceux qui ne connaissent pas, ça demande au compilateur de copier le contenu de la fonction à chaque appel de celle-ci. Du coup c'est plus rapide mais les EXE sont plus gros.

Et là mon algo devient environ 7 fois plus rapide en release (sur 1 million de melanges). Par contre en debug ça tourne tojours à 2.5.

Pour info voici comment j'ai fait le test :

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

#include <sys/types.h>
#include <sys/timeb.h>

int compare( const void* arg1, const void* arg2 ){ return (rand()+1)<<31; }

inline void melange(int* tableau, int nTaille)
{
int i;

for (i = 0; i<nTaille; i++)
tableau[i] = -1;

for (i = 0; i<nTaille; i++)
{
int nPos = rand() % nTaille;

while (tableau[nPos%nTaille] != -1)
nPos++;

tableau[nPos%nTaille] = i;
}

}

#define TAILLE 32
#define MELANGES 1000000

int main(int argc, char* argv[])
{
srand( (unsigned)time( NULL ) );

_timeb t0, t1, t2;

_ftime(&t0);

// Premiere méthode
{
int nIndex[TAILLE];
for (int i = 0; i<MELANGES; i++)
melange(nIndex, TAILLE);
}

_ftime(&t1);

// Deuxieme méthode
{
int nIndex[]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31};
for (int i = 0; i<MELANGES; i++)
qsort(nIndex,sizeof(nIndex)/sizeof(*nIndex),sizeof(*nIndex),compare);
}

_ftime(&t2);


// Calcul des durées
int test1 = (t1.time-t0.time)*1000 + (t1.millitm-t0.millitm);
int test2 = (t2.time-t1.time)*1000 + (t2.millitm-t1.millitm);

printf("##### 1 000 000 itérations #####
Premiere méthode : %d ms
Seconde méthode  : %d ms
Le premier test est %f fois plus rapide
", test1, test2, test2/(float)test1);

system("pause");

return 0;
}