1 Introduction

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 Construire un projet C++ avec cmake.

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.

2 Initialisation d’un vecteur (0h10)

Dans cette partie, vous codez (et comparez) 3 manières d’initialiser un vecteur :

• (TODO 1 Begin)
  • Définissez un vector de int nommé v0.
  • Peuplez v0 en y rangeant taille_vecteur valeurs retournées par distrib(gen).
• (TODO 2 Begin)
  • Définissez un vector de int nommé v1.
  • Invoquez la méthode vector::reserve pour réserver de la place pour taille_vecteur éléments dans v1
  • Peuplez v0 en y rangeant taille_vecteur valeurs retournées par distrib(gen)
• (TODO 3 Begin)
  • Définissez un vector de int nommé v2 en précisant qu’il faut le créer avec taille_vecteur valeurs initialisées à 0.
  • Peuplez 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 ?

3 Fusion de 2 vecteurs (0h10)

Dans cette partie, vous codez (et comparez) 2 manières d’ajouter le conteneur d’un vecteur à un autre vecteur :

• (TODO 4 Begin)
  • A l’aide d’une boucle for, ajoutez le contenu de v0 à v1.
• (TODO 5 Begin)
  • A l’aide de la méthode 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 ?

4 Moyenne des éléments d’un vecteur (0h10)

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)
  • Calculez somme avec une boucle for.
• (TODO 7 Begin)
  • Calculez 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)
  • Calculez 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)
  • Calculez 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 ?

5 Quartiles des éléments d’un vecteur (0h15)

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 !
  • Trier v0 avec une fonction de la STL.
  • Initialiser vector<int> quartile1 avec les 3 quartiles.
• (TODO 10 Begin) A faire seulement après la séance 2 qui forme aux map !
  • Définissez vector<int> quartile0
  • Définissez 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.
  • Balayer v0 pour peupler frequency.
  • Balayer 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 ?

6 Pour aller plus loin (0h10)

Vous avez testé les performances en mode Debug, donc avec un niveau d’optimisation faible. Créez une version Release de votre programme :

• Sous Visual Studio
  • Dans la barre de menu, cliquez sur la flèche à droite de x64-Debug et sélectionnez Gérer les configurations : Un onglet CMakeSettings.json s’ouvre.
  • Dans cet onglet, dans Configurations, cliquer sur le bouton “+” et sélectionnez x64-Release
  • Fermez l’onglet CMakeSettings.json
  • Dans la barre de menu, sélectionnez x64-Release à la place de x64-Debug : Votre projet est régénéré en mode Release.
• Sous CLion
  • Menu File > Setting : Une fenêtre de “Settings” s’ouvre.
  • Sélectionnez Build, Execution, Deployment > CMake : Le sous-menu CMake s’ouvre.
  • Dans la colonne de gauche des profils, là où il n’y a que la mention Debug, cliquez sur le bouton “+” : Un item Release est créé. Cliquez sur “OK”.
  • Patientez un peu le temps que le projet se régénère.
  • Dans la liste déroulante avec 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.

7 Conclusion

Corrigé (à exploiter selon la procédure Construire un projet C++ avec cmake).

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 !