MELANGER N'IMPORTE QUOI
hoiby
Messages postés
3
Date d'inscription
mercredi 10 décembre 2003
Statut
Membre
Dernière intervention
11 décembre 2003
-
10 déc. 2003 à 19:14
hoiby Messages postés 3 Date d'inscription mercredi 10 décembre 2003 Statut Membre Dernière intervention 11 décembre 2003 - 11 déc. 2003 à 12:09
hoiby Messages postés 3 Date d'inscription mercredi 10 décembre 2003 Statut Membre Dernière intervention 11 décembre 2003 - 11 déc. 2003 à 12:09
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/18593-melanger-n-importe-quoi
https://codes-sources.commentcamarche.net/source/18593-melanger-n-importe-quoi
11 déc. 2003 à 12:09
Mais bon j'ai trouvé ça sympa d'utiliser qsort pour mélanger :)
11 déc. 2003 à 08:25
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;
}
10 déc. 2003 à 19:39
Par contre comme je le pensais ta méthode est plus longue. Pour la bonne et simple raison que le tri rapide n'est pas si rapide que ça...Il est en O(n.log n) en moyenne, ce qui est le mieux pour un tri. Mais au pire des cas il atteint O(n^2). Bref, tout ça pour dire que le tri reste un algo relativement lourd.
Apres des tests sur 100 000 mélanges, ma méthode se révèle être 2.5 fois plus rapide.
Mais je ne connaissais pas la fonction qsort...merci !
10 déc. 2003 à 19:14
#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;
}