Statique ou dynamique ?

a marqué ce sujet comme résolu.
Auteur du sujet

Bonjour,

Je suis en train de réaliser un petit Morpion à titre d'exercice. Je représente la grille par un tableau de char et une question me taraude. Dans la mesure où la grille est de taille fixe, est-ce qu'il vaut mieux que j'utilise un char[9] ou un vector<char> ?

Cette réponse a aidé l’auteur du sujet

Un std::array<State, 9>

char = sémantique de caractère, il est mieux de créer un enum (ou une classe, a voir selon le design) pour avoir une sémantique explicite (empty, square, cross)

vector = taille peut changer dynamiquement au runtime, pas besoin dans ton cas

tableau C = syntaxe plus lourde pour utiliser avec les algos standards (et tes propres algos, puisque tu vas respecter la syntaxe des algos standards pour tes propres algos, naturellement…)

Pour poser des questions ou simplement discuter informatique, vous pouvez rejoindre le discord NaN.

+4 -0

Je ne suis pas sur que "player" soit le bon terme. Tes joueurs ne sont pas sur le plateau de jeu a priori.

A priori, pas besoin de pointeur (et surtout pas de pointeur nu)

Pour poser des questions ou simplement discuter informatique, vous pouvez rejoindre le discord NaN.

+0 -0

En soi, ce n'est pas "mauvais" comme choix, mais quel intérêt d'avoir un pointeur vers player pour aller chercher le caractère a afficher plutôt que de mettre directement le caractère dans la grille ?

Pour poser des questions ou simplement discuter informatique, vous pouvez rejoindre le discord NaN.

+0 -0

A titre d'information, il peut être intéressant ici d'utiliser un std::array<3, std::array<3, Whatever>>. Cela permet de manipuler effectivement une grille grid[y][x].

A ne surtout pas faire dans le cas d'un std::vector (!).

germinolegrand

La raison m'intéresse. Un problème de performance ? Je sais qu'on conseille un seul std::vector de taille N * M qu'un std::vector contenant N std::vector de taille M dans le cas où on représente une matrice par exemple.

+0 -0

La raison m'intéresse. Un problème de performance ?

Exactement ! Aussi bien au niveau mémoire qu'en temps d'accès.

Un vecteur de taille n*m requière n + 1 allocation, donc hoverhead et dispersion de la mémoire plus importante. De plus, les données ne sont pas alignées et il faut 2 déréférencements pour accéder à un élément.

Si on veut utiliser une matrice alignée comme un tableau 2d, il est préférable de retourner une vue (voir std::array_view).

+0 -0

La raison m'intéresse. Un problème de performance ? Je sais qu'on conseille un seul std::vector de taille N * M qu'un std::vector contenant N std::vector de taille M dans le cas où on représente une matrice par exemple.

informaticienzero

Réfléchis à la manière dont est structurée un vecteur en mémoire et ce qui se passe quand on change la taille et qu'elle dépasse alors la capacité du vecteur.

Édité par KFC

« Kommunist Fried Chicken » | Macroeconomics: Three decades of intellectual regress

+0 -0

La raison m'intéresse. Un problème de performance ? Je sais qu'on conseille un seul std::vector de taille N * M qu'un std::vector contenant N std::vector de taille M dans le cas où on représente une matrice par exemple.

informaticienzero

Plusieurs problématiques en réalité.

La première c'est la place que ça prend en mémoire : un vector de vector de T de taille N*M, c'est tout d'abord sizeof(vector) + N*sizeof(vector) + N*M*sizeof(T) octets, tandis qu'un vector de T de taille N*M, c'est seulement sizeof(vector) + N*M*sizeof(T).

La deuxième c'est la discontinuité du stockage des données : en effet, autant un vector simple s'assure que ses données sont stockées de façon contigüe en mémoire, ce qui assure les meilleures vitesses d'accès puisque si j'accède à une case X, la case X+L est dans une grande majorité des cas dans le cache ; tandis que dans le cas d'un vector de vector, on se prend de façon presque inévitable un cache miss à chaque fin de ligne.

La troisième, eh bien le nombre d'allocations nécessaires sur le tas (heap), ce qui est habituellement une opération lente (sauf si on s'amuse à gérer un pool de mémoire et des allocateurs personnalisés sur les vector), à savoir N+1 allocations pour un vector de vector, contre seulement 1 allocation pour un vector simple.

La quatrième, et cette fois-ci elle est en défaveur du vector simple, c'est la simplicité d'utilisation. Il est mille fois plus agréable de travailler avec des vector de vector, puisqu'on manipule effectivement un grid[y][x], tandis qu'il faut mettre des formules de partout avec un vector simple : grid[y*grid[0].size() + x], ce qui est un facteur d'erreurs important. Une solution peut être une classe pour encapsuler cela, et comme le dit jo_link_noir std::array_view semble être la solution standard qui se profile à l'horizon. Il faudra toutefois attendre la prochaine version du standard (C++17 si tout va bien) pour en disposer.

Nouveauté C++17 : les décompositions | Nouveautés du C++14 | FYS : une bibliothèque C++ dans le domaine public

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte