26 avril 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/manipulation_vecteurs.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
// Endafin 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 v1v0 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 contenur 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> quartile0map<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-ReleaseCMakeSettings.jsonx64-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 | ReleaseMesurez à 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.
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 !