Discussion :

[souviron34]

j'ai re-testé en utilisant 10 comme dimension des tableaux (puisqu'on ne dépasse jamais ça à cause du len)..

J'ai des résultalts équivalents avec les 2 (environ 1.5 micro-seconde par algo), et le même nombre de bouccles (420 000)sur mon Acer 1362 Athlon Sempron d'il y a 6 ans, sous Linux CentOS 4.6

Si je met la taille des tableaux que tu avais intialement mis, effectivement il y a un facteur 3. Qui donc vient comme mentionné précédememnt effectivement sans doute des caches...

Mais comme on a besoin que de 10...

[diogene]

0- ce n'est pas ces valeurs là, mais celles dans c :1,4,9,6,8,7,2,5,3

1- Sur la fonction pandigital() :
si s[i] est égal à 0, alors s[i]-1 est négatif et le résultat du décalage est indéfini.
Préférer

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
	for (i=0; i<9; i++) m |= 1 << s[i];
	return m == 0x3FE;

2- Sur la fonction main():

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
  for(j=0; j<len; j++){
      res = r + a[j] + b[j];
      c[j] = res % 10

Si len == N alors a[] et b[] doivent être des tableaux contenant N valeurs utiles.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
  c[len] = r;
  len += r;

c[] contient N+1 valeurs utiles et si r == 1 , len passe à N+1

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
  tmp = b;
...
  c = tmp

Permutation des pointeurs.
c->a : maintenant a[] contient N+1 valeurs utiles.
a->b : b[] N valeurs utiles
b->c
pandigital() devrait tester a. En testant c, on va faire deux tours de trop (i trop grand de 2)

On repart sur la boucle avec len == N+1. on calcule res = r + a[j] + b[j];j varie de 0 à N, mais où la valeur b[N] a t'elle été initialisée ?

3- Sur le temps d'exécution :
J'ai constaté, fortuitement au départ, qu'il était très variable chez moi mais de façon reproductible. Il peut varier d'un facteur 2 allant dans le meilleur des cas très légerement plus vite que l'autre code.

Je donne mes constatations brutes en attendant que d'autres reproduisent le problème et l'expliquent clairement.

Le facteur déterminant la durée d'exécution est le nombre de int que tu alloues dans tes malloc() : 131072 (= 0x20000) est justement le pire cas. Si on alloue un peu plus ou un peu moins, le temps d'exécution chute et est même légèrement plus rapide que dans le cas de l'autre code (-5%). Le temps d'exécution commence à augmenter pour 131060, passe à un maximum pour 131072 (+85%) et retombe à sa valeur minimale pour des valeurs supérieures à 131080.
Ce n'est pas lié à la manière d'allouer les tableaux.

[aslo92]

J'ai dit que le code que j'ai posté précédemment allait 5 fois plus vite.
C'est vrai uniquement si le nombre d'itérations est faible (j'avais fait le test pour i = 100).
Pour i = 329468, mon code et plus lent !

J'ai téléchargé la version d'essai (1 mois de VTUNE)
J'ai lancé les 2 versions sous VTUNE et il apparaît que le code de ton ami ne retourne aucun cache miss dans L2 alors que le tien donne 1 500 000 cache misses.

La ligne de ton code qui prend le plus de temps est :

c[j] = res % 10;

Idem pour le code de ton ami, à part que comme il y n'a pas de miss, ça prend moins de temps.

[anacharsis]

salut !

j'ai lu ce post un peu vite, mais il me semble que les calculs des termes de la suite sont calculés en base 10.
en utilisant 1000000000, la taille à réserver sur le tas est divisée par 9 et le nombre de répétition de la boucle interne aussi ...

A+

[aslo92]

Bonjour à tous,

comme je l'ai dit dans mon précédent post, ce sont les lignes suivantes qui prennent le plus de temps à s'exécuter:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
    c[j] = res % 10;
    r = res / 10;

Utiliser une table pour calculer le reste et la retenue fait gagner 30 % du temps.

Le code correspondant ce trouve ci-dessous:

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
int main(void){	
    int t_a[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    int t_r[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
 
    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] = t_a[res];
            r    = t_r[res];
        }
        c[len] = r;
        len += r;
 
        tmp = b;
        b = a;
        a = c;
        c = tmp;
 
        i++;
        if(len > 9 && pandigital(c) && pandigital(c+len-9)){
			break;
		}
	}
 
    free(a);
    free(b);
    free(c);
    return 0;
}

Pour gagner encore plus de temps, il faudrait pouvoir minimiser le nombre de boucles ou diminuer la taille des buffers.

J'ai essayé de diminuer la taille des buffers en passant les buffers en char au lieu de int. On perd du temps !

Pour minimiser le nombre de boucles, il faudrait pouvoir mettre 4 digits dans un mot de 32 bits (8 bits suffisent à coder les chiffres 0 à 9). On pourrait ainsi faire 4 opérations d'un coup. Le problème vient des retenues qu'il ne faut pas oublier de propager d'un octet à l'autre. Pas facile à faire rapidement en C en base 10. En assembleur, par contre ça ne devrait pas poser de problème avec les instructions SSE.

[anacharsis]

comme je viens de le dire, il suffit de remplacer / 10 et % 10 par / 1000000000 et % 1000000000 pour aller 9 fois plus vite 9 fois moins souvent.

A+

[diogene]

comme je viens de le dire, il suffit de remplacer / 10 et % 10 par / 1000000000 et % 1000000000 pour aller 9 fois plus vite 9 fois moins souvent.

A+

Er que devient dans ce cas la fonction pandigital() ?

[anacharsis]

tu as raison : il faut réécrire pandigital !

en fait j'ai même réécrit 2 pan_hi et pan_lo car a[0] contient bien les 9 chiffres les moins significatifs en base 1000000000 alors que a[len - 1] contient quelques chiffres les plus significatifs et il faut compléter avec quelques chiffres de a[len - 2].

A+

[haleth]

A propos, d'après Wikipedia, le plus petit nombre pandigital en base 10 est 1023456789

Ton algo est faux ?!

[diogene]

Si j'ai bonne mémoire sur ce sujet, l'algo du PO ne considérait que les chiffres 1..9 (mais pas 0). D'où la différence.