31 mars 2024
Le but de cet exercice est de manipuler les vecteurs de la STL et vous donner peut-être l’envie d’approfondir par vous-même (cf. section “Conclusion”).
Téléchargez l’archive ManipulationVecteurs.zip dans le répertoire de votre choix et exploitez-la selon la procédure cmake de ce document.
²Pour cet exercice, vous ne travaillerez qu’avec le fichier
src/main/main.cpp
. Il contient un programme destiné à faire
des statistiques sur std::uniform_int_distribution
(le
générateur de nombres entiers aléatoires selon une distribution
uniforme, fourni par la STL). Pour ce faire, il tire au hasard
taille_vecteur
valeurs comprises entre 0 et
valeur_max
, valeurs qu’il stocke dans un tableau, tableau
sur lequel il fait ensuite des statistiques.
Le principe de cet exercice est que vous écriviez du code entre les différentes lignes
// TODO [numéro] Begin
// Ecrivez ici votre code pour ce Todo
// End
afin de faire ensuite des tests de performance en affichant, en
millisecondes, les temps elapsed
et cpu
qui
ont été consommés pour exécuter le code que vous avez écrit. NB : Si
vous ne comprenez pas la différence entre les temps elapsed
et cpu
, n’hésitez pas à poser des questions !
Recommandation : Pour l’instant, taille_vecteur
est
initialisé à 10. Gardez cette valeur, tant que vous n’êtes pas sûr·e que
votre programme fonctionne correctement. Quand il tournera correctement,
comme l’énoncé vous y invitera, vous augmenterez sa valeur pour des
mesures de performance plus pertinentes.
Dans cette partie, vous codez (et comparez) 3 manières d’initialiser un vecteur :
TODO 1 Begin
)
vector
de int
nommé
v0
.v0
en y rangeant taille_vecteur
valeurs retournées par distrib(gen)
.TODO 2 Begin
)
vector
de int
nommé
v1
.vector::reserve
pour réserver de la
place pour taille_vecteur
éléments dans
v1
v0
en y rangeant taille_vecteur
valeurs retournées par distrib(gen)
TODO 3 Begin
)
vector
de int
nommé
v2
en précisant qu’il faut le créer avec
taille_vecteur
valeurs initialisées à 0
.v2
avec une boucle for
qui fait
taille_vecteur
instructions
v2[i] = distrib(gen);
Quand vous estimez que votre programme fonctionne correctement (la
taille affichée pour les différents vecteurs est correcte), passez la
valeur de taille_vecteur
à 10'000
(pour
améliorer la lisibilité, C++ propose d’utiliser '
comme
séparateur des milliers), puis à 10'000'000
. NB : Si vous
ne comprenez pas la différence entre les temps elapsed
et
cpu
(tous deux affichés en millisecondes dans le cadre de
cet exercice), n’hésitez pas à poser des questions !
Que pensez-vous des résultats obtenus ? Selon vous, font-ils sens ?
Dans cette partie, vous codez (et comparez) 2 manières d’ajouter le conteneur d’un vecteur à un autre vecteur :
TODO 4 Begin
)
for
, ajoutez le contenu de
v0
à v1
.TODO 5 Begin
)
vector::insert
, ajoutez le
contenu de v0
à v2
. NB : Pour les itérateurs,
vu que vous n’utilisez pas ces itérateurs pour modifier le contenu de ce
vers quoi ils pointent, vous pouvez utiliser les itérateurs constants
cbegin()
/cend()
au lieu de
begin()
/end()
.Avant de tester votre programme pour vérifier son fonctionnement,
pensez à remettre taille_vecteur
à 10
.
Quand vous estimez que votre programme fonctionne correctement (la
taille affichée pour les vecteurs est correcte), passez la valeur de
taille_vecteur
à 10'000
, puis à
10'000'000
.
Que pensez-vous des résultats obtenus ? Selon vous, font-ils sens ?
Dans cette partie, vous codez (et comparez) 4 manières de calculer la
moyenne des éléments contenus dans le vecteur v0
. Pour
calculer cette moyenne, pour chaque TODO
, vous calculez la
somme des éléments de v0
dans la variable
long long somme{0};
que vous avons définie pour vous. Le
code (déjà fourni) calcule ensuite la moyenne avec
somme / v0.size()
.
Question préliminaire : Pourquoi la variable somme
est
de type long long
?
TODO 6 Begin
)
somme
avec une boucle for
.TODO 7 Begin
)
somme
avec la fonction
accumulate()
fournie par la STL. Pour information,
la section exemple de la documentation
de reduce
(oui, oui, reduce
, pas
accumulate
!) contient un exemple pertinent (il faut juste
y remplacer v.cend(), 0L
par
v.cend(), 0LL
).TODO 8 Begin
)
somme
avec la fonction reduce()
fournie par la STL. Pour information, la section exemple de la
documentation
de reduce
contient un exemple pertinent. NB : Durant
ces tests, l’auteur de ce sujet a trouvé qu’il manquait un paramètre
0LL
dans l’exemple.TODO 9 Begin
)
somme
avec la fonction reduce()
et son paramètre execution::par
. NB : Idem NB
précédent.Avant de tester votre programme pour vérifier son fonctionnement,
pensez à remettre taille_vecteur
à 10
.
Quand vous estimez que votre programme fonctionne correctement (la
moyenne affichée fait sens), passez taille_vecteur
à
10'000
, puis à 10'000'000
.
Que pensez-vous des résultats obtenus ? Selon vous, font-ils sens ?
Dans cette partie, vous codez (et comparez) 2 manières de calculer
les quartiles des éléments contenus dans le vecteur v0
.
Rappel : Le quartile 0
est l’entier tel que
25%
des éléments de v0
sont strictement
inférieurs à cet entier. Quant au quartile 1
, c’est
50%
, tandis que pour le quartile 2
, c’est
75%
.
TODO 11 Begin
) Oui, oui, 11, pas 10 !
v0
avec une fonction de la STL.vector<int> quartile1
avec les 3
quartiles.TODO 10 Begin
) A faire seulement après la
séance 2 qui forme aux map
!
vector<int> quartile0
map<int, int> frequency;
. La clé,
i.e. le premier élément de frequency
correspond à un
élément qui apparaît dans v0
; la valeur, i.e. le second
élément de frequency
correspond à la fréquence à laquelle
cet élément la clé apparaît dans v0
.v0
pour peupler frequency
.frequency
pour peupler
quartile0
.Avant de tester votre programme pour vérifier son fonctionnement,
pensez à remettre taille_vecteur
à 10
.
Quand vous estimez que votre programme fonctionne correctement (les
quartiles affichés font sens), passez taille_vecteur
à
10'000
, puis à 10'000'000
.
Que pensez-vous des résultats obtenus ? Selon vous, font-ils sens ?
Vous avez testé les performances en mode Debug, donc avec un niveau d’optimisation faible. Créez une version Release de votre programme :
x64-Debug
et sélectionnez
Gérer les configurations
: Un onglet
CMakeSettings.json
s’ouvre.Configurations
, cliquer sur le
bouton “+” et sélectionnez x64-Release
CMakeSettings.json
x64-Release
à la
place de x64-Debug
: Votre projet est régénéré en mode
Release.File
> Setting
: Une fenêtre de
“Settings” s’ouvre.Build, Execution, Deployment
>
CMake
: Le sous-menu CMake
s’ouvre.Debug
, cliquez sur le bouton “+” : Un item
Release
est créé. Cliquez sur “OK”.manipulation_vecteur | Debug
, vous pouvez maintenant
sélectionner Release
, puis sélectionner
manipulation_vecteur | Release
Mesurez à nouveau les performances pour taille_vecteur
valant 10
, 10'000
et
10'000'000
.
Que pensez-vous des résultats obtenus ? Selon vous, font-ils sens ?
Idéalement, testez sur une autre plateforme (par exemple, si vous êtes sous Windows, testez sous Linux, par exemple en Windows Subsystem Linux). Vous constaterez qu’une plateforme n’est pas toujours plus performante qu’une autre selon la plateforme. C’est parce que la STL n’est pas implémentée de la même manière selon le compilateur ! Certains industriels décident donc d’implémenter leur propre STL pour en faire une version plus adaptée à leurs propres besoins/plateformes cibles.
Corrigé (à
exploiter selon la procédure cmake
de ce document).
Nous espérons vous avoir convaincu·e que connaître les fonctions de la STL permet d’écrire du code plus concis, potentiellement moins bugué (vu que d’autres utilisateurs·trices l’ont déjà testé), voire plus performant. C’est pourquoi nous vous invitons à lire rapidement la page Bibliothèque d’algorithmes, simplement pour prendre connaissance de la variété des fonctions disponibles (par exemple, trouver une valeur, compter le nombre d’occurrences, recopier en sens inverse, etc.). Ainsi, face à certains problèmes, vous saurez qu’il faut chercher dans cette bibliothèque d’algorithmes. Selon nous, il ne fait aucun doute que le temps perdu à chercher dans cette bibliothèque et à comprendre comment utiliser l’une de ses fonctions vaut la chandelle !