Incohérences de performances
Bonjour,
voilà je faisais tout simplement un code qui calcule la suite de Fibonacci (le but étant de trouver une valeur qui soit pandigital au début et à la fin du nombre).
Bref, j'ai fais ce code :
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
| int main(void){
int* a = (int*)malloc(sizeof(int)*131072);
int* b = (int*)malloc(sizeof(int)*131072);
int* c = (int*)malloc(sizeof(int)*131072);
int* tmp;
a[0] = 1;
b[0] = 1;
int i = 0;
int r = 0;
int res;
int j = 0;
int len = 1;
for(;;){
r = 0;
for(j=0; j<len; j++){
res = r + a[j] + b[j];
c[j] = res % 10;
r = res / 10;
}
c[len] = r;
len += r;
tmp = b;
b = a;
a = c;
c = tmp;
i++;
if(len > 9 && pandigital(c) && pandigital(c+len-9)){
printf("Found !\n");
break;
}
}
return 0;
} |
Son temps d'exécution est d'environ 240 secondes.
Un ami m'a proposé de le faire de cette façon, qui s'exécute en seulement 100 secondes :
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
| int main(void){
int* a = (int*)malloc(sizeof(int)*1);
int* b = (int*)malloc(sizeof(int)*1);
int* c = NULL;
a[0] = 1;
b[0] = 1;
int i = 0;
int r = 0;
int res;
int j = 0;
int len = 1;
for(;;){
c = malloc((len+1) * sizeof(int));
c[len] = 0;
r = 0;
for(j=0; j<len; j++){
res = r + a[j] + b[j];
c[j] = res % 10;
r = res / 10;
}
c[len] = r;
len += r;
free(b);
b = a;
a = c;
i++;
}
return 0;
} |
La différence étant qu'au lieu de faire une rotation des pointeurs, on alloue un nouvel espace pour le prochain nombre et on libère celui qui ne sert plus (la valeur à n-2)
Je n'arrive pas à comprendre comment un malloc et un free peuvent être plus rapide qu'un simple échange de pointeurs.
Je pensais que l'échange prenait peut-être du temps, donc si je mets malloc/free et rotation à la fois le code reste tout de même rapide.
J'ai pensé à un souci d'alignement des buffers, donc j'ai essayé à coup de memalign avec différentes valeurs mais sans résultats...
Si une âme éclairée pouvait passer par là j'aimerai bien comprendre :calim2:
Merci
