IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C Discussion :

Algorithme Shellsort, probleme de lenteur en utilisant les pointeurs


Sujet :

C

  1. #1
    Membre éclairé
    Homme Profil pro
    Autres
    Inscrit en
    Août 2008
    Messages
    39
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 46
    Localisation : France, Var (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Autres

    Informations forums :
    Inscription : Août 2008
    Messages : 39
    Par défaut Algorithme Shellsort, probleme de lenteur en utilisant les pointeurs
    Bonjour à ceux qui vont me lire.

    En utilisant le tri de shell avec un tableau de pointeur sur un tableau de structure, je remarque que mon tri est 2 fois plus rapide en faisant le tri sur le tableau de structure plutot que sur celui avec les pointeurs.
    La difference est plus marqué sur une tablette ou c'est 4 fois plus rapide.

    Je ne me l'explique pas, avec qsort par contre tout va bien. Si un programmeur C voit ou je fais une erreur ou alors si c'est normal. Il y a l'algorithme pour le tri de shell sur tableau de structure pour trier des chaines de caracteres, et l'autre qui le fait en utilisant les pointeurs.


    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
     
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <time.h>
     
    typedef struct _ch ch;
    typedef struct _idxch idxch;
     
    struct _ch
    {
    	char c[26];
    };
     
    struct _idxch
    {
    	ch ** idx;
    };
     
    int compare(const void* str1,const void* str2)
    {     
         const char **pp1=(const char**)str1;
         const char **pp2=(const char**)str2;
         return(strcmp(*pp1,*pp2));
    }
     
     
    void shellsort( ch * arr, int num )
    {
    	ch * b;
    	b = malloc( 1 * sizeof( ch ) );
     
        int i, j, k;
        for (i = num / 2; i > 0; i = i / 2)
        {
            for (j = i; j < num; j++)
            {
                for(k = j - i; k >= 0; k = k - i)
                {
                    if ( strcmp( arr[k+i].c, arr[k].c ) >= 0 )
                        break;
                    else
                    {
                        b[0] = arr[k];
                        arr[k] = arr[k+i];
                        arr[k+i] = b[0];
                    }
                }
            }
        }
    free ( b );
     
    }
     
    void shellsortpointeur( ch ** id, int num )
    {
    	idxch b;
    	b.idx = malloc( 1 * sizeof( * b.idx ) );
     
        int i, j, k;
        for (i = num / 2; i > 0; i = i / 2)
        {
            for (j = i; j < num; j++)
            {
                for(k = j - i; k >= 0; k = k - i)
                {
                    if ( strcmp( id[k+i]->c, id[k]->c ) >= 0 )
                        break;
                    else
                    {
                        b.idx[0] = id[k];
                        id[k] = id[k+i];
                        id[k+i] = b.idx[0];
                    }
                }
            }
        }
    free ( b.idx );
     
    }
     
    int main( void )
    {
    	int i, j, y;
     
    	ch * a;
    	a = malloc( 1000000 * sizeof( * a ) );
     
    	idxch id;
    	id.idx = malloc( 1000000 * sizeof( * id.idx ) );
     
    	for( y = 0 ; y < 1000000 ; y++ )
    	{
    		id.idx[y] = &a[y];
    	}
     
    	strncpy( a[0].c, "Souris", 25 + 1 );
    	strncpy( a[1].c, "Yetenue", 25 + 1 );
    	strncpy( a[2].c, "Iuoi", 25 + 1 );
    	strncpy( a[3].c, "Juissance", 25 + 1 );
    	strncpy( a[4].c, "Dptimal", 25 + 1 );
    	strncpy( a[5].c, "Xaturel", 25 + 1 );
    	strncpy( a[6].c, "Horoder", 25 + 1 );
    	strncpy( a[7].c, "Myon", 25 + 1 );
    	strncpy( a[8].c, "Erypton", 25 + 1 );
    	strncpy( a[9].c, "Wournee", 25 + 1 );
    	strncpy( a[10].c, "Ammersion", 25 + 1 );
    	strncpy( a[11].c, "Fector", 25 + 1 );
    	strncpy( a[12].c, "Sorille", 25 + 1 );
    	strncpy( a[13].c, "Froid", 25 + 1 );
    	strncpy( a[14].c, "Uclipse", 25 + 1 );
    	strncpy( a[15].c, "Qirecteur", 25 + 1 );
    	strncpy( a[16].c, "Castor", 25 + 1 );
    	strncpy( a[17].c, "Orumeux", 25 + 1 );
    	strncpy( a[18].c, "Tmerica", 25 + 1 );
    	strncpy( a[19].c, "Bldorande", 25 + 1 );
     
    	printf( "%ld %ld\n", sizeof( a[0] ), sizeof( id.idx[0] ) );
    	printf( "%s %s\n\n", a[0].c, id.idx[0]->c );
     
    	j = 0;
    	for( i = 20 ; i < 1000000 ; i++)
    	{
    		if( j < 20 )
    		{
    			strncpy( a[i].c, a[j].c, 25 + 1 );
    			j++;
    		}
    		else
    		{
    		  j = 0;
    		  strncpy( a[i].c, a[j].c, 25 + 1 );
     
    		}
    	}
     
     
    	for( i = 0 ; i < 20 ; i++)
    	{
    		printf( "- %s -", a[i].c );
    	}
    	printf( "\n\n" );
     
    	int ( * cmp )( const void  *, const void * );
    	cmp = &compare;
     
    	long debut = clock();
     
    	//shellsort( a, 1000000 ); // 2eme
    	shellsortpointeur( id.idx, 1000000 );
    	//qsort( id.idx, 1000000, sizeof( * id.idx ), cmp );
     
    	long fin = clock();
     
    	long duree = ( fin - debut) / ( CLOCKS_PER_SEC / 1000 );
    	printf( "Temps du tri : %ld ms\n\n", duree );
     
    	for( i = 0 ; i < 20 ; i++)
    	{
    		printf( "- %s -", a[i].c );
    	}
    	printf( "\n\n\n" );
     
    	for( i = 0 ; i < 20 ; i++)
    	{
    		printf( "- %s -", id.idx[i]->c );
    	}
    	printf( "\n\n" );
     
    	printf( "Temps d'execution total : %ld\n",  clock() );
     
     
    	free( id.idx );
    	free( a );
     
     
     
     
    return 0;
    }

  2. #2
    Membre Expert
    Inscrit en
    Mars 2005
    Messages
    1 431
    Détails du profil
    Informations forums :
    Inscription : Mars 2005
    Messages : 1 431
    Par défaut
    Je n'ai pas vérifié la validité de ton implémentation ni de ton jeu de données mais sur ma présente machine (i7 64-bit) le temps d'exécution des deux versions est rigoureusement similaire :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    shellsort: 96 ms
    ----------
    shellsortpointeur: 94 ms
    ----------
    qsort: 17 ms
    Ceci pour 1000 exécutions consécutives (afin de lisser un tant soit peu le bruit dû aux cache misses) en modifiant la partie de test comme suit :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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
    32
        long long duree = 0;
        for (size_t i = 0; i < 1000; ++i)
        {
            const long debut = clock();
     
            shellsort( a, 1000000 ); // 2eme
     
            duree += (clock() - debut);
        }
        printf( "shellsort: %lld ms\n----------\n", duree / CLOCKS_PER_SEC);
     
        duree = 0;
        for (size_t i = 0; i < 1000; ++i)
        {
            const long debut = clock();
     
            shellsortpointeur( id.idx, 1000000 );
     
            duree += (clock() - debut);
        }
        printf( "shellsortpointeur: %lld ms\n----------\n", duree / CLOCKS_PER_SEC);
     
        duree = 0;
        for (size_t i = 0; i < 1000; ++i)
        {
            const long debut = clock();
     
            qsort( id.idx, 1000000, sizeof( * id.idx ), cmp );
     
            duree += (clock() - debut);
        }
        printf( "qsort: %lld ms\n", duree / CLOCKS_PER_SEC);
    Compilé avec : gcc -std=c11 -pedantic -Wall -Wextra -O2 shell.c .

  3. #3
    Membre éclairé
    Homme Profil pro
    Autres
    Inscrit en
    Août 2008
    Messages
    39
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 46
    Localisation : France, Var (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Autres

    Informations forums :
    Inscription : Août 2008
    Messages : 39
    Par défaut
    Tes résultats m'etonnes.

    Sur mon PC fixe i7 64 bits c'est 386ms
    Sur le portable i7 64bits c'est 790ms
    Tablette 32 bits c'est 3600ms
    Par contre la version sans pointeur sur tablette c'est 1000ms
    Toujours pour 1 000 000 d'elements de mon coté, je comprend pas cette difference.

  4. #4
    Membre Expert
    Inscrit en
    Mars 2005
    Messages
    1 431
    Détails du profil
    Informations forums :
    Inscription : Mars 2005
    Messages : 1 431
    Par défaut
    As-tu activé les optimisations ? As-tu effectué plusieurs tris au sein du même processus ?

    Tu ne peux pas tirer de résultats à partir d'une seule exécution de chaque algorithme (ou alors sur une très grande quantité de données, générées via /dev/urandom par exemple), il suffit qu'un autre processus se mette en branle sur la machine pour tout fausser. Même mon test n'est en rien concluant vu que les données sont entièrement triées dès après la première itération.

  5. #5
    Membre éclairé
    Homme Profil pro
    Autres
    Inscrit en
    Août 2008
    Messages
    39
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 46
    Localisation : France, Var (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Autres

    Informations forums :
    Inscription : Août 2008
    Messages : 39
    Par défaut
    Oui j'ai les memes optimisations que toi mis à part le standard c99 pour moi.

    Je sais que je ne peu me fier à un resultat, mais il se repete sur plusieurs machines differentes. Toutes sous linux debian et android pour la tablette.

    L'ecart est trop important, et pourquoi le resultat avec le tableau de pointeurs et moins performants ?


    EDIT : Ce qui m'etonne est juste la difference entre le tri en passant par le tableau de pointeurs plus lent que le tri sur le tableau de structure lui meme.
    Bien entendu chaque algorithme est testé à chaque fois apres recompilation et chacun leur tour sur des donnees non triés.

  6. #6
    Expert confirmé

    Avatar de fearyourself
    Homme Profil pro
    Ingénieur Informaticien Senior
    Inscrit en
    Décembre 2005
    Messages
    5 121
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Ingénieur Informaticien Senior
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2005
    Messages : 5 121
    Par défaut
    Comme Matt le dit, c'est très difficile de tirer des conclusions sur ces tests. Il se peut que le fait que tu as une indirection en plus dans le cas de pointeur provoque ce souci de performance. A chaque fois que tu fais ton accès
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
     
     if ( strcmp( id[k+i]->c, id[k]->c ) >= 0 )
    Tu fais les accès tableaux pour trouver le pointeur et ensuite deux chargements de plus pour trouver les c, et enfin on peut faire la comparaison.

  7. #7
    Membre éclairé
    Homme Profil pro
    Autres
    Inscrit en
    Août 2008
    Messages
    39
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 46
    Localisation : France, Var (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Autres

    Informations forums :
    Inscription : Août 2008
    Messages : 39
    Par défaut
    Merci pour avoir jeté un oeil. Je marque comme résolu, c’était une observation dont je voulais comprendre le résultat.

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Réponses: 3
    Dernier message: 19/09/2009, 16h37
  2. Réponses: 8
    Dernier message: 13/11/2008, 21h28
  3. Comment utiliser les pointeurs
    Par jeje86 dans le forum Macros et VBA Excel
    Réponses: 1
    Dernier message: 27/08/2008, 13h24
  4. Quand utiliser les pointeurs ?
    Par kedare dans le forum Qt
    Réponses: 4
    Dernier message: 22/08/2007, 11h50

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo