Algorithme Shellsort, probleme de lenteur en utilisant les pointeurs

Version imprimable

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:

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;
}

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:

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:

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 .

15/02/2017, 12h07
Proteiforme

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.
15/02/2017, 12h19
Matt_Houston

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.
15/02/2017, 12h28
Proteiforme

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.
18/02/2017, 07h49
fearyourself
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:

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.
18/02/2017, 09h22
Proteiforme

Merci pour avoir jeté un oeil. Je marque comme résolu, c’était une observation dont je voulais comprendre le résultat.