31 mars 2025
Le but de cet exercice est de :
Voici un exemple de statistiques obtenues sur 10.000 parties à 10 joueurs·ses s’affrontant à l’aide des 5 stratégies implantées dans ce simulateur :
---- Statistiques (sur 10000 simulations) ----
Nom strategie | Moyenne rangs | Moyenne vaches encaissees
Carte la plus petite | 5.73275 | 15
Carte au milieu de la main | 5.39285 | 14
Carte random | 5.99605 | 16
Carte avant la plus grande | 5.42985 | 14
Carte la plus grande | 4.94850 | 13
Ces statistiques suggèrent que la stratégie consistant à jouer systématiquement la carte la plus grande est la meilleure des stratégies. Ce résultat doit être nuancé par le fait que, dans ce simulateur, il y a toujours 2 joueurs·ses qui jouent, à chaque tour, la carte la plus grande, pendant que 2 joueur·ses jouent systématiquement la carte la plus petite. De ce fait, celles·ceux qui jouent leur carte la plus grande verrouille les rangées et obligent fréquemment celles·ceux qui jouent leur carte la plus petite à encaisser des vaches pour pouvoir placer leur carte.
Téléchargez l’archive SixQuiPrend.zip dans le répertoire de votre choix et exploitez-la selon la procédure cmake de ce document.
Dans la suite, vous travaillez essentiellement sur les fichiers
src/core/simulateur.cpp
et
src/core/simulateur.h
.
Au début d’une partie, la variable tas_cartes_initial
contient kNb_initial_cartes_en_main
numérotées de
1
à kNb_initial_cartes_en_main
et mélangées
:
Après distribution, chaque main de joueur·se contient
kNb_initial_cartes_en_main
cartes en provenance de
tas_cartes_initial
. Par ailleurs, kNb_rangees
rangées sont initialisées chacune avec une carte provenant de
tas_cartes_initial
. Dans la figure ci-après :
8
, la
carte 75
, la carte 103
et la carte
22
.Supposons que nous sommes parvenus au 3ème tour de jeu.
joueuse[0]
a décidé de jouer sa carte 40
,
joueuse[1]
la 5
, joueuse[2]
la
100
et joueuse[3]
la 76
.
rangees[0]
contient les cartes 8
,
15
, 20
, 23
et 27
,
tandis que rangees[1]
contient 75
et
77
, etc.
Durant chaque tour, les joueurs·ses jouent dans l’ordre croissant des
cartes qu’iels ont décidé de jouer. Donc, l’ordre de passage des
joueurs·ses pour ce 3ème tour est joueuse[1]
(carte 5
), joueuse[0]
(carte 40
),
joueuse[3]
(carte 77
) et
joueuse[3]
(carte 100
).
joueuse[1]
ne peut ajouter sa carte à une rangée, vu que sa
valeur est inférieure à la carte à droite de chaque rangée. Dans la
simulation, joueuse[1]
choisit systématiquement de ramasser
la rangée qui lui apporte le moins de vaches (symboles en haut et de
chaque rangée). Ramasser rangees[0]
lui infligerait une
pénalité de 8
vaches, rangees[1]
7
vaches, rangees[2]
1
vaches, et
rangees[3]
8
vaches. joueuse[1]
ramasse donc rangees[2]
et y met sa carte.
C’est au tour de joueuse[0]
. Iel doit jouer dans
rangees[0]
qui a déjà
kNb_max_cartes_dans_rangee
. joueuse[0]
ramasse
rangees[2]
et y met sa carte.
Dans simuler_partie(statistiques_t& stat)
,
définissez tas_cartes_initial
en tant que
std::vector<int>
contenant 104 valeurs et stockez-y
des valeurs allant de 1 à 104.
Complétez la fonction dump_cartes()
(cf. marque TODO
1 bis) pour qu’elle affiche les valeurs stockées dans le vecteur
v
passé en paramètre. Avec dump_cartes()
,
vérifiez que tas_cartes_initial
est correctement
initialisé. NB : Si vous souhaitez que vos entiers soient
systématiquement affichés sur 3 caractères et cadrés à droite, utilisez
cout << format("{:3} ", valeur_a_afficher);
Mélangez tas_cartes_initial
et vérifiez le mélange avec
dump_cartes()
.
std::iota
contient un exemple de mélange de vecteur.Initialisez maintenant le tableau joueuses
pour les
kNb_joueuses
qui seront simulées :
tas_cartes_initial
, la deuxième, les 10 suivantes,
etc.dump_cartes()
pour vérifier que les mains ont été
correctement initialisées.i
est initialisée à
strategie_joueuses[i].assign et std::ranges::sort devraient vous aider.
Initialisez les kNb_rangees
de rangees
.
Affichez-les avec dump_cartes()
pour vérifier que votre
code est correct.
choisir_carte()
(que nous
coderons plus tard).choisir_carte()
dans
simulateur.h
(marque TODO 4 bis) et, pour être
cohérent·e, au niveau de sa définition dans simulateur.cpp
(marque TODO 4 ter), décidez si le paramètre est passé en
copie, en référence ou en référence constante.joueuses
par ordre croissant de l’attribut
carte_pour_ce_tour
de chaque joueuse.std::ranges::sort est ton ami·e.
jouer_carte()
(que nous
coderons plus tard).jouer_carte()
dans
simulateur.h
(marque TODO 6 bis) et, pour être
cohérent·e, au niveau de sa définition dans simulateur.cpp
(marque TODO 6 ter), décidez si :
j
est passé en copie, en référence ou en
référence constante.rangees
est passé en copie, en référence
ou en référence constante.cout << "*** Etat a la fin du tour " << tour << endl;
joueuses
par ordre croissant de l’attribut
nb_vaches_encaissees
de chaque joueuse.<< "Classement des joueuses en fonction du nombre de vaches encaissees"
cout << endl;
int classement{0};
int dernier_nb_vaches_encaissees{-1};
int nb_joueuses_classees{0};
for (const auto &j : joueuses) {
++nb_joueuses_classees;
if (dernier_nb_vaches_encaissees < j.nb_vaches_encaissees) {
// La joueuse j n'est pas ex-aequo avec la joueuse precedente (ou bien c'est la premiere joueuse au classement)
= nb_joueuses_classees;
classement = j.nb_vaches_encaissees;
dernier_nb_vaches_encaissees }
<< std::format("{:3} vaches encaissees (Strategie {})", j.nb_vaches_encaissees,
cout (j.strategie))
get_nom_strategie<< endl;
[j.strategie].first += classement;
stat[j.strategie].second += j.nb_vaches_encaissees;
stat}
La fin de votre affichage devrait être désormais :
Classement des joueuses en fonction du nombre de vaches encaissees
0 vaches encaissees (Strategie Carte la plus petite)
0 vaches encaissees (Strategie Carte la plus petite)
0 vaches encaissees (Strategie Carte la plus petite)
0 vaches encaissees (Strategie Carte la plus petite)
0 vaches encaissees (Strategie Carte la plus petite)
0 vaches encaissees (Strategie Carte la plus petite)
0 vaches encaissees (Strategie Carte la plus petite)
0 vaches encaissees (Strategie Carte la plus petite)
0 vaches encaissees (Strategie Carte la plus petite)
Cet affichage n’est pas pertinent, car il vous manque encore le code de 4 fonctions. C’est l’objet de la prochaine section.
Dans cette section, nous implantons
get_nb_vaches(const cartes_t& cartes)
,
choix_carte()
, jouer_carte()
, et
get_rang_ou_jouer()
(dans cet ordre, pour aller de la plus
simple à la plus compliquée à coder).
Nous appliquons ici la même démarche que celle vue dans le Devoir Hors Présentiel de CSC4103 :
Pour ces tests comme pour tous les tests unitaires en C++ de cette UV, nous utilisons GoogleTest.
Suivez la procédure GoogleTest de ce document pour vérifier
le résultat des tests fournis dans src/test/unitTests.cpp
.
Sur les 14 tests effectés, seul 1 est correct. Il concerne la fonction
get_nb_vaches(int carte)
dont le code vous est déjà fourni,
car il n’apportait rien du point de vue manipulation des vecteurs.
get_nb_vaches(const cartes_t& cartes)
Voyons tout d’abord comment est codé le test de cette fonction. Dans
src/test/unitTests.cpp
, vous trouvez les lignes :
(get_nb_vaches, cartes) {
TESTconst cartes_t cartes{1, 15, 20, 44, 55, 104};
(19, get_nb_vaches(cartes));
EXPECT_EQ}
TEST(get_nb_vaches, ...)
est le nom de la fonction
concernée par ce test.TEST(..., cartes)
désigne le sous-cas testé par ce test
(ici, plusieurs cartes).const cartes_t cartes{1, 15, 20, 44, 55, 104};
est
notre jeu de données d’entrée. Dans le cas présent, c’est un ensemble
cartes
de cartes dont on cherche à connaître le nombre
total de vaches.EXPECT_EQ(19, get_nb_vaches(cartes));
est le test
lui-même :
EXPECT_EQ
désigne un test d’égalité. En cas d’erreur,
GoogleTest affichera les deux termes de
EXPECT_EQ
.EXPECT_EQ(19, ...)
est la valeur attendue pour ce
test.EXPECT_EQ(..., get_nb_vaches(cartes))
fait l’appel à la
fonction testée get_nb_vaches()
avec cartes
en
paramètre. La valeur renvoyée par cette fonction est la valeur observée
pour ce test et est comparée à la valeur attendue
(19
).Les tests unitaires fournis utilisent ASSERT_EQ
, alors
que :
assert*
de JUnit.assert_*
de cmocka.GoogleTest fournit également des ASSERT_*
.
Toutefois, comme expliqué dans cette
documentation :
Usually
EXPECT_*
are preferred, as they allow more than one failures to be reported in a test. However, you should useASSERT_*
if it doesn’t make sense to continue when the assertion in question fails.
cartes
, appelez
get_nb_vaches(int carte)
(qui est fournie).TEST(get_nb_vaches, cartes)
est désormais correct.choix_carte()
Comme cette fonction simule une joueuse choisissant une carte selon
une stratégie, il faut tester les différentes stratégies, soit plusieurs
tests TEST(choisir_carte, ...)
. Étudions un exemple de ces
tests de stratégie avec ce code issu de
src/test/unitTests.cpp
:
(choisir_carte, strategie_kCarte_la_plus_petite) {
TEST{
Joueuse jstrategie_t::kCarte_la_plus_petite,
{2, 4, 6},
0,
{},
0
};
(j);
choisir_carte
(cartes_t({4, 6}), j.main);
EXPECT_EQ(2, j.carte_pour_ce_tour);
EXPECT_EQ}
TEST(choisir_carte, strategie_kCarte_la_plus_petite)
:
Le test concerne la fonction choisir_carte
et le sous-cas
“Stratégie kCarte_la_plus_petite
”.Joueuse j{};
est notre jeu de données d’entrée. Dans le
cas présent, il est uniquement constituée d’une joueuse j
qui n’est pas const
, car choisir_carte
modifie
j
.choisir_carte(j);
invoque la fonction à tester.EXPECT_EQ(cartes_t({4, 6}), j.main);
définit la valeur
attendue cartes_t({4, 6})
pour j.main
.EXPECT_EQ(2, j.carte_pour_ce_tour);
définit la valeur
attendue 2
pour j.carte_pour_ce_tour
.src/test/unitTests.cpp
(marque TODO 10
bis), dans le test
TEST(choisir_carte, strategie_kCarte_la_plus_grande)
,
remplacez la ligne actuelle EXPECT_TRUE(false);
(qui
garantit que le test est toujours calculé comme faux) par un test
correct de la stratégie kCarte_la_plus_grande
.j.carte_pour_ce_tour
en fonction de
j.strategie
.
j.main
est
un vecteur trié.j.carte_pour_ce_tour
de j.main
(en veillant à garder j.main
trié)TEST(choisir_carte, ...)
sont désormais corrects.(choisir_carte, strategie_kCarte_la_plus_grande) {
TEST{
Joueuse jstrategie_t::kCarte_la_plus_grande,
{2, 4, 6},
0,
{},
0
};
(j);
choisir_carte
(cartes_t({2, 4}), j.main);
EXPECT_EQ(6, j.carte_pour_ce_tour);
EXPECT_EQ}
Un exemple vaut mieux qu’un long discours :
case kCarte_la_plus_petite:
.carte_pour_ce_tour = j.main.front();
jbreak;
A vous de coder les autres cas !
Essayez std::erase_if
en supprimant tous les éléments de j.main
qui sont égaux à
j.carte_pour_ce_tour
. NB : Nous le verrons dans la section
“Profiling du code pour l’optimiser” qu’il y a plus performant.
get_rang_ou_jouer()
NB : Le codage de cette fonction pourrait vous prendre du temps (car il faut assimiler correctement les règles du “6 qui prend”). Aussi, si vous avez l’impression d’être ou de prendre du retard, n’hésitez pas à copier-coller le code de la solution.
Concevez et plantez l’algorithme pour que cette fonction respecte :
Vérifiez que les tests unitaires
TEST(get_rang_ou_jouer, ...)
sont désormais corrects.
size_t get_rang_ou_jouer(const Joueuse& j, const rangees_t& rangees) {
// TODO 11
// Recherche rang tel que j.carte_pour_ce_tour est la plus proche de la
// derniere carte de la rangee.
size_t rang_ou_jouer = 0;
int diff = j.carte_pour_ce_tour - rangees[rang_ou_jouer].back();
for (size_t r = 1; r < kNb_rangees; ++r) {
if (0 < j.carte_pour_ce_tour - rangees[r].back() &&
.carte_pour_ce_tour - rangees[r].back() < diff) {
j= j.carte_pour_ce_tour - rangees[r].back();
diff = r;
rang_ou_jouer }
}
if (diff < 0) {
// La carte jouee est une carte trop faible par rapport aux cartes dans @p
// rangees
// ==> On choisit la rangee ou la joueuse encaisse le moins de vaches.
= 0;
rang_ou_jouer int encaissement = get_nb_vaches(rangees[rang_ou_jouer]);
for (size_t r = 1; r < kNb_rangees; ++r) {
if (get_nb_vaches(rangees[r]) < encaissement) {
= get_nb_vaches(rangees[r]);
encaissement = r;
rang_ou_jouer }
}
}
return rang_ou_jouer;
}
jouer_carte()
Après la ligne
size_t rang_ou_jouer{get_rang_ou_jouer(j, rangees)};
(déjà
fournie) :
j.cartes_encaissees
et
j.nb_vaches_encaissees
.j.carte_pour_ce_tour
dans cette
rangée.TEST(jouer_carte, ...)
sont désormais corrects.if (j.carte_pour_ce_tour < rangees[rang_ou_jouer].back()
|| rangees[rang_ou_jouer].size() >= kNb_max_cartes_dans_rangee) {
std::vector::clear
permet de vider un vecteur.Vérifiez que votre code fonctionne correctement en l’exécutant et en analysant vos traces.
Puis, dans src/main/main.cpp
, remplacez l’instruction
simuler_partie(stat);
par les lignes :
for (auto i = 0; i < kNb_simulations; ++i) {
(stat);
simuler_partie}
// Affiche les statistiques.
<< format("---- Statistiques (sur {} simulations) ----", kNb_simulations) << endl;
cout << format("{:30} | {:13} | {:25}", "Nom strategie",
cout "Moyenne rangs",
"Moyenne vaches encaissees")
<< endl;
for (const auto& [strategie, ses_stat] : stat) {
// Pour la moyenne, on doit diviser par 2 car chaque strategie
// est testee 2 fois durant chaque simulation de partie.
<< format("{:30} | {:13.5f} | {:25}", get_nom_strategie(strategie),
cout static_cast<double>(ses_stat.first) / 2 / kNb_simulations,
.second / 2 / kNb_simulations)
ses_stat<< endl;
}
Vérifiez que les statistiques désormais affichées sont cohérentes avec vos traces.
Puis, faites les modifications suivantes dans
src/core/simulateur.cpp
:
kNb_simulations
à 10'000
au
lieu de 1
(notez que le caractère '
peut
servir de séparateur de milliers pour améliorer la lisibilité).dump_cartes()
ou des appels à cout
.
NB : Ne mettez pas en commentaires les cout
présents dans
src/core/main.cpp
vu q’ils affichent les résultats de vos
simulations.Exécutez votre programme pour afficher les statistiques sur 10.000 simulations.
Corrigé (à exploiter
selon la procédure cmake
de ce document).
Maintenant que le code est opérationnel, nous allons repérer les sections de code où notre programme passe du temps, afin d’optimiser ces sections de code et donc améliorer le temps d’exécution. Pour ce faire, nous allons utiliser un “profiler de performances” qui nous permet de repérer les sections de code problématiques. Nous modifions le code et utilisons à nouveau le “profiler” pour vérifier le résultat de nos optimisations.
Afin de disposer à la fois d’une version non optimisée et d’une version optimisée de notre code (et ainsi pouvoir comparer les performances des codes réalisés):
src/core/simulateur_optimise.cpp
en
suivant la procédure “IDE CLion ou Visual Studio : Ajout de fichiers
source dans un projet généré par cmake” de ce document.src/core/simulateur.cpp
dans
src/core/simulateur_optimise.cpp
.
src/code/simulateur.cpp
,
mais en utilisant un flag de compilation
SIMULATEUR_OPTIMISE
. Nous ne le faisons pas pour
src/core/simulateur.cpp
afin de ne pas alourdir le code
avec des #ifdef
. Toutefois, nous le ferons pour
src/core/simulateur.h
et
src/test/unitTests.cpp
.src/core/CMakeLists.txt
(qui,
exceptionnellement, n’a pas été correctement modifié par votre IDE) par
les lignes :add_library(lib_core
simulateur.cpp
simulateur.h
)
target_include_directories(lib_core PUBLIC ./)
add_library(lib_core_optimise
simulateur_optimise.cpp
simulateur.h
)
target_include_directories(lib_core PUBLIC ./)
src/main/CMakeLists.txt
pour qu’il ait le
contenu suivant :add_executable(main
main.cpp
)
target_link_libraries(main lib_core)
add_executable(main_optimise
main.cpp
)
target_link_libraries(main_optimise lib_core_optimise)
Dans la suite de cette section, vous travaillerez sur
src/core/simulateur_optimise.cpp
.
Commencez par vérifier que :
kNb_simulations
est initialisé à 10'000
au
lieu de 1
.dump_cartes()
ou des appels à cout
sont
commentées.Lancez une session de profiling de CPU de
six_qui_prend_optimise
conformément aux instructions
pour Visual Studio ou celles
pour CLion. En résumé, pour Visual Studio :
Release
(cf. section
“Génération d’une version Release d’un programme” de ce document et exécutez
votre application dans ce mode.Dans la suite, nous supposons une session de profiling avec Visual Studio.
Votre programme s’exécute, puis Visual Studio affiche le rapport de sa session de diagnostic :
Sans surprise, simuler_partie()
représente
95,92%
de la consommation CPU totale (colonne “Temps
processeur total (unité, %)”). Toutefois, sa colonne “Temps UC exclusif
(unité, %)” qui représente la CPU consommée exclusivement dans
simuler_partie()
proprement dite et non dans les fonctions
qu’elle appelle n’est que de 10,88%
. Aussi, regardons les
autres fonctions signalées dans le rapport :
get_nb_vaches()
représente exclusivement
9,86%
.choisir_carte()
représente exclusivement
7,82%
.Cliquez sur get_nb_vaches
. Une fenêtre de diagnostic
concernant get_nb_vaches(int carte)
s’affiche :
Les différents tests effectués dans cette fonction représentent 10% de l’ensemble de la CPU du programme ! Que proposez-vous pour réduire drastiquement ce pourcentage ?
NB : Si vous souhaitez vérifier, avec les tests GoogleTest,
que vos modifications sont correctes, pensez à modifier
src/test/CmakeLists.txt
pour remplacer sa ligne
target_link_libraries(tests GTest::gtest_main lib_simulateur)
par
target_link_libraries(tests GTest::gtest_main lib_simulateur_optimise)
pour tester la version optimisée de votre bibliothèque.
Plutôt que de calculer à chaque fois le nombre de vaches, vous pouvez le calculer une bonne fois pour toutes, stocker le résultat obtenu dans un tableau qui fait office de cache à votre fonction.
Voici un exemple de code optimisé de
int get_nb_vaches(int carte)
(n’hésitez pas à discuter avec
l’intervenant·e, si vous ne comprenez pas certaines parties) :
// Pensez a ajouter #include <array>
int get_nb_vaches(int carte) {
static array<int, kNb_total_cartes + 1> carte2nb_vaches{
-1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 3, 5, 1, 1, 1, 2, 1, 1, 1,
1, 3, 1, 5, 1, 1, 2, 1, 1, 1, 1, 3, 1, 1, 5, 1, 2, 1,
1, 1, 1, 3, 1, 1, 1, 5, 2, 1, 1, 1, 1, 3, 1, 1, 1, 1,
7, 1, 1, 1, 1, 3, 1, 1, 1, 1, 2, 5, 1, 1, 1, 3, 1, 1,
1, 1, 2, 1, 5, 1, 1, 3, 1, 1, 1, 1, 2, 1, 1, 5, 1, 3,
1, 1, 1, 1, 2, 1, 1, 1, 5, 3, 1, 1, 1, 1};
return carte2nb_vaches[carte];
}
Dans la fenêtre de diagnostic initial, cliquez maintenant sur
choisir_carte
. Une fenêtre de diagnostic concernant
choisir_carte(Joueuse &j)
s’affiche :
Que proposez-vous pour réduire les différents pourcentages ?
Il y a deux pistes d’amélioration :
j.main
erase_if()
qui balaye l’ensemble du
tableau pour trouver les valeurs à supprimer, puis balaye à nouveau le
tableau pour les supprimer effectivement, utiliser
j.main.erase()
en indiquant l’index à supprimer : Vous ne
ferez ainsi qu’un seul balayage de j.main
.Voici un exemple de code optimisé de
choisir_carte(Joueuse &j)
(n’hésitez pas à discuter
avec l’intervenant·e, si vous ne comprenez pas certaines parties) :
void choisir_carte(Joueuse& j) {
// Fixe @a j.carte_pour_ce_tour en fonction de @a j.strategie.
// NB : @a j.main est triee par ordre croissant.
size_t index{0};
switch (j.strategie) {
using enum strategie_t;
case kCarte_la_plus_petite:
= 0;
index break;
case kCarte_au_milieu_main:
= j.main.size() / 2;
index break;
case kCarte_random:
{
static random_device rd;
static default_random_engine gen(rd());
(0, static_cast<int>(j.main.size() - 1));
uniform_int_distribution distrib= distrib(gen);
index break;
}
case kCarte_avant_la_plus_grande:
= j.main.size() - (j.main.size() > 1 ? 2 : 1);
index break;
case kCarte_la_plus_grande:
= j.main.size() - 1;
index break;
default:
assert(false);
}
.carte_pour_ce_tour = j.main[index];
j// Supprime @a j.carte_pour_ce_tour de @a j.main.
.main.erase(j.main.begin() + index);
j}
Fort de ces modifications de code, faisons un nouveau profiling pour voir le résultat de nos optimisations :
Ce nouveau rapport montre que get_rang_ou_jouer
représente exclusivement 9,26%
.
Cliquez sur get_rang_ou_jouer
. Une fenêtre de diagnostic
concernant
get_rang_ou_jouer(const Joueuse &j, rangees_t &rangees)
s’affiche :
Il permet de constater que :
if (0 < j.carte_pour_ce_tour - rangees[r].back() && j.carte_pour_ce_tour - rangees[r].back() < diff) {
consomme 5,56%
de CPU.if (get_nb_vaches(rangees[r]) < encaissement) {
et la
ligne encaissement = get_nb_vaches(rangees[r]);
consomme
3,36% + 1,34 = 4,50%
de CPU.Que proposez-vous ?
Il y a deux pistes d’amélioration :
j.carte_pour_ce_tour - rangees[r].back()
qui est calculé 3
fois dans cette fonction.rangees
devienne un vector<pair<cartes_t, int>>
, le
premier élément de la paire correspondant aux cartes dans cette rangée
et le second élément correspondant au nombre de vaches présentes dans
cette rangée. Ainsi, nous n’aurons plus besoin de la fonction
get_nb_vaches(const cartes_t &cartes)
(qui est coûteuse
du fait du balayage du tableau).Voici un exemple de code optimisé de
get_rang_ou_jouer(const Joueuse &j, rangees_t &rangees)
et jouer_carte(Joueuse &j, rangees_t &rangees)
(n’hésitez pas à discuter avec l’intervenant·e, si vous ne comprenez pas
certaines parties).
Dans src/code/simulateur.h
, la ligne
using rangees_t = std::vector<cartes_t>;
devient
:
//
// Fichier src/code/simulateur.h
//
#ifndef SIMULATEUR_OPTIMISE
using rangees_t = std::vector<cartes_t>;
#else // SIMULATEUR_OPTIMISE
using rangees_t = std::vector<std::pair<cartes_t,int>>; // first correspond aux cartes de la rangee,
// second correspond aux vaches encaissable dans cette rangee.
#endif// SIMULATEUR_OPTIMISE
src/code/simulateur_optimise.cpp
évolue de la manière
suivante :
//
// Fichier src/code/simulateur_optimise.cpp
//
#define SIMULATEUR_OPTIMISE // Ce #define est ajoute **avant** le #include "simulateur.h" pour influencer les lignes incluses.
#include "simulateur.h"
size_t get_rang_ou_jouer(const Joueuse &j, rangees_t &rangees) {
// Recherche rang tel que j.carte_pour_ce_tour est la plus proche de la
// derniere carte de la rangee.
size_t rang_ou_jouer = 0;
int diff = j.carte_pour_ce_tour - rangees[rang_ou_jouer].first.back();
for (size_t r = 1; r < kNb_rangees; ++r) {
if (auto diff_r = j.carte_pour_ce_tour - rangees[r].first.back();
0 < diff_r && diff_r < diff) {
= diff_r;
diff = r;
rang_ou_jouer }
}
if (diff < 0) {
// La carte jouee est une carte trop faible par rapport aux cartes dans @p
// rangees
// ==> On choisit la rangee ou la joueuse encaisse le moins de vaches.
= 0;
rang_ou_jouer for (size_t r = 1; r < kNb_rangees; ++r) {
if (rangees[r].second < rangees[rang_ou_jouer].second) {
= r;
rang_ou_jouer }
}
}
return rang_ou_jouer;
}
//
// // jouer_carte() est modifiee
//
void jouer_carte(Joueuse &j, rangees_t &rangees) {
size_t rang_ou_jouer{get_rang_ou_jouer(j, rangees)};
if (j.carte_pour_ce_tour < rangees[rang_ou_jouer].first.back() ||
[rang_ou_jouer].first.size() >= kNb_max_cartes_dans_rangee) {
rangees.cartes_encaissees.insert(j.cartes_encaissees.end(),
j[rang_ou_jouer].first.begin(),
rangees[rang_ou_jouer].first.end());
rangees.nb_vaches_encaissees += rangees[rang_ou_jouer].second;
j[rang_ou_jouer].first.clear();
rangees[rang_ou_jouer].second = 0;
rangees}
[rang_ou_jouer].first.push_back(j.carte_pour_ce_tour);
rangees[rang_ou_jouer].second += get_nb_vaches(j.carte_pour_ce_tour);
rangees}
//
// L'initialisation de rangees est modifiee
//
for (size_t i = 0; i < kNb_rangees; ++i) {
[i].first.push_back(
rangees[kNb_joueuses * kNb_initial_cartes_en_main + i]);
tas_cartes_initial[i].second = get_nb_vaches(rangees[i].first.front());
rangees// dump_cartes(rangees[i]);
}
Si vous souhaitez tester unitairement ces modifications, il faut également changer tous les tests unitaires qui utilisent des rangées :
//
// Fichier src/code/unitTests.cpp
//
#define SIMULATEUR_OPTIMISE // Ce #define est ajoute **avant** le #include "simulateur.h" pour influencer les lignes incluses.
#include "simulateur.h"
(get_rang_ou_jouer, la_carte_peut_etre_ajoutee_a_une_rangee) {
TESTconst Joueuse j{
strategie_t::kCarte_la_plus_grande,
{2, 4, 6},
42,
{},
0
};
#ifndef SIMULATEUR_OPTIMISE
const rangees_t rangees{
{6, 7, 8},
{38, 39, 40},
{50, 60},
{103, 104}
};
#else // SIMULATEUR_OPTIMISE
const rangees_t rangees{
{{6, 7, 8}, 3},
{{38, 39, 40}, 5},
{{50, 60}, 6},
{{103, 104}, 2}
};
#endif // SIMULATEUR_OPTIMISE
(1, get_rang_ou_jouer(j, rangees));
EXPECT_EQ}
(get_rang_ou_jouer, la_carte_est_trop_petite_et_doit_se_substituer_a_la_rangee_qui_rapporte_le_moins_de_vaches) {
TESTconst Joueuse j{
strategie_t::kCarte_la_plus_grande,
{2, 4, 6},
42,
{},
0
};
#ifndef SIMULATEUR_OPTIMISE
const rangees_t rangees{
{6, 7, 8, 98}, // Nombre de vaches = 4
{38, 39, 90}, // Nombre de vaches = 5
{50, 60}, // Nombre de vaches = 6
{103, 104} // Nombre de vaches = 2
};
#else // SIMULATEUR_OPTIMISE
const rangees_t rangees{
{{6, 7, 8, 98}, 4}, // Nombre de vaches = 4
{{38, 39, 90}, 5}, // Nombre de vaches = 5
{{50, 60}, 6},// Nombre de vaches = 6
{{103, 104}, 2} // Nombre de vaches = 2
};
#endif // SIMULATEUR_OPTIMISE
(3, get_rang_ou_jouer(j, rangees));
EXPECT_EQ}
(jouer_carte, la_carte_est_ajoutee_a_une_rangee_de_moins_de_5_cartes) {
TESTconst Joueuse j_init{
strategie_t::kCarte_la_plus_grande,
{2, 4, 6},
42,
{12, 13},
2
};
{j_init};
Joueuse j#ifndef SIMULATEUR_OPTIMISE
const rangees_t rangees_init{
{6, 7, 8},
{38, 39, 40},
{50, 60},
{103, 104}
};
#else // SIMULATEUR_OPTIMISE
const rangees_t rangees_init{
{{6, 7, 8}, 3},
{{38, 39, 40}, 5},
{{50, 60}, 6},
{{103, 104}, 2}
};
#endif // SIMULATEUR_OPTIMISE
rangees_t rangees{rangees_init};
(j, rangees);
jouer_carte
(j_init.main, j.main);
EXPECT_EQ(j_init.cartes_encaissees, j.cartes_encaissees);
EXPECT_EQ(j_init.nb_vaches_encaissees, j.nb_vaches_encaissees);
EXPECT_EQ(rangees_init[0], rangees[0]);
EXPECT_EQ#ifndef SIMULATEUR_OPTIMISE
(cartes_t({38, 39, 40, 42}), rangees[1]);
EXPECT_EQ#else // SIMULATEUR_OPTIMISE
(make_pair(cartes_t({38, 39, 40, 42}), 6), rangees[1]);
EXPECT_EQ#endif // SIMULATEUR_OPTIMISE
(rangees_init[2], rangees[2]);
EXPECT_EQ(rangees_init[3], rangees[3]);
EXPECT_EQ}
(jouer_carte, la_carte_est_ajoutee_a_une_rangee_de_5_cartes) {
TESTconst Joueuse j_init{
strategie_t::kCarte_la_plus_grande,
{2, 4, 6},
42,
{12, 13},
2
};
{j_init};
Joueuse j#ifndef SIMULATEUR_OPTIMISE
const rangees_t rangees_init{
{6, 7, 8},
{35, 36, 38, 39, 40},
{50, 60},
{103, 104}
};
#else // SIMULATEUR_OPTIMISE
const rangees_t rangees_init{
{{6, 7, 8}, 3},
{{35, 36, 38, 39, 40}, 8},
{{50, 60}, 6},
{{103, 104}, 2}
};
#endif // SIMULATEUR_OPTIMISE
rangees_t rangees{rangees_init};
(j, rangees);
jouer_carte
(j_init.main, j.main);
EXPECT_EQ(cartes_t({12, 13, 35, 36, 38, 39, 40}), j.cartes_encaissees);
EXPECT_EQ(10, j.nb_vaches_encaissees);
EXPECT_EQ(rangees_init[0], rangees[0]);
EXPECT_EQ#ifndef SIMULATEUR_OPTIMISE
(cartes_t({42}), rangees[1]);
EXPECT_EQ#else // SIMULATEUR_OPTIMISE
(make_pair(cartes_t({42}), 1), rangees[1]);
EXPECT_EQ#endif // SIMULATEUR_OPTIMISE
(rangees_init[2], rangees[2]);
EXPECT_EQ(rangees_init[3], rangees[3]);
EXPECT_EQ}
(jouer_carte, la_carte_se_substitue_a_une_rangee_de_cartes) {
TESTconst Joueuse j_init{
strategie_t::kCarte_la_plus_grande,
{2, 4, 6},
42,
{12, 13},
2
};
{j_init};
Joueuse j#ifndef SIMULATEUR_OPTIMISE
const rangees_t rangees_init{
{6, 7, 8, 98}, // Nombre de vaches = 4
{38, 39, 90}, // Nombre de vaches = 5
{50, 60}, // Nombre de vaches = 6
{103, 104} // Nombre de vaches = 2
};
#else // SIMULATEUR_OPTIMISE
const rangees_t rangees_init{
{{6, 7, 8, 98}, 4},// Nombre de vaches = 4
{{38, 39, 90}, 5}, // Nombre de vaches = 5
{{50, 60}, 6}, // Nombre de vaches = 6
{{103, 104}, 2} // Nombre de vaches = 2
};
#endif // SIMULATEUR_OPTIMISE
rangees_t rangees{rangees_init};
(j, rangees);
jouer_carte
(j_init.main, j.main);
EXPECT_EQ(cartes_t({12, 13, 103, 104}), j.cartes_encaissees);
EXPECT_EQ(4, j.nb_vaches_encaissees);
EXPECT_EQ(rangees_init[0], rangees[0]);
EXPECT_EQ(rangees_init[1], rangees[1]);
EXPECT_EQ(rangees_init[2], rangees[2]);
EXPECT_EQ#ifndef SIMULATEUR_OPTIMISE
(cartes_t({42}), rangees[3]);
EXPECT_EQ#else // SIMULATEUR_OPTIMISE
(std::make_pair(cartes_t({42}), 1), rangees[3]);
EXPECT_EQ#endif // SIMULATEUR_OPTIMISE
}
Fort de ces nouvelles modifications de code, faisons un nouveau profiling pour voir le résultat de nos optimisations :
Ce nouveau rapport montre que les get_rang_ou_jouer
représente exclusivement 9,26%
.
La sous-fenêtre “Chemin réactif” montre que le temps passé dans
simuler_partie
est lié au temps passé dans
jouer_carte
et dans std::ranges::_Sort_fn
:
Cliquer sur jouer_carte
montre qu’on ne peut plus
vraiment améliorer ce code :
En revanche, pour std::ranges::_Sort_fn
, en cliquant sur
son diagnostic :
on constate que le tri qui consomme de la CPU est un tri. Cliquez droit sur ce tri et demandez l’affichage du “Flame graph” :
Le tri qui pose souci est celui de joueuses
. En effet,
pour trier joueuses
, nous avons besoin de faire des
permutations de Joueuse_t
, ce qui est coûteux en CPU et en
mémoire. Il serait plus efficace de trier un tableau d’index sur
joueuses
.
Voici un exemple de code (à insérer dans
void simuler_partie(statistiques_t &stat) {
) optimisé
pour le tri de joueuses
(n’hésitez pas à discuter avec
l’intervenant·e, si vous ne comprenez pas certaines parties) :
// Initialisation d'un vecteur contenant des index dans @a joueuses. C'est ce
// vecteur qu'on trie pour obtenir @a joueuses trie sans utiliser
// ranges::sort(joueuses...)
<size_t>index_pour_joueuses_triees(kNb_joueuses);
vector(index_pour_joueuses_triees.begin(), index_pour_joueuses_triees.end(), 0);
iota
//
// Simulation des tours de jeu.
//
for (size_t tour = 1; tour <= kNb_initial_cartes_en_main; ++tour) {
// Chaque joueuse choisit sa carte.
for (auto &j : joueuses) {
(j);
choisir_carte}
// Trie @a index_pour_joueuses_triees pour connaitre @a joueuses trie
// de la plus petite à la plus grande carte_pour_ce_tour.
::sort(index_pour_joueuses_triees, [&joueuses](const auto &i1, const auto &i2) {
rangesreturn joueuses[i1].carte_pour_ce_tour < joueuses[i2].carte_pour_ce_tour;
});
// Chaque joueuse joue sa carte.
for (const auto &i : index_pour_joueuses_triees) {
(joueuses[index_pour_joueuses_triees[i]], rangees);
jouer_carte}
[...]
}
Par ailleurs, pour le mélange, peut-être aviez-vous la ligne
ranges::shuffle(tas_cartes_initial, std::mt19937{std::random_device{}()});
.
Si c’est le cas, remplacez-la par les lignes :
static random_device rd;
static mt19937 gen(rd());
::shuffle(tas_cartes_initial, gen); ranges
Au final, après ces différentes optimisations, pour 100.000 simulations compilées en mode Release :
Measure-Command { .\main.exe | Out-Default }
(/usr/bin/time ./.\main.exe
sous Linux,
time ./.\six_qui_prend.exe
sous macOS) affiche un temps
d’exécution de 2700
millisecondes.Measure-Command { .\main_optimise.exe | Out-Default }
affiche un temps d’exécution de 1800
millisecondes, soit
une réduction de 33%
du temps d’exécution .Corrigé (à exploiter
selon la procédure cmake
de ce document).