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 :

Pourquoi fact_res_1 est-elle plus rapide que fact_res_2 ?


Sujet :

C

  1. #1
    Membre éclairé Avatar de ypcman
    Homme Profil pro
    Retraité codeur !
    Inscrit en
    janvier 2011
    Messages
    566
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Maine et Loire (Pays de la Loire)

    Informations professionnelles :
    Activité : Retraité codeur !
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : janvier 2011
    Messages : 566
    Points : 859
    Points
    859
    Par défaut Pourquoi fact_res_1 est-elle plus rapide que fact_res_2 ?
    Bonjour.
    A l'occasion d'un exo sur la récursivité, je code la traditionnelle fonction factoriel.
    Voulant tester sa rapidité, je compare 2 façons de la coder :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    unsigned long fact_rec_1(int n) {
    	if (n == 1) 
    		return 1;
    	 else 
    		return n * fact_rec_1(n - 1);
    }
     
    unsigned long fact_rec_2(int n) {
    	if (n != 1)
    		return n * fact_rec_2(n - 1);
    	else
    		return 1;
    }
    J'obtiens
    fact_rec_1 : 63 millisecondes
    fact_rec_2 : 69 millisecondes
    et je suis surpris que fact_res_1() où le test est False le plus souvent soit plus rapide que fact_res_2 ou est True le plus souvent et n'oblige donc pas la fct à passer au Merci pour vos éclaircissements !



    Le code complet pour ceux qui voudraient tester :
    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
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
     
    unsigned long fact_rec_1(int n) {
    	if (n == 1) {
    		return 1;
    	} else {
    		return n * fact_rec_1(n - 1);
    	}
    }
     
    unsigned long fact_rec_2(int n) {
    	if (n != 1)
    		return n * fact_rec_2(n - 1);
    	else
    		return 1;
    }
     
    int main(void) {
    	unsigned long res = 0;
    	time_t begin = clock();
    	time_t end = clock();
     
    	begin = clock();
    	for (int n = 0; n < 100000; n++) {
    		for (int i = 15; i < 25; i++) {
    			res = fact_rec_1(i);
    		}
    	}
    	end = clock();
    	printf("fact_rec_1 : %ld millisecondes\n",
    			(end - begin) * 1000 / CLOCKS_PER_SEC);
     
    	begin = clock();
    	for (int n = 0; n < 100000; n++) {
    		for (int i = 15; i < 25; i++) {
    			res = fact_rec_2(i);
    		}
    	}
    	end = clock();
    	printf("fact_rec_2 : %ld millisecondes\n",
    			(end - begin) * 1000 / CLOCKS_PER_SEC);
    	return EXIT_SUCCESS;
    }
    Participez vous aussi !
    Message utile
    Discussion résolue

  2. #2
    Membre expert

    Homme Profil pro
    Directeur de projet
    Inscrit en
    mai 2013
    Messages
    942
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet
    Secteur : Service public

    Informations forums :
    Inscription : mai 2013
    Messages : 942
    Points : 3 001
    Points
    3 001
    Par défaut Presque pareil
    Bonjour,

    Les deux tests (n== 0 et n != 0=) sont équivalents une comparaison suivi d'un saut conditionnel (les divers sauts conditionnels sont, d'une part, équivalents et, d'autre part, ils seront bien prédits ici) .
    Une vue de l'assembleur possible peut faire comprendre ce qui se passe :
    Code asm : 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
    ; Code : if(n== 0)
       cmp n, 0
       jnz  _Else
       ;...then return 1...
       jmp _End_if   ; qui ne sert à rien à cause du return et sera peut être supprimé
    _Else:
       ;...else fact_1...
    _End_if:
     
    ; Code : if(n!= 0)
       cmp n, 0
       jnz  _Else
       ;...then fact_2......'
       jmp _End_if
    _Else:
       ;...else return 1...'
    _End_if:
    Comme on le voit, la branche "then" a un jmp en plus c'est ce qui fait la différence. Sinon il n'yen a pas, la prédiction de branchement rend les deux sauts conditionnels équivalents vers le même cas le plus fréquent (!= 1).
    Certains compilateurs peuvent être assez astucieux pour permuter les cas. Mais pas tous

    Mea culpa : à cause des return mon explication ne tient pas.

    Salutations
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

  3. #3
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    février 2006
    Messages
    11 178
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : février 2006
    Messages : 11 178
    Points : 27 373
    Points
    27 373
    Billets dans le blog
    1
    Par défaut
    Bonjour

    Des benchs de ce genre ne sont pas facile à interpréter car tu as ta machine qui fait d'autres trucs qui peuvent interférer. A titre d'information, Python possède un module de bench (timeit) qui fonctionne de la façon suivante: on lui donne un repeat (ex 10) et un number (ex 500). Il lance alors la fonction à tester 500 fois et chronomètre le temps que prend ces 500 appels. Et il fait ça 10 fois. Et au bout des 10 chronos il te donne le plus court, le plus long et la moyenne. Pour essayer de te donner un bench le plus impartial possible en lissant au mieux les interférences éventuelles.

    Plus le compilateur qui rajoute parfois sa sauce en faisant des optimisations qui font que le code généré ne correspond pas au code écrit. Perso je n'aime pas car pour moi un compilateur c'est un traducteur qui n'a pas à prendre d'initiatives sur mon code mais que peut-on y faire et surtout qu'est-ce que cela entraine sur un bench tel que tu l'as écrit...?
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  4. #4
    Membre éclairé Avatar de ypcman
    Homme Profil pro
    Retraité codeur !
    Inscrit en
    janvier 2011
    Messages
    566
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Maine et Loire (Pays de la Loire)

    Informations professionnelles :
    Activité : Retraité codeur !
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : janvier 2011
    Messages : 566
    Points : 859
    Points
    859
    Par défaut
    Bonsoir Sve@r, j'ai essayé de reproduire le test que tu as décris :

    Avec 10 tests répétés 1000000 fois, j'obtiens toujours le même résultat étonnant :
    fact_rec_1_min : 107 millisecondes
    fact_rec_1_max : 114 millisecondes
    fact_rec_1_moy : 111.900002 millisecondes

    fact_rec_2_min : 122 millisecondes
    fact_rec_2_max : 126 millisecondes
    fact_rec_2_moy : 124.000000 millisecondes
    J'ai essayé d'inverser l'ordre des tests, d’abord rec_2 puis rec_1 , cela ne chance rien au résultat.

    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
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
     
    #define REPETITION 10
    #define NOMBRE 1000000
     
    unsigned long fact_rec_1(int n);
    unsigned long fact_rec_2(int n);
    unsigned long tab_min(unsigned long *tab, int taille);
    unsigned long tab_max(unsigned long *tab, int taille);
    float tab_moy(unsigned long *tab, int taille);
     
    int main(void) {
    	unsigned long res = 0;
    	unsigned long fact_rec_1_res[REPETITION] = { 0 };
    	unsigned long fact_rec_2_res[REPETITION] = { 0 };
    	time_t begin = clock();
    	time_t end = clock();
    	int n, i;
     
    	for (n = 0; n < REPETITION; n++) {
    		begin = clock();
    		for (i = 0; i < NOMBRE; i++) {
    			res = fact_rec_1(25);
    		}
    		end = clock();
    		fact_rec_1_res[n] = (end - begin) * 1000 / CLOCKS_PER_SEC;
     
    		begin = clock();
    		for (i = 0; i < NOMBRE; i++) {
    			res = fact_rec_2(25);
    		}
    		end = clock();
    		fact_rec_2_res[n] = (end - begin) * 1000 / CLOCKS_PER_SEC;
    	}
     
    	printf("fact_rec_1_min : %ld millisecondes\n",
    			tab_min(fact_rec_1_res, REPETITION));
    	printf("fact_rec_1_max : %ld millisecondes\n",
    			tab_max(fact_rec_1_res, REPETITION));
    	printf("fact_rec_1_moy : %f millisecondes\n",
    			tab_moy(fact_rec_1_res, REPETITION));
    	puts("");
    	printf("fact_rec_2_min : %ld millisecondes\n",
    			tab_min(fact_rec_2_res, REPETITION));
    	printf("fact_rec_2_max : %ld millisecondes\n",
    			tab_max(fact_rec_2_res, REPETITION));
    	printf("fact_rec_2_moy : %f millisecondes\n",
    			tab_moy(fact_rec_2_res, REPETITION));
     
    	return EXIT_SUCCESS;
    }
     
    unsigned long fact_rec_1(int n) {
    	if (n == 1)
    		return 1;
    	else
    		return n * fact_rec_1(n - 1);
    }
     
    unsigned long fact_rec_2(int n) {
    	if (n != 1)
    		return n * fact_rec_2(n - 1);
    	else
    		return 1;
    }
     
    unsigned long tab_min(unsigned long *tab, int taille) {
    	unsigned long res = tab[0];
    	for (int i = 0; i < taille; i++) {
    		if (tab[i] < res) {
    			res = tab[i];
    		}
    	}
    	return res;
    }
     
    unsigned long tab_max(unsigned long *tab, int taille) {
    	unsigned long res = tab[0];
    	for (int i = 0; i < taille; i++) {
    		if (tab[i] > res) {
    			res = tab[i];
    		}
    	}
    	return res;
    }
     
    float tab_moy(unsigned long *tab, int taille) {
    	float res = 0;
    	for (int i = 0; i < taille; i++) {
    		res += tab[i];
    	}
    	return res / (float) taille;
    }
    Participez vous aussi !
    Message utile
    Discussion résolue

  5. #5
    Expert éminent
    Homme Profil pro
    Analyste/ Programmeur
    Inscrit en
    juillet 2013
    Messages
    4 350
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Analyste/ Programmeur

    Informations forums :
    Inscription : juillet 2013
    Messages : 4 350
    Points : 9 857
    Points
    9 857
    Par défaut
    Le seul truc que je vois c'est le nombre de possibilités pour rentrer dans le if :
    • if (n == 1), 1 seule
    • if (n != 1), 1 infinité


    On peut penser raisonnablement que la première solution peut être transformée en switch (avec 1 seul cas et le else qui devient le cas par défaut).
    Le switch étant [légèrement] + efficace parce qu'il utilise 1 table de sauts

    En testant vite fait avec 1 switch (mais il faut garder les return dans les case et ne pas créer de variable locale), on arrive [quasi] au même résultat que le code avec if (n == 1).
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    unsigned long fact_rec_3(int n) {
        switch(n) {
        case 1:
            return 1;
            break;
        default:
            return (n * fact_rec_3(n - 1));
            break;
        }
    }
    Mais cela interroge parce que j'ai toujours entendu dire qu'il faut mettre le cas qui a l'occurence la + élevée dans le if (ici le code avec if (n != 1)).
    Mais cela veut dire que le compilateur ne va pas y toucher et il ne va pas l'optimiser
    après remplacer 1 if par 1 switch c'est très souvent trivial et tout le monde sait que le switch est [légèrement] + efficace

  6. #6
    Modérateur

    Avatar de Bktero
    Homme Profil pro
    Développeur en systèmes embarqués
    Inscrit en
    juin 2009
    Messages
    4 447
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 35
    Localisation : France, Loire Atlantique (Pays de la Loire)

    Informations professionnelles :
    Activité : Développeur en systèmes embarqués

    Informations forums :
    Inscription : juin 2009
    Messages : 4 447
    Points : 13 533
    Points
    13 533
    Billets dans le blog
    1
    Par défaut
    Dans des cas comme ça, il faut regarder l'assembleur généré pour les 2 (ou 3) fonctions, par exemple avec https://compiler-explorer.com/

    Bien penser à mettre une option pour le niveau d'optimisation (comme -O2), sinon les comparaisons n'ont pas de sens.

    Après, c'est pas forcément facile de comprendre pourquoi ça donne ça, mais c'est toujours mieux que de faire des suppositions sur ce que ça donne.

  7. #7
    Expert éminent
    Homme Profil pro
    Ingénieur développement matériel électronique
    Inscrit en
    décembre 2015
    Messages
    1 468
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 59
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Ingénieur développement matériel électronique
    Secteur : High Tech - Électronique et micro-électronique

    Informations forums :
    Inscription : décembre 2015
    Messages : 1 468
    Points : 7 115
    Points
    7 115
    Par défaut
    Je dirais plutôt que les 2 fonctions sont totalement identiques. L'optimiseur devrait voir cela.
    Il faudrait voir les 2 codes assembleurs.
    Selon moi, la fonction 1 fait l'appel récursif en toute dernière action, et donc est facilement convertible en un traitement non récursif faisant gagner du temps. Mais encore une fois, les fonctions sont identiques, l'optimiseur fait mal son boulot!

  8. #8
    Membre averti
    Homme Profil pro
    très occupé
    Inscrit en
    juillet 2014
    Messages
    128
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : très occupé

    Informations forums :
    Inscription : juillet 2014
    Messages : 128
    Points : 378
    Points
    378
    Par défaut
    Le plus probable est que ypcman compilait sans optimisations (sans passer l'option -O de gcc comme rappelé par Bktero, avec -O2 ou -O3 par exemple).

    En tout cas, il n'indique pas qu'elles étaient ses options de compilation, ni le compilateur utilisé.

  9. #9
    Membre éclairé Avatar de ypcman
    Homme Profil pro
    Retraité codeur !
    Inscrit en
    janvier 2011
    Messages
    566
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Maine et Loire (Pays de la Loire)

    Informations professionnelles :
    Activité : Retraité codeur !
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : janvier 2011
    Messages : 566
    Points : 859
    Points
    859
    Par défaut
    j'ai utilisé le lien pour voir l'assembleur généré et effectivement, l'assembleur est identique pour les 2 fonctions, identique aussi avec celle employant un switch/case
    Code asm : 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
    fact_rec_1(int):
            push    rbp
            mov     rbp, rsp
            push    rbx
            sub     rsp, 24
            mov     DWORD PTR [rbp-20], edi
            cmp     DWORD PTR [rbp-20], 1
            jne     .L2
            mov     eax, 1
            jmp     .L3
    .L2:
            mov     eax, DWORD PTR [rbp-20]
            movsx   rbx, eax
            mov     eax, DWORD PTR [rbp-20]
            sub     eax, 1
            mov     edi, eax
            call    fact_rec_1(int)
            imul    rax, rbx
    .L3:
            mov     rbx, QWORD PTR [rbp-8]
            leave
            ret

    Je suis sous gcc (GCC) 11.3.1 20220421 (Red Hat 11.3.1-2)
    Effectivement je compilais en -O0. En passant à -O2, les différences de durées deviennent négligeables.

    Merci pour vos réflexions !
    Participez vous aussi !
    Message utile
    Discussion résolue

  10. #10
    Membre expérimenté
    Homme Profil pro
    Chef de projet NTIC
    Inscrit en
    juillet 2020
    Messages
    346
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 50
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Chef de projet NTIC

    Informations forums :
    Inscription : juillet 2020
    Messages : 346
    Points : 1 328
    Points
    1 328
    Par défaut
    Bonjour,

    Durée nulle = optimisation, toutes tes boucles ont élé opt out car elles n'avaient aucun effet →passe ta variable res en volatile pour éviter cela avec des optimisations poussées (ou fait quelque chose avec le résultat calculé).
    Et surtout, surtout utilise des outils comme godbolt.

    J'imagine, et là il faudrait qu'un expert confirme, que dans le premier cas le code qui est déjà dans le pipeline d'exécution se trouve exécuté la majorité du temp, alors que dans le second cas le processeur devra invalidé le pipeline d'exécution et recommencer.

  11. #11
    Membre éclairé Avatar de ypcman
    Homme Profil pro
    Retraité codeur !
    Inscrit en
    janvier 2011
    Messages
    566
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Maine et Loire (Pays de la Loire)

    Informations professionnelles :
    Activité : Retraité codeur !
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : janvier 2011
    Messages : 566
    Points : 859
    Points
    859
    Par défaut
    J'ai justement utilisé godbolt !

    Citation Envoyé par WhiteCrow Voir le message
    Bonjour,

    Durée nulle = optimisation, ....
    En fait, je testais toujours fact(25) un million de fois. Or avec l'optimisation, fact(25) n'étais plus recalculé d'où les durées nulles. J'ai modifié mon code pour calculer un fact(rand()%26) et les durées sont redevenues non nulles mais en revanche quasi identiques et sans l'une systématiquement plus faible que l'autre :
    fact_rec_1_min : 122 millisecondes
    fact_rec_1_max : 126 millisecondes
    fact_rec_1_moy : 124.800003 millisecondes

    fact_rec_1_plus_min : 120 millisecondes
    fact_rec_1_plus_max : 127 millisecondes
    fact_rec_1_plus_moy : 124.900002 millisecondes

    fact_rec_2_min : 122 millisecondes
    fact_rec_2_max : 126 millisecondes
    fact_rec_2_moy : 124.800003 millisecondes

    fact_rec_2_plus_min : 121 millisecondes
    fact_rec_2_plus_max : 128 millisecondes
    fact_rec_2_plus_moy : 125.099998 millisecondes
    Voici le code si ça intéresse
    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
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
     
    #define REPETITION 10
    #define NOMBRE 10000000
     
    unsigned long fact_rec_1(int n);
    unsigned long fact_rec_1_plus(int n);
    unsigned long fact_rec_2(int n);
    unsigned long fact_rec_2_plus(int n);
    unsigned long tab_min(unsigned long *tab, int taille);
    unsigned long tab_max(unsigned long *tab, int taille);
    float tab_moy(unsigned long *tab, int taille);
     
    int main(void) {
    	unsigned long res = 0;
    	unsigned long fact_rec_1_res[REPETITION] = { 0 };
    	unsigned long fact_rec_2_res[REPETITION] = { 0 };
    	unsigned long fact_rec_1_plus_res[REPETITION] = { 0 };
    	unsigned long fact_rec_2_plus_res[REPETITION] = { 0 };
    	time_t begin = clock();
    	time_t end = clock();
    	int n, i;
    	int val = 26;
    	srand(time(NULL));
    	for (n = 0; n < REPETITION; n++) {
     
    		begin = clock();
    		for (i = 0; i < NOMBRE; i++) {
    			res = fact_rec_1_plus(rand() % val);
    		}
    		end = clock();
    		fact_rec_1_plus_res[n] = (end - begin) * 1000 / CLOCKS_PER_SEC;
     
    		begin = clock();
    		for (i = 0; i < NOMBRE; i++) {
    			res = fact_rec_2_plus(rand() % val);
    		}
    		end = clock();
    		fact_rec_2_plus_res[n] = (end - begin) * 1000 / CLOCKS_PER_SEC;
     
    		begin = clock();
    		for (i = 0; i < NOMBRE; i++) {
    			res = fact_rec_1(rand() % val);
    		}
    		end = clock();
    		fact_rec_1_res[n] = (end - begin) * 1000 / CLOCKS_PER_SEC;
     
    		begin = clock();
    		for (i = 0; i < NOMBRE; i++) {
    			res = fact_rec_2(rand() % val);
    		}
    		end = clock();
    		fact_rec_2_res[n] = (end - begin) * 1000 / CLOCKS_PER_SEC;
     
    	}
     
    	printf("fact_rec_1_min : %ld millisecondes\n",
    			tab_min(fact_rec_1_res, REPETITION));
    	printf("fact_rec_1_max : %ld millisecondes\n",
    			tab_max(fact_rec_1_res, REPETITION));
    	printf("fact_rec_1_moy : %f millisecondes\n",
    			tab_moy(fact_rec_1_res, REPETITION));
    	puts("");
    	printf("fact_rec_1_plus_min : %ld millisecondes\n",
    			tab_min(fact_rec_1_plus_res, REPETITION));
    	printf("fact_rec_1_plus_max : %ld millisecondes\n",
    			tab_max(fact_rec_1_plus_res, REPETITION));
    	printf("fact_rec_1_plus_moy : %f millisecondes\n",
    			tab_moy(fact_rec_1_plus_res, REPETITION));
    	puts("");
    	printf("fact_rec_2_min : %ld millisecondes\n",
    			tab_min(fact_rec_2_res, REPETITION));
    	printf("fact_rec_2_max : %ld millisecondes\n",
    			tab_max(fact_rec_2_res, REPETITION));
    	printf("fact_rec_2_moy : %f millisecondes\n",
    			tab_moy(fact_rec_2_res, REPETITION));
    	puts("");
    	printf("fact_rec_2_plus_min : %ld millisecondes\n",
    			tab_min(fact_rec_2_plus_res, REPETITION));
    	printf("fact_rec_2_plus_max : %ld millisecondes\n",
    			tab_max(fact_rec_2_plus_res, REPETITION));
    	printf("fact_rec_2_plus_moy : %f millisecondes\n",
    			tab_moy(fact_rec_2_plus_res, REPETITION));
    	return EXIT_SUCCESS;
    }
     
    unsigned long fact_rec_1(int n) {
    	if (n == 1)
    		return 1;
    	else
    		return n * fact_rec_1(n - 1);
    }
     
    unsigned long fact_rec_1_plus(int n) {
    	switch (n) {
    	case 1:
    		return 1;
    		break;
    	default:
    		return n * fact_rec_1(n - 1);
    		break;
    	}
    }
     
    unsigned long fact_rec_2(int n) {
    	if (n != 1)
    		return n * fact_rec_2(n - 1);
    	else
    		return 1;
    }
     
    unsigned long fact_rec_2_plus(int n) {
    	if (!(n == 1))
    		return n * fact_rec_2(n - 1);
    	else
    		return 1;
    }
     
    unsigned long tab_min(unsigned long *tab, int taille) {
    	unsigned long res = tab[0];
    	for (int i = 0; i < taille; i++) {
    		if (tab[i] < res) {
    			res = tab[i];
    		}
    	}
    	return res;
    }
     
    unsigned long tab_max(unsigned long *tab, int taille) {
    	unsigned long res = tab[0];
    	for (int i = 0; i < taille; i++) {
    		if (tab[i] > res) {
    			res = tab[i];
    		}
    	}
    	return res;
    }
     
    float tab_moy(unsigned long *tab, int taille) {
    	float res = 0;
    	for (int i = 0; i < taille; i++) {
    		res += tab[i];
    	}
    	return res / (float) taille;
    }
    Participez vous aussi !
    Message utile
    Discussion résolue

  12. #12
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    février 2006
    Messages
    11 178
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : février 2006
    Messages : 11 178
    Points : 27 373
    Points
    27 373
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par ypcman Voir le message
    J'ai modifié mon code pour calculer un fact(rand()%26)
    Si tu veux un rand plus uniforme, il est conseillé de demander un rand() / RAND_MAX * 26
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  13. #13
    Membre éclairé Avatar de ypcman
    Homme Profil pro
    Retraité codeur !
    Inscrit en
    janvier 2011
    Messages
    566
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Maine et Loire (Pays de la Loire)

    Informations professionnelles :
    Activité : Retraité codeur !
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : janvier 2011
    Messages : 566
    Points : 859
    Points
    859
    Par défaut
    Citation Envoyé par Sve@r Voir le message
    Si tu veux un rand plus uniforme, il est conseillé de demander un rand() / RAND_MAX * 26
    Ok, mais ce ne serait pas plutôt
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    26*(double)rand()/(double)RAND_MAX;
    Sinon, ça renvoie toujours 0, non ?
    Participez vous aussi !
    Message utile
    Discussion résolue

  14. #14
    Membre averti
    Homme Profil pro
    très occupé
    Inscrit en
    juillet 2014
    Messages
    128
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : très occupé

    Informations forums :
    Inscription : juillet 2014
    Messages : 128
    Points : 378
    Points
    378
    Par défaut
    Citation Envoyé par ypcman Voir le message
    Ok, mais ce ne serait pas plutôt
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    26*(double)rand()/(double)RAND_MAX;
    Sinon, ça renvoie toujours 0, non ?
    Oui.

    Tu peux aussi le faire en castant seulement le numérateur ou le dénominateur de la division. Il n'est pas nécessaire de caster les deux.

  15. #15
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    février 2006
    Messages
    11 178
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : février 2006
    Messages : 11 178
    Points : 27 373
    Points
    27 373
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par ypcman Voir le message
    Sinon, ça renvoie toujours 0, non ?
    Exact, il faut diviser en double (me pensais en Python). Mais un seul cast suffit, une opération impliquant 2 opérandes se faisant toujours dans le type le plus large des deux . A toi de choisir lequel tu veux caster.
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  16. #16
    Membre expert

    Homme Profil pro
    Directeur de projet
    Inscrit en
    mai 2013
    Messages
    942
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet
    Secteur : Service public

    Informations forums :
    Inscription : mai 2013
    Messages : 942
    Points : 3 001
    Points
    3 001
    Par défaut Youppie !
    Bonjour,

    A la lecture de l'assembleur, mon explication initiale redevient valide .

    En effet, les return ne sont pas exécutés in situ car seule la valeur de retour est préparée là où ils apparaissent (dans eax ou rax) pour être traitée seulement en fin de fonction. Le jmp systématique de fin du "then" pèse alors effectivement plus car plus fréquent dans la seconde fonction. Ceci d'autant plus que la ribambelle de call qui précèdent casse un peu le potentiel d'anticipation du jmp par le processeur.

    Salutations
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

  17. #17
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    février 2006
    Messages
    11 178
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : février 2006
    Messages : 11 178
    Points : 27 373
    Points
    27 373
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par ypcman Voir le message
    J'ai modifié mon code pour calculer un fact(rand()%26)
    Désolé de revenir sur ce détail, mais pour être le plus impartial possible, il faudrait que les deux fonctions calculent les mêmes choses...

    Accessoirement, pourquoi prendre la factorielle comme exemple? Ton but tel que tu l'exprimes c'est regarder comment se comporte if (truc_le_moins_probable) vs if (truc_le_plus_probable). Pourquoi ne pas écrire une fonction style
    Code c : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    void fct1(int n) {
    	if (n == 0) n=5;
    	else n=10;
    	sleep(1);
    }
     
    void fct2(int n) {
    	if (n != 0) n=10;
    	else n=5;
    	sleep(1);
    }
    Après si le sleep() change la donne sur les chronos, on peut le remplacer par autre chose (une boucle), l'essentiel est que les effets induits par la récursivité soient supprimés...
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  18. #18
    Membre éclairé Avatar de ypcman
    Homme Profil pro
    Retraité codeur !
    Inscrit en
    janvier 2011
    Messages
    566
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Maine et Loire (Pays de la Loire)

    Informations professionnelles :
    Activité : Retraité codeur !
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : janvier 2011
    Messages : 566
    Points : 859
    Points
    859
    Par défaut
    Tu as raison. C'est juste que j'étais en train de coder une fct factoriel récursive lorsque j'ai voulu tester les 2 versions du if().
    Pour le rand() aussi mais à relativiser car je boucle un grand nombre de fois :
    Participez vous aussi !
    Message utile
    Discussion résolue

  19. #19
    Membre expert

    Homme Profil pro
    Directeur de projet
    Inscrit en
    mai 2013
    Messages
    942
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet
    Secteur : Service public

    Informations forums :
    Inscription : mai 2013
    Messages : 942
    Points : 3 001
    Points
    3 001
    Par défaut Factorielle récursive vs performances
    Bonjour,

    Coder une factorielle en récursif pour comprendre la récursivité pourquoi pas. Faire des mesures de performances dessus n'est pas loin de la perversité (il suffit de comparer à une simple boucle).

    En outre le codage n'est pas très fiable car l'argument est déclaré comme int il peut donc être négatif ou nul. Badaboum ! : boucle infinie heureusement arrêtée (salement mais arrêté quand même) par la saturation de la pile.
    Même en passant en unsigned, il est préférable d'écrire :
    Code C : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    unsigned long fact_rec_1(int n) {
       if (n < 2) return 1;
       return n * fact_rec_1(n - 1);
    }

    Salutations
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

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

Discussions similaires

  1. Les applications Rust sont-elles plus rapides que leurs équivalents en C ?
    Par Patrick Ruiz dans le forum Programmation système
    Réponses: 32
    Dernier message: 10/02/2021, 20h57
  2. Réponses: 1
    Dernier message: 19/01/2019, 19h09
  3. Réponses: 1
    Dernier message: 23/06/2017, 11h27
  4. Réponses: 8
    Dernier message: 20/04/2012, 23h37

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