Nous abordons cette dernière semaine des façons plus efficaces de faire les simulations.
On cherche ici à améliorer la gestion des rencontres entre particules, et plus exactement le calcul permettant de déterminer si deux particules interagissent (cf exercice P9 et plus particulièrement la question P9.2).
Plutôt que de calculer l'interaction de chacune des autres particules avec une particule donnée même si cette interaction est nulle car les particules sont trop éloignées, on propose ici d'échantillonner l'espace par un certain nombre de « cases » (portions de l'espace représentant le système), chaque particule sachant à tout moment dans quelle case elle se trouve (nous allons voir comment) et chaque case connaissant la liste des particules qu'elle contient.
Déterminer quelle particule est en interaction avec une particule donnée P devient alors simple : il suffit d'accéder à la case de P et de regarder quelles particules cette case et ses voisines directes contiennent.
[Question P12.1] Avant de préciser les détails
d'implémentation, quelle est la complexité temporelle pire cas de
cette solution en fonction du nombre de particules ?
[On supposera ici que
les particules sont « assez bien réparties » dans les cases. On supposera de plus que
la taille d'une case est petite par rapport à la taille du système. Ainsi
on peut faire l'hypothèse que le nombre de particules par
case est négligeable (O(1)) devant le nombre total de particules
(c.-à-d. toutes les particules ne se retrouvent pas en même temps dans la même case).
Quel(s)
inconvénient(s) présente cependant cette solution ?
Répondez à
cette question dans votre fichier REPONSES.
Concrètement, je vous propose donc de choisir un « pas d'espace » tel que deux particules situées à plus d'une case d'intervalle n'interagissent pas, c.-à-d. que ce « pas d'espace » est supérieur à 2σ (voir section 4.1, page 3 du complément mathématique du projet).
Nous avons donc besoin de partitionner le système de sorte que :
Il existe plusieurs façons d'implémenter ceci et vous êtes, bien sûr, libres de choisir la vôtre. Je ne fais que vous en proposer une ici.
Pour les contenus des cases, le plus simple est d'utiliser un tableau dynamique de pointeurs sur des Particules, ou alors si vous avez « numéroté » vos particules d'une manière ou d'une autre, un tableau d'entiers.
À chaque déplacement d'une particule, on le supprime de sa case et on l'ajoute dans sa nouvelle case.
Pour accéder à une case depuis une particule, le plus simple est de choisir une convention de représentation simple qui permette de directement accéder à la case, par exemple bien choisir les unités des positions de sorte que la partie entière des coordonnées donne directement accès à la case correspondante, les différentes cases étant alors gardées en mémoire sous forme d'un tableau tridimensionnel.
On peut bien sûr prendre d'autres conventions entre les unités
de position et les cases (comme prendre la partie entière des positions
divisé par ce qui va bien), voire chercher des structures de données plus
compliquées et utiliser des pointeurs (de la particule vers sa case)...
...mais dans ce sens nous proposons justement une autre solution dans l'exercice suivant.
Pour implémenter le modèle proposé ici, vous pouvez soit créer de nouvelles classes, soit [plus difficile : ceci est vraiment pour celles et ceux qui sont à un haut niveau ! J'insiste qu'il serait catastrophique pour des étudiant(e)s ne se sentant pas à l'aise d'essayer ici de grappiller inutilement des points !] utiliser le polymorphisme pour avoir les deux possibilités (exerciceP9 et celui-ci) dans le même exécutable.
Indiquez nous la solution choisie (explicitez un peu votre réponse) en répondant à la question suivante dans votre fichier REPONSES :
[Question P12.2] Comment et où avez-vous implémenté cette nouvelle façon de calculer les collisions ?
ATTENTION ! Nous parlons bien ici d'échantillonner l'espace pour déterminer si il y a interaction entre deux particules, non pas pour représenter les positions utiles pour calculer les déplacements, qui elles restent en double (en clair les déplacements restent bien plus fins que la taille des cases).
Sauvegardez bien cette étape du projet (appelez la par exemple exerciceP12.cc). Elle devra faire partie du rendu final.
Pour aller encore plus loin sur le chemin de l'idée précédente, on propose ici d'avoir une structure de données qui à chaque position associe directement la liste des particules s'y trouvant.
Pour une telle structure de données, je vous propose d'utiliser les tables associatives (map) de la bibliothèque C++ : l'idée est d'associer à la position discrétisée (les trois entiers utilisés pour la solution précédente) la liste des particules se trouvant à cette position.
Il faut donc (si ce n'est pas déjà fait) créer la notion de «triplet d'entiers» (appelons-les ici «triplet») et faire une table associative map<triplet, vector<Particule*> > (ou un vector<size_t> si vous avez « numéroté » vos particules).
Il faudra bien sûr penser à mettre à jour cette structure de données à chaque déplacement de particule (mais cela est assez similaire à ce qui a été fait à l'exercice précédent).
[Question P13.1] Quelle est la complexité temporelle pire
cas de cette solution en fonction du nombre de particules ?
[Cette question est difficile et nécessite la lecture
de la documentation sur les map]
Quel(s) avantage(s) par rapport à la solution précédente ?
Répondez à cette question dans votre
fichier REPONSES.
Remarque pratique importante : les clés d'une table associative (c.-à-d. les « triplets » ici) doivent pouvoir être copiés (c.-à-d. a = b, donc en particulier ne peut pas être un tableau « à la C ») et doivent aussi avoir un operator<().
Ceci constitue donc la dernière partie du projet.
Pour celles et ceux qui en redemandent : il y a sur cette page (projetFin.html) des pistes d'extensions possibles (tout à fait optionnelles).
Pour le rendu de votre projet (au plus tard dimanche 31 mai à 23h59) : voir cette page là (rendu-projet.html).