Optimisation de vitesse et correction syntaxique

**akorx** · 03/08/2011, 14h54

Salut à tous et à toutes !

Je n'ai pas fait de c et de c++ depuis l'école pour ainsi dire (il y a donc une bonne quinzaine d'années) et pour m'y remettre, je viens de m'amuser à écrire un petit programme me permettant de trouver tous les nombres premiers compris entre 2 et 10.000.000 et j'affiche au final le plus grand.

Voici le code que j'ai créé (j'utilise code::blocks).

main.cpp :

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
 
#include <iostream>
#include <ctime>
#include <vector>
#include "verifPremier.h"
 
using namespace std;
 
int main()
{
    int i(0);
    int *Pi=&i; //pointeur sur i
    vector<int> t; //tableau dynamique contenant les nombres premiers trouves
    t.push_back(2);
    long H;
    time(&H);
    cout << "Heure de lancement               = " << ctime(&H) << endl;
    for (i=2; i<10000000; i++)
    {
        siPremier(Pi,t);
    }
    time(&H);
    cout << "Heure de fin                     = " << ctime(&H) << endl;
    cout << "Plus grand nombre premier trouve = " << t.back() << endl << endl << endl << endl << endl;
    return 0;
}

verifPremier.h :

Code :

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

1
2
3
4
5
6
7
8
9
 
#ifndef VERIFPREMIER_H_INCLUDED
#define VERIFPREMIER_H_INCLUDED
 
using namespace std;
 
void siPremier(int *Pi , vector<int> & t );
 
#endif // VERIFPREMIER_H_INCLUDED

verifPremier.cpp :

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
 
#include <iostream>
#include <cmath>
#include <vector>
#include "verifPremier.h"
 
using namespace std;
 
void siPremier(int *Pi , vector<int> & t )
{
    int taille=t.size();
    int i=0;
    int j=0;
    double racine=sqrt(*Pi);
    while (t[i]<=floor(racine) && i<=taille && j==0)
    {
        if (*Pi%t[i]==0)
        {
            j++;
        }
        i++;
    }
    if (j==0)
    {
        //cout << *Pi << endl;
        t.push_back(*Pi);
    }
}

Pour résumer en gros la méthode que j'utilise pour vérifier si un nombre est premier, je vérifie si il est divisible par les n nombres premiers inférieurs à sa racine carrée. Dès que je trouve qu'il est divisible par l'un d'entre eux je passe au suivant : c'est ce que je fais dans le :

[I]
if (*Pi%t==0)
{
j++;
}

Si le nombre est premier je l'ajoute à mon tableau dans un tableau dynamique ("vector <int> t") ce qui fait que mon tableau évolue comme ceci à chaque incrémentation de i si ce dernier est un nombre premier :

2
2 3
2 3 5
2 3 5 7
2 3 5 7 11
2 3 5 7 11 13
2 3 5 7 11 13 17
2 3 5 7 11 13 17 19
2 3 5 7 11 13 17 19 23
2 3 5 7 11 13 17 19 23 29 .
2 3 5 7 11 13 17 19 23 29 31
2 3 5 7 11 13 17 19 23 29 31 33
2 3 5 7 11 13 17 19 23 29 31 33 37 ...

NB : La méthode de calcul n'est peut être pas la plus rapide pour vérifier si un nombre est premier mais vous l'aurez bien compris : ce n'est pas trop via la méthode que je veux optimiser mon programme mais plutôt par les techniques utilisées (c'est donc purement dans un but pédagogique et non scientifique).. je veux donc juste vérifier si SYNTAXIQUEMENT parlant on peut faire beaucoup mieux (avec des pointeurs par exemple ou autres "techniques" ou objets).

On pourrait peut être ajouter pendant le calcul une petite animation qui bascule entre les symboles du type / -- \ | comme on le voit souvent.

Merci d'avances pour toutes vos réponses, remarques et critiques.

**akorx** · 03/08/2011, 15h21

J'oubliais une chose très importante : dois je libérer la mémoire à la fin de mon programme? si c'est le cas par quelle méthode?

**koala01** · 03/08/2011, 15h45

Salut,

Pourrais tu déjà essayer de justifier l'utilisation d'un pointeur sur un entier lorsqu'il s'agit d'appeler ta fonction

Pour rappel, un pointeur n'est jamais qu'une variable enitère numérique particulière en cela qu'elle représente... l'adresse ("physique") à laquelle la variable se trouve effectivement.

Comme tu ne modifie absolument pas "ce qui est pointé" par ton pointeur, pourquoi vouloir absolument ajouter une indirection

Ceci dit, il est bon de garder le principe de la responsabilité unique (Single Responsability Principle ) en tête, et donc de veiller à ce que chaque fonction ne fasse qu'une chose, mais qu'elle le fasse bien...

J'aurais donc plutôt tendance à créer une fonction estPremier qui prend effectivement un entier et une référence (constante, pour bien faire) sur un std::vector contenant ceux que l'on a déjà trouvé, et qui renvoie simplement vrai si le nombre recherché est premier et false si ce n'est pas le cas.

Ce serait alors à la fonction main de veiller à insérer le nombre s'il apparait qu'il est, effectivement, premier.

Ta boucle ressemblerait donc plutôt à quelque chose comme

Code :

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

1
2
3
4
5
for (i=2; i<10000000; i++)
    {
        if(estPremier(i,t))
            t.push_back(i);
    }

Pour répondre à ta question quant à savoir si tu dois libérer la mémoire:
La classe std::vector est suffisemment intelligente pour gérer elle-même la mémoire dont elle a besoin.

D'un autre coté, tu n'alloue absolument jamais de mémoire pour le seul pointeur que tu utilise avec new. Il est donc totalement inutile (et dangereux) de libérer l'adresse mémoire vers laquelle il pointe (avec delete).

Le fait que tu te sois posé la question met parfaitement en évidence ce que l'on répète sans cesse : il est important d'éviter le recours aux pointeurs, à moins que l'on n'ait vraiment pas le choix

**akorx** · 03/08/2011, 16h34

Je me disais que l'utilisation d'un pointeur (ici Pi) m'éviterais de copier la valeur de i à chaque fois en y faisant plutôt référence (c'est le but du pointeur) pour optimiser légèrement les perfs étant donné que je "jongle" avec cette variable 10 millions de fois...

D'ailleurs je pensais avoir raison de le faire car si on fait le test en utilisant le pointeur mon programme met 20s pour trouver les nombres premiers compris entre 0 et 10 millions alors que sans le pointeur je passe à 78s...

C'est bien dans ce but d'optimisation et de critique que je suis venu vous proposez d'analyser mon code et je pensais justement que le pointeur était l'une des solutions...

Pour résumer : je n'aurais pas utiliser de pointeur et tu m'aurais proposé de le faire je me serais "bon sang c'est clair il a raison c'est bien plus rapide" mais là tu sembles me dire qu'il vaut mieux l'éviter

.

Qu'en est il?

screetch · 03/08/2011, 16h48

erroné;

si tu ne copies pas l'entier i lui même, tu dois copier son adresse. Or une adresse est au mieux, aussi grande qu'un entier; au pire, deux fois plus grande, donc c'est plus coûteux de copier l'adresse.

screetch · 03/08/2011, 16h57

autre optimisation; lorsque tu fais push_back sur un vecteur, il se peut que le vecteur n'aie plus de place, et du coup tout va devoir être réalloué (ca veut dire, nouvelle allocation mémoire, copie de tooooouuuut le tableau, destruction de la mémoire précédente)

la solution est d'utiliser "reserve" sur le tableau et de réserver assez de mémoire pour contenir tout ce dont tu as besoin. Une sorte de borne supérieure.
Par exemple, sur 10000000 de chiffres, retirer tous ceux qui sont multiple de 2, de 3 et de 5 va elaguer enormément
Multiple2 = 10000000/2 (il y a 1/2 de multiples de deux)
Multiple3 = 10000000/3 (...)
Multiple5 = 10000000/5 (...)

(mais on a retiré trop de chiffres; ceux multiples de 6 sont retirer deux fois, ceux de 10 et ceux de 15 aussi, et ceux de 2*3*5 sont eux retirer 3 fois)
Multiple6 = 10000000/6
Multiple10 = 10000000/10
Multiple15 = 10000000/15
Multiple30 = 10000000/30

Max = 10000000-Multiple2-Multiple3-Multiple5+Multiple6+Multiple10+Multiple15+2*Multiple30
ca fait genre 3166666 (maxi)

bon mes maths sont sans doutes toutes pourries mais c'est l'idée

**akorx** · 03/08/2011, 17h03

Envoyé par screetch

autre optimisation; lorsque tu fais push_back sur un vecteur, il se peut que le vecteur n'aie plus de place, et du coup tout va devoir être réalloué (ca veut dire, nouvelle allocation mémoire, copie de tooooouuuut le tableau, destruction de la mémoire précédente)

la solution est d'utiliser "reserve" sur le tableau et de réserver assez de mémoire pour contenir tout ce dont tu as besoin. Une sorte de borne supérieure.
Par exemple, sur 10000000 de chiffres, retirer tous ceux qui sont multiple de 2, de 3 et de 5 va elaguer enormément
Multiple2 = 10000000/2 (il y a 1/2 de multiples de deux)
Multiple3 = 10000000/3 (...)
Multiple5 = 10000000/5 (...)

(mais on a retiré trop de chiffres; ceux multiples de 6 sont retirer deux fois, ceux de 10 et ceux de 15 aussi, et ceux de 2*3*5 sont eux retirer 3 fois)
Multiple6 = 10000000/6
Multiple10 = 10000000/10
Multiple15 = 10000000/15
Multiple30 = 10000000/30

Max = 10000000-Multiple2-Multiple3-Multiple5+Multiple6+Multiple10+Multiple15+2*Multiple30
ca fait genre 3166666 (maxi)

bon mes maths sont sans doutes toutes pourries mais c'est l'idée

A oui bien joué le fait de "retirer" les multiples de 2,3,5,etc... je n'y avais pas penser...

Pour revenir à l'optimisation elle même de mon code, comment "réserver" cette plage en mémoire dès le début (car c'est surement l'une des meilleures optimisations de code que je recherchais dans mon énoncé) je suppose qu'il faut que je taille mon tableau tout simplement avec 10 millions de cases à zéro et qu'après je teste si la case est à zéro quand je parcours mon tableau pour récupérer chaque nombre premier trouvé... est ce bien ça?

screetch · 03/08/2011, 17h11

non, il y a une méthode ".reserve()", et tu peux l'appeler avec 3166666 comme decrit plus haut (au lieu de 10000000)
si tu sais combien il y en a tu peux aussi utiliser moins de place.
reserve ne fait que réserver la mémoire, il n'y a pas besoin de changer ton code ailleurs.

**bertry** · 03/08/2011, 21h57

Salut,

Pourquoi ne pas utiliser une list plutôt qu'un vector? J'ai l'impression que ce serait plus approprié pour ton algo :
-Tu fais un accès séquentiel à ton container ( pas besoin de l'accès par indices ), donc tu peut accéder à tes nombres premiers avec un simple itérator sur cette liste.
-Ça solutionne le problème de la réservation anticipée de la mémoire, puisque là, le push_back n'est pas pénalisant.

En ce qui concerne le passage d'arguments à une fonction, tu peux utiliser le passage par référence constante (évoqué ici dans la FAQ ) plutôt que le passage par pointeurs

**3DArchi** · 04/08/2011, 08h07

for (i=3; i<10000000; i+=2) devrait diminuer par 2. Pas besoin d'analyser les nombres pairs. Et par conséquent tu peux enlever 2 du vecteur. ce qui diminue sérieusement la taille de ton échantillon. (au passage c'est le seul gain significatif que j'ai obtenu, ce qui renforce qu'il faut bien travailler sur les algorithmes et non sur les 'micro' optimisations).

Même si tu voulais éviter la copie (ce qui comme le dit screetch ici n'est pas pertinent), ce n'est pas un pointeur qu'il aurait fallu utiliser mais un passage par référence constante. Un pointeur suppose implicitement que la valeur NULL est pertinente

using namespace std;(surtout dans le .h)

cf F.A.Q..

Les constantes en dur, c'est mal

plutôt que de calculer la racine carrée (qui peut être couteuse) de *Pi, tu dois pouvoir calculer le carrée t[i] et la comparer à *Pi.

while (t[i]<=floor(racine) && i<=taille && j==0) : i<=taille est erronée : les tableaux s'adressent de 0 à taille-1. De plus comme le test sur la taille est après l'adressage du tableau, tu va toujours accéder à l'élément [n] ce qui est un comportement indéterminé

const c'est bon, mangez-en

je préfère utiliser les itérateurs pour parcourir les tableaux (cohérence, lisibilité)

Les temps que tu présentes (20s/78s) me semble très très très important : tu travailles avec un TO7-70 ou tu fais tes tests en mode Debug ? Car pour comparer des perfs, vaut mieux compiler en mode release avec les optimisations de vitesses activées. Le compilateur fera beaucoup de choses intéressantes pour toi

@bertry : quel intérêt à la liste ? vecteur me semble assez intuitif ici.

Ce qui pourrait donner :

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
#include <iostream>
#include <ctime>
#include <vector>
 
void siPremier(int Pi , std::vector<int> & t, std::vector<int>&square );
 
int main()
{
   static const int TAILLE_TABLEAU = 10000000;
    std::vector<int> t; //tableau dynamique contenant les nombres premiers trouves
    std::vector<int> square;
    t.reserve(TAILLE_TABLEAU/2);
    square.reserve(TAILLE_TABLEAU/2);
    clock_t const T0 = clock();
    for (int i=3; i<TAILLE_TABLEAU; i+=2)
    {
        siPremier(i,t,square);
    }
    clock_t const TFin = clock();
    std::cout << "Duree                     = " << ((TFin-T0)*1000/CLOCKS_PER_SEC) << std::endl;
    std::cout << "Plus grand nombre premier trouve = " << t.back() << std::endl << std::endl << std::endl << std::endl << std::endl;
    return 0;
}
 
#include <cmath>
void siPremier(int Pi , std::vector<int> & t, std::vector<int>&square )
{
    const std::vector<int>::const_iterator it_end = t.end();
    std::vector<int>::const_iterator it_t = t.begin();
    std::vector<int>::const_iterator it_s = square.begin();
    while ((it_t!=it_end) && ((*it_s)<=Pi))
    {
        if (Pi%(*it_t)==0)
        {
            return;
        }
        ++it_t;
        ++it_s;
    }
    t.push_back(Pi);
    square.push_back(Pi*Pi);
}

**akorx** · 04/08/2011, 09h29

Tout d'abord merci à tous pour vos remarques éclairées... c'est plutôt motivant de se sentir épaulé lorsqu'on débute

.

Avant de parcourir plus en détail vos propositions de codage, commençons par cette fameuse remarque soulevée par 3DArchi concernant le using namespace std; que j'ai ajouté dans le header. Si j'essaie de m'en passer mon EDI qu'est code::blocks m'envoie balader de la sorte :

verifPremier.h :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
#ifndef VERIFPREMIER_H_INCLUDED
#define VERIFPREMIER_H_INCLUDED
 
//using namespace std;
 
void siPremier(int *Pi , vector<int> & t );
void autresiPremier(int r , vector<int> & t );
void message();
 
#endif // VERIFPREMIER_H_INCLUDED

Build messages :

Code :

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

1
2
3
4
error: 'vector' has not been declared
error: expected ',' or '...' before '<' token
error: 'vector' has not been declared
error: expected ',' or '...' before '<' token

J'avais essayé initialement de mettre cette ligne uniquement dans mon verifPremier.cpp mais il me jette pour les mêmes raison car il la veut dans le header...

Où est ce que ça cloche ? est ce une particularité de code::blocks ?

screetch · 04/08/2011, 10h03

il y a deux possibilités: le mettre dans un fichier CPP a la place, ou alors utiliser le nom complet de vector qui est std::vector

**akorx** · 04/08/2011, 10h06

Envoyé par screetch

il y a deux possibilités: le mettre dans un fichier CPP a la place, ou alors utiliser le nom complet de vector qui est std::vector

Mais il est dans mon .cpp ! et code::blocks veut que je l'ajoute également dans le .h ...

screetch · 04/08/2011, 10h29

oui parce que tu l'utilises dans le fichier .h aussi
dans le .h il faudrait utiliser le nom complet std::vector dans ce cas

d'ailleurs, comme tu te sers de vector dans le fichier .h, c'est la que tu devrais mettre #include <vector>idealement, le fichier header ne devrait pas contenir de "using namespace" (car on ne sait pas ou ca se propage) et on devrait inclure tous les fichiers dont on a besoin pour le faire fonctionner, pour qu'il soit "indépendant"

**akorx** · 04/08/2011, 10h54

Reprenons... vous allez me prendre pour un débile mais le ridicule ne tuant pas je me lance.

Y a surement un truc de base qui m'échappe. Déjà pourquoi le main.cpp fait il référence au verifPremier.h et non au verifPremier.cpp ? En effet la logique voudrait que le main.cpp "charge" le verifPremier.cpp qui à son tour intègre un verifPremier.h au début... mais bon sur le plan conventionnel je sais que ça ne se fait pas car on doit faire des#include vers les .h uniquement.
Dans les faits on a un main.cpp qui fait référence au verifPremier.h qui lui se débrouille pour trouver le verifPremier.cpp qui va bien... comment s'en sort il?

Dans mon exemple : que doivent contenir exactement le .h et .cpp ? sur plan théorique si je comprends bien le verifPremier..cpp ne devrait avoir aucun #include hormis le #include verifPremier.h car c'est ce dernier qui est sensé faire les #include nécessaire au .cpp... c'est bien ça ou je gauffre royalement ?

Moi j'ai ceci... ça marche ok mais est ce correct ?

verifPremier.h :

Code :

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

1
2
3
4
5
6
#ifndef VERIFPREMIER_H_INCLUDED
#define VERIFPREMIER_H_INCLUDED
 
void siPremier(int *Pi , std::vector<int> & t );
 
#endif // VERIFPREMIER_H_INCLUDED

verifPremier.cpp :

Code :

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

1
2
3
4
5
6
#include <iostream>
#include <cmath>
#include <vector>
#include "verifPremier.h"
 
using namespace std;

main.cpp :

Code :

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

1
2
3
4
#include <iostream>
#include <ctime>
#include <vector>
#include "verifPremier.h"

Aller, dites moi tout pour que mon "cas" serve d'exemple !

screetch · 04/08/2011, 11h16

reprenons; tes fichiers CPP sont compilés "indépendemment", puis une étape supplémentaire, plus tard, les "fusionne" pour faire un executable.

Si ils sont compilés indépendemment, ils n'ont qu'une connaissance limitée du programme global; par exemple ton fichier main.cpp ne connaît pas verifPremier.cpp, il ne sait pas ce qu'il y a dedans.

C'est un problème car main.cpp doit appeler une fonction qui est dans verifPremier.cpp

pour cela, il suffit de donner a main.cpp un "résumé" de ce qu'il y arua dans verifPremier.cpp; pas tout, juste ce dont tu peux avoir besoin. Bon, dans verifPremier.cpp il y a la fonction siPremier. Il n'y a pas besoin de donner le code a main.cpp, juste de dire que la fonction existe(ra).

Pour faire ca on crée un fichier "header", qui va lister/resumer tout ce que l'on trouve dans verifPremier.cpp (du moins, tout ce que l'on veut rendre public). Ainsi on a pas besoin de connaitre tout ce qu'il y a dans verifPremier.cpp, verifPremier.h nous en donne un résumé.

donc dans main.cpp on inclut verifPremier.h
Or, verifPremier.h utilise vector; il faut aussi inclure vector pour que le compilateur sache de quoi on parle. Soit on a du bol et ca a déjà été inclus avant (c'est ton cas; main.cpp et verifPremier.cpp ont tous les deux inclus vector) soit, verifPremier.h inclus aussi vector pour être sûr que dés que tu inclus verifPremier.h, tout le monde aura le "vector" sous la main.

Enfin, verifPremier.cpp n'a pas vraiment besoin de verifPremier.h dans ton cas, mais dans un cas plus compliqué (une classe en C++) il va aussi avoir besoin de son propre résumé. Ca permet de détecter des erreurs de declaration/définition; si le résumé dit "oh j'ai une fonction siPremier" mais que le fichier CPP définit avec une faute d'orthographe "siPérimé" alors le compilateur peut voir qu'il y a une erreur (ca marche seulement pour les classes, et c'est un peu la lecon suivante, donc pas la peine d'insister la dessus)

voila pourquoi on a un fichier verifPremier.h

**akorx** · 04/08/2011, 12h21

Quelques ultimes remarques :

1 - le mode release :

Les temps que tu présentes (20s/78s) me semble très très très important : tu travailles avec un TO7-70 ou tu fais tes tests en mode Debug ? Car pour comparer des perfs, vaut mieux compiler en mode release avec les optimisations de vitesses activées. Le compilateur fera beaucoup de choses intéressantes pour toi

Je viens de faire le test en release sur mon TO7-70 (

, nostalgie quand tu nous tiens... lol), y a pas photo les temps sont très nettement améliorés... un grand merci pour cette petite astuce que ne connaissais pas et qui peut grandement servir

.

2 - Le remplacement des carrés au lieu de racines carrées :

La remarque de 3Darchi concernant l'utilisation du carré au lieu de la racine carrée est également extrêmement judicieuse (le gain de temps au final est d'un facteur 2 !), encore fallait il y penser car on pense bien souvent qu'une opération en vaut une autre au niveau du temps alors que c'est loin d’être le cas et là moi je dis "chapeau bas" 3Darch

.

3 - Le mode release :

Par contre où actives tu l'option "optimisations de vitesses activées" dont tu parles ? je suppose qu'elle est cochée par défaut dans le mode release mais je préfère m'en assurer pour ma gouverne personnelle.

4 - Petite "pause" pour l'affichage du résultat :

Et tant que j'y suis : comment faire une véritable pause à la fin du programme le temps d'afficher les résultats (qui soit portable et non réservé à windows avec le classique :

#include<windows.h>
system("PAUSE");

5 - La méthode ".reserve()" :

En quoi la méthode ".reserve()" peut elle être intéressante dans la mesure ou j'utilise un tableau dynamique sur lequel par définition je ne connais pas la taille finale (je comprendrais bien evidemment la chose avec un tableau classique qui lui possède une taille statique).

6 - Truc bizarre sur la boucle du main() :

Reste une curiosité quand même concernant le test de toutes les valeurs via :
for (i=2; i<100000000; i++)
au lieu d'une sur deux via (pour éviter de faire le calcul sur les nombres pairs) :
for (i=3; i<100000000; i+=2)

Cela ne me fait gagner aucun temps... bizarre non dans la mesure ou l'on teste 2x moins de nombre ? bon il est vrai que le test nous éjecte dès le début car on vérifie si le nombre est divisible par 2 ("2" étant le permier élément du tableau contenant les nombres premiers trouvés la boucle ne va pas loin).

**3DArchi** · 04/08/2011, 20h11

Envoyé par akorx

1 - le mode release :

Faire des mesures de temps sans activer le mode release (et donc sans les optimisations de code) rend les données peu pertinentes. C'est comme si tu t'étonnais de marcher moins vite avec des bottes crottées et un sac de 30kg sur les épaules. Peu de sprinter font des 100m affublé d'un tel costume, tu en conviendras.

Envoyé par akorx

2 - Le remplacement des carrés au lieu de racines carrées :

En calcul mental, si tu es comme tout le monde, tu réussis mieux les multiplications que les divisions. C'est un peu pareil pour un micro.

Envoyé par akorx

3 - Le mode release :

Par contre où actives tu l'option "optimisations de vitesses activées" dont tu parles ? je suppose qu'elle est cochée par défaut dans le mode release mais je préfère m'en assurer pour ma gouverne personnelle.

Cela dépend de ton compilateur (gcc, visual C++, intel, etc...) et incidemment de ton IDE. En général, le mode release demande au compilateur de faire des optimisations. Et là, comme on ne peut pas avoir le beurre et l'argent du beurre, il faut choisir entre deux familles d'optimisations parfois contradictoires : diminuer la taille de l'exécutable ou favoriser le temps d'exécution.

Envoyé par akorx

4 - Petite "pause" pour l'affichage du résultat :

Pour rester indépendant de l'environnement windows, cf F.A.Q. Comment faire une pause (attendre que l'utilisateur tape une touche) ?

Envoyé par akorx

5 - La méthode ".reserve()" :

En quoi la méthode ".reserve()" peut elle être intéressante dans la mesure ou j'utilise un tableau dynamique sur lequel par définition je ne connais pas la taille finale (je comprendrais bien evidemment la chose avec un tableau classique qui lui possède une taille statique).

std::vector est un tableau dynamique, c'est à dire qu'à T0 il ne contient aucun élément. Ajouter des éléments nécessite de leur réserver de la place. Donc allouer un nouveau buffer, recopier les données de l'ancien buffer vers le nouveau et rajouter la nouvelle donnée. Même s'il y a des stratégies dans la cuisine interne de std::vector pour ne pas faire une telle allocation à chaque ajout, à plusieurs moment cette opération a lieu. Et elle peut ralentir ton programme. Ici tu sais que tu auras TAILLE_TABLEAU/2 au maximum. reserve permet de réserver un bloc d'au moins cette taille et éviter d'éventuelle allocation/copie pendant l'exécution.

Envoyé par akorx

6 - Truc bizarre sur la boucle du main() :

Reste une curiosité quand même concernant le test de toutes les valeurs via :
for (i=2; i<100000000; i++)
au lieu d'une sur deux via (pour éviter de faire le calcul sur les nombres pairs) :
for (i=3; i<100000000; i+=2)

Cela ne me fait gagner aucun temps... bizarre non dans la mesure ou l'on teste 2x moins de nombre ?

Oui. J'avais le regard embuée ce matin car effectivement les différences ne sont pas aussi significatives que j'en ai eu l'impression. J'avoue ne pas avoir réfléchi à ce point. J'ose une hypothèse mais sans filet : le cache et la grande localité données+instruction?

Envoyé par akorx

bon il est vrai que le test nous éjecte dès le début car on vérifie si le nombre est divisible par 2 ("2" étant le permier élément du tableau contenant les nombres premiers trouvés la boucle ne va pas loin).

**akorx** · 05/08/2011, 09h06

Hop hop hop 3Darchi tu as pourtant raison ! à partir du moment ou je ne soumets pas les valeurs de i suivantes :

3 4 5 6 7 8 9 10 11 12 13 14 15 16

mais celles-ci (c'est à dire sans les nombres pairs) :

3 5 3 7 9 11 13 15

... je divise ma "quantité de valeurs à analyser" par 2. Donc en théorie mon traitement devrait tout de même y gagné considérablement hors ce n'est pas le cas.

Bon ok, le programme total ne mettra bien évidemment pas 2x fois moins de temps en enlevant les chiffres pairs car ces derniers sont rapidement rejetés par la fonction verifPremier() (contrairement aux impairs qui eux nécessitent une analyse beaucoup plus longue car ils susceptibles d'être premiers).

NB : ce qui "dégoute" toujours un peu avec nos processeurs actuels c'est qu'on a beau avoir 4 cœurs ou même bientôt plus, ce type de petit programme ne tournera pas beaucoup plus vite que sur un antique pentium4 à fréquence égale...

**koala01** · 08/08/2011, 08h40

Au passage, quelques corrections "minimes"...

Lorsqu'un fichier est inclus dans un fichier d'en-tête qui est lui même inclus, on peut réellement parler d'inclusion indirecte, ce qui fait qu'il n'est pas nécessaire d'inclure à nouveau le fichier en question...

C'est d'ailleurs la raison pour laquelle il est préférable de ne pas utiliser la directive using namespace dans un fichier d'en-tête : avec le jeu des inclusions indirecte (le fichier étant inclus dans un fichier qui est lui-même inclus dans un autre, et ainsi de suite ), on ne sait absolument pas jusqu'où cette directive pourra remonter, et provoquer, pourquoi pas, des conflits, et, de toutes manières, perdre tout l'attrait des espaces de noms...

Au final, tes fichiers pourraient se composer de
verifPremier.h :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
/* indispensable pour pouvoir utiliser std::vector dans la déclaration 
 * de la fonction
 */
#include <vector>  
 
#ifndef VERIFPREMIER_H_INCLUDED
#define VERIFPREMIER_H_INCLUDED
/* pas de directive using namespace ici
 */
 
void siPremier(int *Pi , std::vector<int> & t );
 
#endif // VERIFPREMIER_H_INCLUDED

verifPremier.cpp

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
/* on profite de l'intégralité du contenu de verifPremier.h
 * ... y compris de l'inclusion de <vector>
 */
#include "verifPremier.h"
#include <cmath>
/* nous pourrions, éventuellement utiliser la directive
 * using namespace std;
 * mais bon, on s'habitue vite à utilisr le nom complet :D
 */
void siPremier(int Pi , std::vector<int> & t, std::vector<int>&square )
{
    /* copier / collé d'un code précédent, non corrigé */
    const std::vector<int>::const_iterator it_end = t.end();
    std::vector<int>::const_iterator it_t = t.begin();
    std::vector<int>::const_iterator it_s = square.begin();
    while ((it_t!=it_end) && ((*it_s)<=Pi))
    {
        if (Pi%(*it_t)==0)
        {
            return;
        }
        ++it_t;
        ++it_s;
    }
    t.push_back(Pi);
    square.push_back(Pi*Pi);
}

main.cpp

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
/* ici, on n'a pas besoin de <cmath> : on n'utilise aucune fonction
 * fournie par ce fichier
 *
 * par contre, nous avons besoin de verifPremier
 */
#include "verifPremier.h"
int main()
{
    /* copier / coller d'un code précédent */
   static const int TAILLE_TABLEAU = 10000000;
    std::vector<int> t; //tableau dynamique contenant les nombres premiers trouves
    std::vector<int> square;
    t.reserve(TAILLE_TABLEAU/2);
    square.reserve(TAILLE_TABLEAU/2);
    clock_t const T0 = clock();
    for (int i=3; i<TAILLE_TABLEAU; i+=2)
    {
        siPremier(i,t,square);
    }
    clock_t const TFin = clock();
    std::cout << "Duree                     = " << ((TFin-T0)*1000/CLOCKS_PER_SEC) << std::endl;
    std::cout << "Plus grand nombre premier trouve = " << t.back() << std::endl << std::endl << std::endl << std::endl << std::endl;
    return 0;
}

Optimisation de vitesse et correction syntaxique

C++

Discussions similaires

Partager

Partager