Je m'entraine actuellement a l'utilisation d'un ECS grâce a l'exercice Javaquarium et le code proposer par Gbdivers sur son site (sur le quel je me suis appuyé pour toute la base du système)
Comme dit sur son site, le découpage en fonction n'est pas complètement fait, et j'ai quand même fini par me détacher de son code pour apporter ma propre touche, je souhaiterais donc avoir vos critiques sur mon code avant de passer a l'étape des sauvegardes dans fichier
Le code fait environ 400 lignes avec l'indentations, pour eviter un post trop long (& pour essayer pour la première fois GitHub) voici le reposit :
Plutôt que d'utiliser systématiquement std::pair et std::tuple, ce qui n'est pas une mauvaise idée en soi, mais qui manque cruellement d'expressivité (tu dois en permanence te souvenir de quelle information se trouve à quelle position de la paire / tuple), pourquoi ne ferais tu pas des structures?
Cela te faciliterait énormément la vie d'avoir quelque chose comme
struct living{
type type_data;
hp hp_data;
age age_data;
};
struct living_component{
id id_data;
living living_Data;
}
using all_types = std::vector<living_component>;
Cela ne fera que te permettre de gagner en expressivité, dans le sens où, au lieu d'avoir une fonction
et cela ne pourrait qu'améliorer la compréhension du code
Une deuxième chose : lorsque tu ajoute tes composants, tu crées systématiquement une nouvelle entité. C'est une approche "raisonnable" dans certaines situation.
Mais tu aurais sûrement intérêt à prévoir la possibilité de rajouter un composant à une entité existante, ce qui te permettrait de travailler dans un ordre proche de
/* 1 - je crée l'entité
*/
auto temp_id=create_entity();
/* 2 - je crée un composant spécifique pour cette entité
*/
add_seaweed(temp_id, 10);
Enfin, les variable globales C'EST MAL... il faudrait faire "quelque chose" pour y remédier (peut être créer une structure Aquarium, qui les regrouperait toutes, dont tu créerais une instance dans main, et que tu transmettrait à toutes les fonctions qui en ont besoin ???
Et, pour ce qui est de la découpe des fonctions, je dirais qu'il n'y a qu'en définitive que spend_time qui en fait définitivement trop à cause de sa boucle interne.
Cette boucle devrait être prise en charge par une fonction particulière, ce qui te permettrait de "simplifier" ta fonction sous une forme proche de
void spend_time(std::vector<id> const& fishs, std::vector<id> const& seaweeds)
{
ecs::hp_update();
ecs::age_update();
/* je n'ai pas vraiment fait attention, mais ces deux
* distributions devront peut être aller dans la
* fonction
*/
std::uniform_int_distribution<size_t> fish_dist(0, fishs.size() - 1);
std::uniform_int_distribution<size_t> seaweed_dist(0, seaweeds.size() - 1);
fish_spend_time(/* paramètre nécessaires */ );
}
Ce qui se conçoit bien s'énonce clairement. Et les mots pour le dire viennent aisément.Mon nouveau livre : Coder efficacement - Bonnes pratiques et erreurs à éviter (en C++)Avant de faire ce que tu ne pourras défaire, penses à tout ce que tu ne pourras plus faire une fois que tu l'auras fait
J'ai donc ajouter la structure "Aquarium" pour virer les variables globales, et remplacer les tuples/pairs par des structures comme tu me la conseiller
Pour ce qui ai d’implémenter un moyen pour ajouter des composants à une entité, je garde cela de coter pour quand je devrais gérer le fait d'ajouter des entités a un tour donner (la suite de l'exo)
J'aurais deux questions :
- Maintenant que j'ai enlevé les 4 vecteurs qui étaient en global, je dois aussi retirer ceci ? (qui sont aussi en global)
- En fesant les modifs, je me suis rendu compte d'un bug qui est apparu en codant les fonctions, ce qui ma forcer a quelques modifications :
void fish_spend_time(Aquarium & aquarium, std::vector<id> const& fishs, std::vector<id> const& seaweeds, std::vector<id> & trash)
{
std::uniform_int_distribution<size_t> fish_dist(0, fishs.size() - 1);
std::uniform_int_distribution<size_t> seaweed_dist(0, seaweeds.size() - 1);
for (auto & fish : fishs)
{
sexe_update(aquarium, fish);
auto & fish_type{ get_component(aquarium._types, fish) };
if (is_famished(fish_type) && !is_dead(fish_type))
{
auto fish_race{ get_component(aquarium._races, fish) };
if (is_carnivorous(fish_race.race_data) && !fishs.empty())
{
eat_fish(aquarium, fish_type, random_entity(fish_dist, fishs), trash);
}
else if (is_herbivorous(fish_race.race_data) && !seaweeds.empty())
{
eat_seaweed(aquarium, fish_type, random_entity(seaweed_dist, seaweeds), trash);
}
}
else if (!is_famished(fish_type) && !is_dead(fish_type))
{
fish_reproduce(aquarium, fish, random_entity(fish_dist, fishs));
}
}
}
void spend_time(Aquarium & aquarium, std::vector<id> & fishs, std::vector<id> & seaweeds)
{
hp_update(aquarium);
age_update(aquarium);
fishs = get_fishs(aquarium); //Mise a jour apres morts dans les updates
seaweeds = get_seaweeds(aquarium); //Mise a jour apres morts dans les updates
std::vector<id> entity_dead;
fish_spend_time(aquarium, fishs, seaweeds, entity_dead);
seaweed_reproduce(aquarium, seaweeds);
delete_entities(aquarium, entity_dead);
}
}
int main() {
ecs::Aquarium aquarium;
for (size_t i{}; i < 5; i++) { ecs::add_seaweed(aquarium); };
for (size_t i{}; i < 5; i++)
{
const auto race{ ecs::random_race() };
ecs::add_fish(aquarium, ecs::to_string(race), race, ecs::random_sexe());
}
std::cout << "Tourt\tEntitees\tAlgue\tHerbivores\tCarnivores" << std::endl;
for (size_t tour{}; tour < 20; ++tour)
{
auto fishs{ ecs::get_fishs(aquarium) };
auto seaweeds{ ecs::get_seaweeds(aquarium) };
const auto herbivorous{ ecs::get_herbivorous(aquarium, fishs) };
const auto carnivorous{ ecs::get_carnivorous(aquarium, fishs) };
ecs::print(tour, aquarium._entities.size(), seaweeds.size(), herbivorous.size(), carnivorous.size());
ecs::spend_time(aquarium, fishs, seaweeds);
}
std::cout << "===== Time Out ===== " << std::endl;
return 0;
}
A l'origine, les vecteurs "fishs", "seaweeds", "herbivorous" et "carnivorous" (ces deux derniers n'ont pour but que l'affichage) etaient créés après la mise a jour des points de vies et de l'age (et donc la suppresion des poissons/algues mortes), maintenant qu'ils sont creer avant (surtout "fishs" et "seaweeds") je me suis retrouvés avec une erreur, vu qu'on cherche a utiliser des poissons/algues mortes.
La solution a donc été de recharger ces deux vecteurs après les mises a jours, je ne peux pas les declarer apres (donc dans la fonction spend_time) puisqu'ils sont necessaires a l'affichage, mais cela est-ce propre ? (vu que sa force a recherché les poissons/algues une fois de plus)
(L'affichage, et la declaration de "carnivorous" et "herbivorous" se fait maintenant avant que le temps passe pour eviter de devoir rechercher encore une fois les vecteurs "fishs" et "seaweeds", vu que des entités sont supprimer pendant la fonction spend_time, rendant hs les vecteurs "fishs" et "seaweeds" declarer au debuts)
En esperant avoir été clair (même si j'en doute beaucoup)
Autant que faire se peut, il faut effectivement les retirer...
Pourquoi n'en ferais tu pas des données membre (au moins pour _random_negine) de ton aquarium, en veillant à l'initialiser correctement à la construction ?
Car, finalement, l'aquarium correspond au "contexte" dans lequel les algues et les poissons vont vivre, non?
- En fesant les modifs, je me suis rendu compte d'un bug qui est apparu en codant les fonctions, ce qui ma forcer a quelques modifications :
void fish_spend_time(Aquarium & aquarium, std::vector<id> const& fishs, std::vector<id> const& seaweeds, std::vector<id> & trash)
{
std::uniform_int_distribution<size_t> fish_dist(0, fishs.size() - 1);
std::uniform_int_distribution<size_t> seaweed_dist(0, seaweeds.size() - 1);
for (auto & fish : fishs)
{
sexe_update(aquarium, fish);
auto & fish_type{ get_component(aquarium._types, fish) };
if (is_famished(fish_type) && !is_dead(fish_type))
{
auto fish_race{ get_component(aquarium._races, fish) };
if (is_carnivorous(fish_race.race_data) && !fishs.empty())
{
eat_fish(aquarium, fish_type, random_entity(fish_dist, fishs), trash);
}
else if (is_herbivorous(fish_race.race_data) && !seaweeds.empty())
{
eat_seaweed(aquarium, fish_type, random_entity(seaweed_dist, seaweeds), trash);
}
}
else if (!is_famished(fish_type) && !is_dead(fish_type))
{
fish_reproduce(aquarium, fish, random_entity(fish_dist, fishs));
}
}
}
void spend_time(Aquarium & aquarium, std::vector<id> & fishs, std::vector<id> & seaweeds)
{
hp_update(aquarium);
age_update(aquarium);
fishs = get_fishs(aquarium); //Mise a jour apres morts dans les updates
seaweeds = get_seaweeds(aquarium); //Mise a jour apres morts dans les updates
std::vector<id> entity_dead;
fish_spend_time(aquarium, fishs, seaweeds, entity_dead);
seaweed_reproduce(aquarium, seaweeds);
delete_entities(aquarium, entity_dead);
}
}
int main() {
ecs::Aquarium aquarium;
for (size_t i{}; i < 5; i++) { ecs::add_seaweed(aquarium); };
for (size_t i{}; i < 5; i++)
{
const auto race{ ecs::random_race() };
ecs::add_fish(aquarium, ecs::to_string(race), race, ecs::random_sexe());
}
std::cout << "Tourt\tEntitees\tAlgue\tHerbivores\tCarnivores" << std::endl;
for (size_t tour{}; tour < 20; ++tour)
{
auto fishs{ ecs::get_fishs(aquarium) };
auto seaweeds{ ecs::get_seaweeds(aquarium) };
const auto herbivorous{ ecs::get_herbivorous(aquarium, fishs) };
const auto carnivorous{ ecs::get_carnivorous(aquarium, fishs) };
ecs::print(tour, aquarium._entities.size(), seaweeds.size(), herbivorous.size(), carnivorous.size());
ecs::spend_time(aquarium, fishs, seaweeds);
}
std::cout << "===== Time Out ===== " << std::endl;
return 0;
}
A l'origine, les vecteurs "fishs", "seaweeds", "herbivorous" et "carnivorous" (ces deux derniers n'ont pour but que l'affichage) etaient créés après la mise a jour des points de vies et de l'age (et donc la suppresion des poissons/algues mortes), maintenant qu'ils sont creer avant (surtout "fishs" et "seaweeds") je me suis retrouvés avec une erreur, vu qu'on cherche a utiliser des poissons/algues mortes.
La solution a donc été de recharger ces deux vecteurs après les mises a jours, je ne peux pas les declarer apres (donc dans la fonction spend_time) puisqu'ils sont necessaires a l'affichage, mais cela est-ce propre ? (vu que sa force a recherché les poissons/algues une fois de plus)
(L'affichage, et la declaration de "carnivorous" et "herbivorous" se fait maintenant avant que le temps passe pour eviter de devoir rechercher encore une fois les vecteurs "fishs" et "seaweeds", vu que des entités sont supprimer pendant la fonction spend_time, rendant hs les vecteurs "fishs" et "seaweeds" declarer au debuts)
En esperant avoir été clair (même si j'en doute beaucoup)
Merci pour ton aide
- Edité par K4kugen il y a moins de 30s
Peut-être te compliques tu tout simplement trop les choses en voulant maintenir une liste des entités qui sont mortes???
Parce que, je dis cela, je ne dis rien mais... quand un poisson décide de manger "quelque chose", on connait non seulement l'identifiant de l'entité qu'il mange, mais aussi ... le type de cette entité, me trompes-je?
Ne serait-ce pas le moment idéal pour faire "tout ce qu'il peut y avoir lieu de faire" lorsqu'une entité est mangée?
Ce qui se conçoit bien s'énonce clairement. Et les mots pour le dire viennent aisément.Mon nouveau livre : Coder efficacement - Bonnes pratiques et erreurs à éviter (en C++)Avant de faire ce que tu ne pourras défaire, penses à tout ce que tu ne pourras plus faire une fois que tu l'auras fait
C'est noter, je vais donc ajouter cela a la structure Aquarium
Pour "tout ce qu'il peut y avoir lieu de faire", oui je pourrais directement supprimer l'entité mangée (si elle en est morte) de l'aquarium et du vecteur "fishs" ou "seaweeds" selon le type (si c'est bien cela que tu sous-entend)
Mais si je fais cela, ma boucle principale
for (auto & fish : fishs)
{
sexe_update(aquarium, fish);
auto & fish_type{ get_component(aquarium._types, fish) };
if (is_famished(fish_type) && !is_dead(fish_type))
{
auto fish_race{ get_component(aquarium._races, fish) };
if (is_carnivorous(fish_race.race_data) && !fishs.empty())
{
eat_fish(aquarium, fish_type, random_entity(fish_dist, fishs), trash);
}
else if (is_herbivorous(fish_race.race_data) && !seaweeds.empty())
{
eat_seaweed(aquarium, fish_type, random_entity(seaweed_dist, seaweeds), trash);
}
}
else if (!is_famished(fish_type) && !is_dead(fish_type))
{
fish_reproduce(aquarium, fish, random_entity(fish_dist, fishs));
}
}
va (sauf erreur ?) casser si je supprime un poisson du vecteur "fishs" pendant que je le parcours, j'ai donc mis en place la liste d'entité morte pour pouvoir les supprimer a la fin de la boucle
Si cette boucle ne casse pas, alors oui, je supprimerais l'entité de l'aquarium et du vecteur correspondant a son type dés qu'elle meurt
Enfin, si, je sais... mais où serait le plaisir si je ne te laissais pas chercher un peu?
Peut-être un tableau n'est il pas forcément le mieux adapté, si la suppression d'une entité risque (effectivement) d'invalider un de tes itérateurs?
Ou, peut-être, peut-tu agir différemment en fonction de différents facteur?
si c'est une algue d'une part
et, si c'est un poisson, agir en fonction de s'il se trouve avant ou après ton itérateur courant dans ton tableau?
EDIT: ou peut-être y a-t-il moyen de tirer un parti intéressant des algorithme remove et remove_if?
Je ne sais pas, hein? j'explore les possibilités
- Edité par koala01 13 avril 2018 à 19:43:17
Ce qui se conçoit bien s'énonce clairement. Et les mots pour le dire viennent aisément.Mon nouveau livre : Coder efficacement - Bonnes pratiques et erreurs à éviter (en C++)Avant de faire ce que tu ne pourras défaire, penses à tout ce que tu ne pourras plus faire une fois que tu l'auras fait
Enfin, si, je sais... mais où serait le plaisir si je ne te laissais pas chercher un peu?
En effet, et c'est comme ça qu'on apprend
Donc pour éviter d'invalider les iterateurs, la solution serait une liste
Je remplace donc le tableau de poissons par une liste, me permettant de supprimer les poissons au fur et à mesure de leurs morts sans casser ma boucle.
Pour les algues, je peux directement supprimer a leur morts
Sur la théorie, je vois un seul point sombre (même si j'en appercois quelque autre, surtout avec hp_update/age_update *), le tirage aléatoire des poissons a manger ne peux se faire dans une liste, vu que je ne peux directement accéder a un élément. Une solution serait de tirer aléatoirement un nombre et d’itérer jusqu’à la place dans la liste pour récupérer le poissons ?
Apres quelque test/recherche, je n'ai pas trouver quelque chose de probant avec std::remove/std::remove_if, l’élément est supprimé et les iterateurs ne sont pas invalider, mais le dernier élément est copier pour conserver la taille (du moins c'est ce que j'ai compris et vu), il faudrait alors garder un compteur pour ne pas itérer jusqu’à la fin, ce qui semble très galère, mais j'ai l'impression d'avoir louper quelque chose
*Pour les problème que j'entrevois, c'est que dans hp_update et age_update, j'utilise aussi le principe de tableau d'entité morte. Viens alors deux choix :
- Supprimer les entités dès leur mort ici aussi, il faudrait alors changer certain tableaux par des listes (je ne sais pas si sa aura des répercussion, je regarde cela demain) + regarder comment mettre a jour liste/tableau de poissons/algues (puisqu'ils sont initialisés avec les entitées avant suppression)
- Laisser comme ca + regarder comment mettre a jour liste/tableau de poissons/algues (puisqu'ils sont initialisés avec les entitées avant suppression)
J'ai l'impression de partir dans tous les sens, j'espere rester un minimum lisible et comprehensible
Merci beaucoup pour ton aide, et ton exploration des possibilités
Enfin, si, je sais... mais où serait le plaisir si je ne te laissais pas chercher un peu?
En effet, et c'est comme ça qu'on apprend
Donc pour éviter d'invalider les iterateurs, la solution serait une liste
Je remplace donc le tableau de poissons par une liste, me permettant de supprimer les poissons au fur et à mesure de leurs morts sans casser ma boucle.
Ou peut-être prendre en compte les faits que:
la taille du tableau et sa capacité sont deux choses différentes
un itérateur n'est invalidé que si l'on modifie la capacité du tableau
que l'on n'est pas forcément obligé de garder les éléments d'un tableau absolument dans l'ordre d'origine
que l'on peut intervertir deux éléments du tableaux sans invalider les itérateurs
qu'il se peut que les algorithmes de la SL ne soient pas forcément adaptés à nos besoins
Je pense à une technique bien particulière en mettant tous ces points en évidence... mais je vais te laisser chercher un peu
Pour les algues, je peux directement supprimer a leur morts
Effectivement
Sur la théorie, je vois un seul point sombre (même si j'en appercois quelque autre, surtout avec hp_update/age_update *), le tirage aléatoire des poissons a manger ne peux se faire dans une liste, vu que je ne peux directement accéder a un élément. Une solution serait de tirer aléatoirement un nombre et d’itérer jusqu’à la place dans la liste pour récupérer le poissons ?
Effectivement la liste nous permet un accès avec une complexité en O(N), ce qui implique que le temps pour accéder à un élément particulier depuis un autre est proportionnel au nombre d'éléments à parcourir.
En termes de performances, c'est l'une des pires solutions qui soient
Par comparaison, les tableaux permettent un accès avec une complexité en O(1), ce qui signifie "en temps constant": il ne faut pas plus de temps pour passer d'un élément particulier à celui qui se trouve cent cases plus loin qu'il n'en faut pour passer d'un élément particulier à celui qui se trouve juste à coté (du moins en théorie, si cela ne provoque pas un "cache miss" au niveau du processeur)
En termes de performances, c'est la meilleure situation qui soit
Mais, peut être disposons nous de collection pour lesquelles l'accès serait --certes -- plus lent que celui d'un tableau, mais malgré tout beaucoup plus rapide que celui d'une liste, car l'accès à un élément particulier pourrait se faire avec une complexité en O(N log(N) ) ?
Apres quelque test/recherche, je n'ai pas trouver quelque chose de probant avec std::remove/std::remove_if, l’élément est supprimé et les iterateurs ne sont pas invalider, mais le dernier élément est copier pour conserver la taille (du moins c'est ce que j'ai compris et vu), il faudrait alors garder un compteur pour ne pas itérer jusqu’à la fin, ce qui semble très galère, mais j'ai l'impression d'avoir louper quelque chose
C'est donc que les algorithmes de la SL ne sont effectivement pas forcément adaptés
Mais as-tu pris en compte le fait que remove_if renvoie normalement un itérateur sur l'élément qui suit l'emplacement auquel se trouvait l'élément supprimé à l'origine, et que tu peux incrémenter et décrémenter les itérateurs d'un tableau?
*Pour les problème que j'entrevois, c'est que dans hp_update et age_update, j'utilise aussi le principe de tableau d'entité morte. Viens alors deux choix :
- Supprimer les entités dès leur mort ici aussi, il faudrait alors changer certain tableaux par des listes (je ne sais pas si sa aura des répercussion, je regarde cela demain) + regarder comment mettre a jour liste/tableau de poissons/algues (puisqu'ils sont initialisés avec les entitées avant suppression)
- Laisser comme ca + regarder comment mettre a jour liste/tableau de poissons/algues (puisqu'ils sont initialisés avec les entitées avant suppression)
Quoi que tu fasse, n'oublie pas:
de respecter scrupuleusement le SRP : si cela signifie créer une fonction iterator removeIfDead(iterator &, iterator &), qu'il en soit ainsi
qu'il vaut mieux, dans un premier temps, quelque chose qui fonctionne correctement mais lentement, que quelque chose qui fonce rapidement dans un mur
Ce qui se conçoit bien s'énonce clairement. Et les mots pour le dire viennent aisément.Mon nouveau livre : Coder efficacement - Bonnes pratiques et erreurs à éviter (en C++)Avant de faire ce que tu ne pourras défaire, penses à tout ce que tu ne pourras plus faire une fois que tu l'auras fait
J'avoue ne pas vraiment voir de que type de collection tu parles qui a avec une complexité de O(N log(N)) pour l’accès a un élément spécifique qui autorise des suppressions sans invalider les itérateurs (j'ai trouver les arbres de recherches, mais pas de suppressions du coup)
Ensuite, j'avoue que la technique dont tu parles a piquer ma curiosité, après mes recherches, j'ai trouver un petit truc comme ça :
int main() {
std::vector<size_t> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
for (auto it = v.begin(); it != v.end(); it++)
{
if (*it == 2)
{
std::remove(v.begin(), v.end(), 4);
v.pop_back();
}
}
for (auto & i : v)
{
std::cout << i << ' ';
}
return 0;
}
Cela permet bien de supprimer un élément du vecteur sans invalider les itérateurs, était-ce la technique a laquelle tu pensais ?
J'avoue ne pas vraiment voir de que type de collection tu parles qui a avec une complexité de O(N log(N)) pour l’accès a un élément spécifique qui autorise des suppressions sans invalider les itérateurs (j'ai trouver les arbres de recherches, mais pas de suppressions du coup)
L'invalidation des itérateurs est un problème spécifique à la notion même de "tableau"...
Tous les autres concepts correspondant à celui de "collection permettant de maintenir un nombre d'éléments connus à l'exécution" (dont fait partie le concept de tableau, d'ailleurs) sont exempt de ce "problème"
Si bien que n'importe quel classe correspondant à ce concept et utilisant un arbre binaire de recherche fera l'affaire
Ensuite, j'avoue que la technique dont tu parles a piquer ma curiosité, après mes recherches, j'ai trouver un petit truc comme ça :
int main() {
std::vector<size_t> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
for (auto it = v.begin(); it != v.end(); it++)
{
if (*it == 2)
{
std::remove(v.begin(), v.end(), 4);
v.pop_back();
}
}
for (auto & i : v)
{
std::cout << i << ' ';
}
return 0;
}
Cela permet bien de supprimer un élément du vecteur sans invalider les itérateurs, était-ce la technique a laquelle tu pensais ?
On commence à s'en rapprocher... Seulement, si l'on accepte de déroger au SRP juste le temps d'un petit test, et que l'on fait en sorte que l'affichage ait lieu dans la boucle de retrait de l'élément sous une forme proche de
int main() {
std::vector<size_t> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
for (auto it = v.begin(); it != v.end(); it++)
{
if (*it == 2)
{
std::remove(v.begin(), v.end(), 4);
v.pop_back();
}
std::cout << *it << ' ';
}
return 0;
}
nous obtiendrons le résultat
$ ./a.out
0 1 2 3 5 6 7 8 9
ce qui n'est pas tout à fait ce que l'on espérait, vu que 2 n'aurait pas du apparaître dans le lot
Je me permet donc de rappeler (et de préciser) deux points qui semblent t'avoir échappé:
que l'on peut intervertir deux éléments du tableaux sans invalider les itérateurs
qu'il se peut que les algorithmes de la SL (surtout ceux qui ont pour objectif d'enlever des éléments) ne soient pas forcément adaptés à nos besoins
Pour être honnête, la technique à laquelle je pense nécessitera d'adapter la logique de manière à prendre en compte l'interversion des éléments (car l'élément auquel on a accès au travers de l'itérateur après inversion doit aussi être mis à jour par spend_time, s'il ne l'a pas déjà été), mais permettrait en revanche (si on s'y prend correctement) malgré tout de supprimer tous les poissons morts d'un coup.
Ce qui se conçoit bien s'énonce clairement. Et les mots pour le dire viennent aisément.Mon nouveau livre : Coder efficacement - Bonnes pratiques et erreurs à éviter (en C++)Avant de faire ce que tu ne pourras défaire, penses à tout ce que tu ne pourras plus faire une fois que tu l'auras fait
Ouppsss... j'avais pas fais attention à ca.... j'ai été au moins aussi distrait que toi sur ce coup
On présumes que l'idée de ton test était bel et bien de supprimer le 2, non ?
Corrigeons donc cette erreur d'attention:
int main() {
std::vector<size_t> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
for (auto it = v.begin(); it != v.end(); it++)
{
if (*it == 2)
{
std::remove(v.begin(), v.end(), 1);
v.pop_back();
}
std::cout << *it << ' ';
}
return 0;
}
qui nous donne bien le résultat escompté. Mais que se passe-t-il réellement à l'intérieur de notre tableau ???
pour essayer de le découvrir, je te propose de supprimer la ligne v.pop_back() (qui supprime le dernier élément du tableau), ce qui nous donnerait un code proche de
int main() {
std::vector<size_t> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
for (auto it = v.begin(); it != v.end(); it++)
{
if (*it == 2)
{
std::remove(v.begin(), v.end(), 1);
}
std::cout << *it << ' ';
}
return 0;
}
et nous obtenons alors le résultat (pas étonnant du tout) de
$ ./a.out
0 1 3 4 5 6 7 8 9 9
Qu'est ce que cela nous apprend? que std::remove a fait exactement ce que l'on attendait de lui:
Il a supprimé l'élément qui avait la valeur 2, puis, pour ne pas laisser "une case vide" au "milieu du jeu de quille", il a décalé tous les éléments suivant d'une case "vers la gauche".
Pas de bol, ca, c'est une action qui présente typiquement une complexité en O(N) : le nombre d'itérations (et donc le temps nécessaire à l'exécution de ces itérations) est directement proportionnel au nombre d'élément qu'il faudra "décaler".
Sur dix éléments, cela peut encore aller, vu que le décalage d'un élément est particulièrement rapide. Mais, quand il y aura 10 000 ou 100 000 éléments à décaler (ou plus encore), on va assister à une (très) sérieuse baisse des performances,
La méthode à laquelle je pense permet, à défaut de garder les éléments dans le même ordre (mais est-ce vraiment indispensable?) de tout faire en temps constant (avec une complexité en O(1) ), et donc de garantir des performances égales (*) quel que puisse être le nombre d'éléments dans le tableau.
(*) sous réserve qu'il n'y ai pas de cache misses, bien sur
Avec toutes les informations que je t'ai données, il ne te manque qu'un algorithme fournit par la bibliothèque standard (std::swap) pour trouver la solution "par toi-même". Mais si tu n'y arrive décidément pas, je me résoudrai à te la donner
Ce qui se conçoit bien s'énonce clairement. Et les mots pour le dire viennent aisément.Mon nouveau livre : Coder efficacement - Bonnes pratiques et erreurs à éviter (en C++)Avant de faire ce que tu ne pourras défaire, penses à tout ce que tu ne pourras plus faire une fois que tu l'auras fait
Par contre, je t'avoue ne pas trop voir comment faire si le poisson à supprimer est avant le poissons en cours d'update, vu qu'apres le swap, le poisson de la fin se retrouvera avant l'actuel poisson, et ne sera donc pas actualiser
J'interviens juste pour le main. On peut encore faire mieux et il y a un bug (les 2 en fin sont déplacés mais pas supprimés).
Le swap échange 2 éléments. Sauf qu'ensuite l'élément est supprimé. Ce qui veut dire qu'une des valeurs n'est pas utile et on pourrait simplement déplacer la valeur de fin: std::swap( *it, *(v.rbegin()) ) -> *it = std::move(v.rbegin()).
v.resize(v.size() - 1) revient à faire un v.pop_back() en plus compliqué.
Concernant le bug:
Avec cette suite: 2, 3, 2
le premier et le dernier 2 sont échangés (aucun changement)
le dernier élément est supprimé: 2, 3
on avance l'itérateur: on est sur 3 et il reste un 2 -> bug
Avant de déplacer le premier élément, il faut chercher l'élément qui n'est pas un 2 dans l'intervalle [position de fin ; position courante]. Normalement, l'élément de fin pourrait être un itérateur qu'on décrémente et au final faire cont.erase(position_fin, cont.end()) pour supprimer les éléments du conteneur.
Au passage, il y a std::iter_swap pour faire un swap sur la valeur d'un itérateur.
Allez, comme tu as presque tout trouvé, je vais te donner la solution
L'idée, c'est, comme tu as fini par le découvrir, d'utiliser l'idiome "swap and resize", mais de ne pas tout faire en même temps...
Je m'explique: dans un premier temps, on va simplement "évacuer" les poissons morts vers "la fin" du tableau en les intervertissant avec le "dernier poisson en vie".
puis, comme lastValid contient désormais un poisson mort (donc invalide), on va le faire "avancer" vers le poisson juste après, qui est bel et bien valide, ce qui donne un code proche de
D'un autre coté, il va falloir tenir compte de la position de toRemove par rapport à la position du poisson qui l'a mangé, comme tu l'as si bien fait remarquer.
Soit, toRemove arrive après le poisson qui l'a mangé (dans le tableau), soit il se trouve entre le début du tableau et le poisson qui l'a mangé.
Dans le premier cas, il n'y a pas à s'inquiéter du fait que l'on sait qu'il faudra s'arrêter au plus tard après avoir traité lastValid (car tous les poissons qui suivent sont morts, et qu'il n'y a donc plus rien à faire pour eux).
Dans le deuxième cas, c'est plus embêtant, car tous les poissons qui se trouvent entre le début du tableau et le poisson qui a bouffé ont déjà été "mis à jour": ils ont eu l'occasion de bouffer s'ils avaient faim, ils ont eu l'occasion de niquer s'ils n'avaient rien d'autre à faire
Mais le poisson qui est désormais accessible au travers de toRemove, le pauvre, il n'a pas eu l'occasion de le faire:P Pour rétablir l'équilibre, il faut donc que l'on se souvienne, d'une manière ou d'une autre, qu'il faut lui donner l'occasion de passer son temps.
On a (au moins) solutions pour y arriver, mais le principe sera toujours le même et nécessitera toujours de connaître au moins deux choses, qui sont:
La position du poisson représenté par toRemove (mais ca, on l'a) et
l'intervalle entre le début du tableau et le poisson qui a bouffé
Si bien que la fonction finale pourrait ressembler à
bool eat_fish(iterator begin, iterator active, itérator & target, reverse_iterator &lastValid){
/* si la cible n'est pas morte, il n'y a rien à faire
*/
if(is_dead(target){
/* sinon, on inverse la cible avec le dernier
* élément valde
*/
std::swap(*target, *lastValid);
/* et comme l'itérateur lastValid contient désormais
*... un élément invalide, on le fait passer
* à l'élément suivant
*/
++lastValid;
/* "y a plus qu'à" déterminer si target doit
* pouvoir passer son temps
*/
return std::distance(begin, target)< (std::distance(begin, active);
}
return false
}
Il faut juste faire attention avec cette fonction, parce qu'elle occasionne non pas un effet de bord, mais elle en occasionne carrément deux (ou du moins potentiellement)!!!: un sur target et l'autre sur lastValid.
!!!CETTE FONCTION NE PEUT EN AUCUN CAS ÊTRE UTILISEE DANS PAR PLUSIEURS THREADS !!! (du moins, en l'état)
Mais elle fait le job
Maintenant que cette fonction est définie dans son intégralité, il est temps de modifier un peu spend_time pour lui permettre de fonctionner avec elle.
Une des possibilités (sans prendre encore en compte le retour de la fonction, j'y reviendrai par après) pourrait être de changer le type de la boucle, pour obtenir quelque chose du proche de
/* je ne fais que changer le type de la boucle et adapter
* l'appel de la fonction à sa nouvelle signature
*/
void fish_spend_time(Aquarium & aquarium,
std::vector<id> & fishs, std::vector<id> & seaweeds)
{
iterator fishBegin = fishs.begin();
iterator fishActive= fishBegin();
reverse_iterator lastValid = fishs.rbegin();
bool again{true};
while(again){
std::uniform_int_distribution<size_t> seaweed_dist(0, seaweeds.size() - 1);
std::uniform_int_distribution<size_t> fish_dist(0, fishs.size() - 1);
sexe_update(aquarium, *it);
auto & fish_type{ get_component(aquarium._types, *it) };
/* je le laisse pour mémoire, mais is_dead n'a plus
* d'intérêt dans le cas présent
*/
if (is_famished(fish_type) && !is_dead(fish_type)){
auto fish_race{ get_component(aquarium._races, *it) };
if (is_carnivorous(fish_race.race_data) && !fishs.empty()){
eat_fish(begin, active, random_iterator(aquarium, fish_dist, fishs),lastValid);
}else if (is_herbivorous(fish_race.race_data) && !seaweeds.empty()){
eat_seaweed(aquarium, fish_type, random_entity(aquarium, seaweed_dist, seaweeds), seaweeds);
}
/* idem... is_dead n'a plus vraiment d'intérêt */
}else if (!is_famished(fish_type) && !is_dead(fish_type)){
fish_reproduce(aquarium, *it, random_entity(aquarium, fish_dist, fishs));
}
if(*active != *lastValid){
++active;
}else{
again=false;
}
}
/* arrivé ici, tous les éléments qui viennent après lastValid (dans le sens normal
* du parcours) sont morts. On peut donc les supprimer
*/
auto sizeToRem=std::distance(fishs.rbegin(), lastValid);
fishs.resize(fishs.size()-sizeToRem);
}
Seulement, la fonction telle qu'elle est là ne permet pas encore aux poissons qui n'ont pas eu l'occasion de passer leur temps de le faire.(mais je ne l'ai montrée qu'à "titre intermédiaire", pour que tu comprenne cette partie spécifique de la modification )
D'ailleurs, c'est bien simple: tu auras remarqué que je n'ai pas récupéré la valeur renvoyée par eat_fish... Il est donc temps de s'occuper de cette valeur de retour.
Deux possibilités (au minimum) s'offrent à nous:
La première "relativement" simple consisterait à "garder une trace" (par exemple dans un tableau) de tous les poissons qui n'ont pas eu l'occasion de manger, et une boucle exactement identique pour leur donner l'occasion de le faire. Seulement, on ne peut pas ignorer le fait que, avec un peu de (mal)chance un des poissons qui n'a pas eu l'occasion de bouger se retrouve, une fois encore, relégué à une place à laquelle il n'aura pas l'occasion de le faire.
La deuxième solution est "plus complexe" car elle fait intervenir la notion de récursivité. Mais cette notion peut nous faciliter énormément la vie :D.
Ce que l'on appelle la récursivité, c'est la capacité que peut avoir une fonction à s'appeler elle-même. Seulement, si on n'y fait pas attention, elle risque de s'appeler elle-même "jusqu'à la fin des temps" (ou, pour être plus réaliste, jusqu'au plantage de l'application :P) Il faut donc trouver le cas dans lequel elle ne devra pas s'appeler "une fois de plus" de manière à "briser le cercle vicieux". Ce cas est généralement appelé le cas de base, et c'est la première possibilité à évacuer.
Dans le cas présent, pour être tout à fait précis, nous allons utiliser ce que nous pourrions appeler de la "récursivité indirecte", car nous allons avoir deux fonctions: une fonction une première fonction qui va se charger de ... faire bouger les poissons, et qui fera appel à une deuxième fonction qui a pour but spécifique de faire en sorte qu'un poisson mange un autre poisson.
Et c'est cette fonction qui fera en sorte, si elle se rend compte que le poisson qui "a pris la place de la cible" risque de passer son tour, de faire appel à la première fonction pour ce poisson spécifique.
Hein? quoi? c'est tordu? Oui, j'avoue... Mais j'aime bien diviser pour mieux régner :D
Commencons donc par la fonction qui s'occupe spécifiquement de faire en sorte qu'un poisson mange un autre poisson..
/* sea est fourni parce qu'on en aura besoin
* pour appeler fish_move
*/
void fish_eat_fish(iterator begin, iterator active,
iterator &target,
reverse_iterator & lastValid,
std::vector<id> &seaweeds){
/* je passe par une variable intermédiaire
* pour la compréhension, mais ce n'est pas
* indispensable
*/
bool needMove{eat_fish(begin, active, target, lastActive)};
/* le cas de bas: si le poisson ne doit pas bouger
* (dans l'immédiat), on peut quitter la récursivité
*/
if(! needMove){
return;
}
/* arrivé ici, on sait que "target" doit pouvoir
* bouger
*/
fish_move(begin, target, seaweeds, false);
}
et la fonction qui fera appel à fish_eat_fish prendra la forme de
Tu l'aura remarqué, cette fonction ressemble étrangement à ta fonction fish_spend_time telle que je l'ai modifiée... En fait, elle prend l'ensemble de la boucle en charge, avec juste une adaptation du comportement en cas de poisson carnivore, et le petit paramètre suppélmentaire (multiple) qui permet de déterminer s'il faut continuer à boucler ou non
Comme fish_spend_time n'a désormais plus à s'occuper de la boucle, nous pouvons la simplifier en
Au passage, je viens de constater un bug potentiel dans ton code: ta fonction random_iterator ne prend pas en compte le poisson qui est occupé à bouger.
Si bien que l'itérateur renvoyé pourrait tout aussi bien etre... le poisson qui bouge lui-même. Ce qui serait embêtant, car cela signifierait qu'il se bouffe lui-même
Ce qui se conçoit bien s'énonce clairement. Et les mots pour le dire viennent aisément.Mon nouveau livre : Coder efficacement - Bonnes pratiques et erreurs à éviter (en C++)Avant de faire ce que tu ne pourras défaire, penses à tout ce que tu ne pourras plus faire une fois que tu l'auras fait
bool eat_fish(Aquarium & aquarium, iterator begin, iterator active, iterator & target,
reverse_iterator & lastValid) {
auto & eater_type{ get_component(aquarium._types, *active) };
auto & target_type{ get_component(aquarium._types, *target) };
if (!is_dead(target_type))
{
get_hp(eater_type) += 5;
get_hp(target_type) -= 4;
if (is_dead(target_type)) {
/* sinon, on inverse la cible avec le dernier
* élément valde
*/
std::swap(*target, *lastValid);
/* et comme l'itérateur lastValid contient désormais
*... un élément invalide, on le fait passer
* à l'élément suivant
*/
++lastValid;
/* "y a plus qu'à" déterminer si target doit
* pouvoir passer son temps
*/
return std::distance(begin, target) < std::distance(begin, active);
}
}
return false;
}
void fish_eat_fish(Aquarium & aquarium, iterator begin, iterator active, iterator & target,
reverse_iterator & last_valid, std::vector<id> fishs, std::vector<id> & seaweeds);
void fish_move(Aquarium & aquarium, iterator begin, iterator active, reverse_iterator & last_valid, std::vector<id> & fishs, std::vector<id> & seaweeds, bool multiple = true)
{
bool again{ true };
while (again)
{
std::uniform_int_distribution<size_t> seaweed_dist(0, seaweeds.size() - 1);
std::uniform_int_distribution<size_t> fish_dist(0, fishs.size() - 1);
sexe_update(aquarium, *active);
auto & fish_type{ get_component(aquarium._types, *active) };
if (is_famished(fish_type))
{
auto fish_race{ get_component(aquarium._races, *active) };
if (is_carnivorous(fish_race.race_data) && (fishs.size() - std::distance(last_valid - 1, fishs.rbegin() + 1)) > 1) {
fish_eat_fish(aquarium, begin, active, random_iterator(aquarium, fish_dist, fishs, active), last_valid, fishs, seaweeds);
}
else if (is_herbivorous(fish_race.race_data) && !seaweeds.empty()) {
eat_seaweed(aquarium, fish_type, random_entity(aquarium, seaweed_dist, seaweeds), seaweeds);
}
}
else if (!is_famished(fish_type))
{
fish_reproduce(aquarium, *active, random_entity(aquarium, fish_dist, fishs));
}
if (*active != *last_valid && multiple)
{
++active;
}
else
{
again = false;
}
}
}
void fish_eat_fish(Aquarium & aquarium, iterator begin, iterator active, iterator & target,
reverse_iterator & last_valid, std::vector<id> fishs, std::vector<id> & seaweeds)
{
bool need_move{ eat_fish(aquarium, begin, active, target, last_valid) };
if (!need_move)
{
return;
}
fish_move(aquarium, begin, active, last_valid, fishs, seaweeds, false);
}
void fish_spend_time(Aquarium & aquarium, std::vector<id> & fishs, std::vector<id> & seaweeds)
{
iterator fish_begin = fishs.begin();
iterator fish_active = fish_begin;
reverse_iterator last_valid = fishs.rbegin();
fish_move(aquarium, fish_begin, fish_active, last_valid, fishs, seaweeds);
auto sizeToRem = std::distance(fishs.rbegin(), last_valid);
fishs.resize(fishs.size() - sizeToRem);
}
Pour le bug, il est resolu en modifiant la fonction random_iterator :
iterator random_iterator(Aquarium & aquarium, std::uniform_int_distribution<size_t> & dist, std::vector<id> & entities, iterator exclusion)
{
iterator it;
do {
it = entities.begin() + dist(aquarium._random_engine);
} while (it == exclusion);
return it;
}
Meler au fait que avant l'appel, on verifie si il existe au moins 2 poissons valides
Pour le bug de jo_link_noir, j'avoue ne pas trop voir ce qui deconne, le but n'etant pas de tous supprimer, normal qu'il reste quelque chose non ?
Je vais adapater le swap - resize pour les fonctions hp_update et age_update, afin de pouvoir supprimer la mise a jour des vecteurs seaweeds et fishs
Par contre, vu que c'est une methode que je decouvre, j'ai voulu reecrire ton code "a ma sauce", il resemble beaucoup au tient avec deux trois truc changer :
bool need_update(iterator active, iterator target)
{
return std::distance(active, target) < 0;
}
void fish_eat_fish(Aquarium & aquarium, iterator active, iterator & target,
reverse_iterator & last_valid, std::vector<id> & fishs, std::vector<id> & seaweeds);
void update_fish(Aquarium & aquarium, iterator active, reverse_iterator & last_valid, std::vector<id> & fishs, std::vector<id> & seaweeds)
{
std::uniform_int_distribution<size_t> seaweed_dist(0, seaweeds.size() - 1);
std::uniform_int_distribution<size_t> fish_dist(0, fishs.size() - 1);
sexe_update(aquarium, *active);
auto & fish_type{ get_component(aquarium._types, *active) };
if (is_famished(fish_type))
{
auto fish_race{ get_component(aquarium._races, *active) };
if (is_carnivorous(fish_race.race_data) && (fishs.size() - std::distance(last_valid - 1, fishs.rbegin() + 1)) > 1) {
fish_eat_fish(aquarium, active, random_iterator(aquarium, fish_dist, fishs, active), last_valid, fishs, seaweeds);
}
else if (is_herbivorous(fish_race.race_data) && !seaweeds.empty()) {
eat_seaweed(aquarium, fish_type, random_entity(aquarium, seaweed_dist, seaweeds), seaweeds);
}
}
else if (!is_famished(fish_type))
{
fish_reproduce(aquarium, *active, random_entity(aquarium, fish_dist, fishs));
}
}
void update_fishs(Aquarium & aquarium, iterator begin, reverse_iterator & last_valid,
std::vector<id> & fishs, std::vector<id> & seaweeds)
{
for (iterator active{ begin }; *active != *last_valid; ++active)
{
update_fish(aquarium, active, last_valid, fishs, seaweeds);
}
}
void eat_fish(Aquarium & aquarium, iterator active, iterator & target,
reverse_iterator & lastValid)
{
auto & eater_type{ get_component(aquarium._types, *active) };
auto & target_type{ get_component(aquarium._types, *target) };
get_hp(eater_type) += 5;
get_hp(target_type) -= 4;
if (is_dead(target_type)) {
/* sinon, on inverse la cible avec le dernier
* élément valde
*/
std::swap(*target, *lastValid);
/* et comme l'itérateur lastValid contient désormais
*... un élément invalide, on le fait passer
* à l'élément suivant
*/
++lastValid;
/* "y a plus qu'à" déterminer si target doit
* pouvoir passer son temps
*/
}
}
void fish_eat_fish(Aquarium & aquarium, iterator active, iterator & target,
reverse_iterator & last_valid, std::vector<id> & fishs, std::vector<id> & seaweeds)
{
eat_fish(aquarium, active, target, last_valid);
/*l'iterateur target contient l'ancien last_valid
*on verfie si il faut l'update...
*/
if (need_update(active, target))
{
/*...et on l'update
*/
update_fish(aquarium, target, last_valid, fishs, seaweeds);
}
}
void fish_spend_time(Aquarium & aquarium, std::vector<id> & fishs, std::vector<id> & seaweeds)
{
reverse_iterator last_valid = fishs.rbegin();
update_fishs(aquarium, fishs.begin(), last_valid, fishs, seaweeds);
auto sizeToRem = std::distance(fishs.rbegin(), last_valid);
fishs.resize(fishs.size() - sizeToRem);
}
Ca reprend fondamentalement ta manière de faire, qu'en penses-tu ?
Encore merci pour tous, le code a beaucoup evoluer avec ton aide
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
GitHub
GitHub
GitHub
GitHub
GitHub
GitHub
GitHub
GitHub