Discussion :

[dazzle]

Bonjour tout le monde,

Je développe un programme en C++ pour modéliser un réseau métabolique (comprendre réseau de réactions chimiques) par un graphe : un ensemble de noeuds liés par des arêtes. Les noeuds correspondent aux composés et les arêtes aux réactions impliquant ces composés. J'ai donc les classes correspondantes : Graph, Node (noeud) et Edge (arête). Graph connait la liste des noeuds et des arêtes. Enfin, chaque noeud est dans un état parmi 4 états possibles : gris, blanc, vert ou rouge.

Un graphe aura dans de nombreux cas plusieurs milliers de noeuds, qui doivent être traversés par l'algorithme de recherche qui tient compte de la couleur des noeuds. Dans l'idée d'optimiser l'utilisation de la mémoire et la vitesse d'exécution, je me demande comment implémenter au mieux la gestion de la couleur des noeuds.

Quel type de variable utiliser pour la couleur (est-ce qu'on peut faire mieux qu'un int) ? Accessoirement, est-il préférable qu'elle soit gérée par le noeud concerné (classe Node) ou par la classe Graph qui se chargerait de mapper le numéro du noeud à sa couleur ?

EDIT : On doit pouvoir différencier rapidement les noeuds verts/rouges des noeuds gris/blancs.

[gangsoleil]

Bonjour,

Dans la mesure où tu n'as que 4 valeurs possibles, pourquoi ne pas utiliser un (unsigned) char ? Ca prend un octet, ce qui sera toujours moins que 4 (ou 8) pour les entiers.

[foetus]

En complément de gangsoleil, un truc comme cela

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
typedef enum e_COLOR_ID {
    COLOR_GREEN = 1,
    COLOR_GREY  = 2,
    COLOR_RED   = 4,
    COLOR_WHITE = 8
} COLOR_ID;
 
 
#define IS_GREEN(C) \
    (((C  & COLOR_GREEN) == COLOR_GREEN) && ((C & COLOR_GREY) == 0) && ((C  & COLOR_RED) == 0) && ((C  & COLOR_WHITE) == 0))
 
 
#define IS_GREY(C) \
    (((C  & COLOR_GREEN) == 0) && ((C & COLOR_GREY) == COLOR_GREY) && ((C  & COLOR_RED) == 0) && ((C  & COLOR_WHITE) == 0))
 
 
#define IS_RED(C) \
    (((C  & COLOR_GREEN) == 0) && ((C & COLOR_GREY) == 0) && ((C  & COLOR_RED) == COLOR_RED) && ((C  & COLOR_WHITE) == 0))
 
 
#define IS_WHITE(C) \
    (((C  & COLOR_GREEN) == 0) && ((C & COLOR_GREY) == 0) && ((C  & COLOR_RED) == 0) && ((C  & COLOR_WHITE) == COLOR_WHITE))

[ternel]

Avec le C++11, tu peux même combiner les deux approches (et sans macro) ainsi:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
enum  COLOR_ID : char{
    COLOR_GREEN = 1,
    COLOR_GREY  = 2,
    COLOR_RED   = 4,
    COLOR_WHITE = 8
};
 
inline bool IS_GREEN(COLOR_ID c) {return c==COLOR_GREEN;}
inline bool IS_GREY(COLOR_ID c) {return c==COLOR_GREY;}
inline bool IS_RED(COLOR_ID c) {return c==COLOR_RED;}
inline bool IS_WHITE(COLOR_ID c) {return c==COLOR_WHITE;}

Voire même mieux encore, avec les class enum:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
enum class COLOR_ID : char {GREEN, GREY, RED, WHITE};
 
inline bool IS_GREEN(COLOR_ID c) {return c==COLOR_ID::GREEN;}
inline bool IS_GREY(COLOR_ID c) {return c==COLOR_ID::GREY;}
inline bool IS_RED(COLOR_ID c) {return c==COLOR_ID::RED;}
inline bool IS_WHITE(COLOR_ID c) {return c==COLOR_ID::WHITE;}

Pour plus de détails sur les class enum, dites aussi scoped enum, regardes sur cppreference.com.

Par ailleurs, si ton noeud n'a aucune autre fonctionnalité (meme technique) que d'avoir une couleur, tu peux envisager de ne pas avoir de classe.
A voir comment ton code s'organise.

[dazzle]

Merci pour vos réponses complémentaires, ça correspond très bien à ce que je cherche en terme d'optimisation de l'espace mémoire (en plus ça a l'avantage de clarifier la notion de couleur dans le code). Par contre, quelqu'un pourrait-il me préciser ce qu'il en est de la rapidité d'accès à ce type de données ? Toujours par rapport à l'utilisation d'un int tout bête par exemple

Par ailleurs, si ton noeud n'a aucune autre fonctionnalité (meme technique) que d'avoir une couleur, tu peux envisager de ne pas avoir de classe.
A voir comment ton code s'organise.

Oui, mais dans cette situation les noeuds possèdent d'autres attributs et méthodes qui justifient la définition d'une classe

[ternel]

Une énum est normalement aussi rapide que le type primitif sous-jacent. Ca n'apporte pour ainsi dire que de robustesse à la compilation.
Mieux, le compilateur est peut-être capable de faire des optimisations spécifiques (surtout avec les scoped enums)

Un type primitif est optimal (en rapidité) s'il fait la meme taille que le mot machine, dont la théorie voudrait que ce soit la taille de int.
En pratique, tu ne devrais pas voir d'écart avec un (un)signed char.

Question optimisation mémoire, il faut étudier le layout mémoire des classes, et le plus simple pour cela, c'est de faire attention à la taille de chaque membre, et à l'ordre correspondant.

Supposons les structures suivantes:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
struct Truc {
char color;
int id;
char a, b, c;
};
 
struct Bidule {
char color, a, b, c;
int id;
};

Sur une machine telle que sizeof(int) == 4, Truc a des chances de faire un sizeof de 12, tandis que Bidule peut n'en faire que 8.
La raison, c'est que, d'une part, une variable ne peut avoir pour adresse qu'un multiple de sa propre taille, et d'autre part que l'ordre en mémoire des membres d'une class/struct est celui déclaré. Dans Truc, le champ [c]id ne peut être aligné que sur un multiple de 4, laissant un trou entre color et lui-même.


En règle général, il y a un compromis à faire sur ces deux aspects d'optimisations (temps et espace).
Dans tous les cas, on n'optimise qu'après mesure, et on ne mesure que dans les conditions réelles, donc quand le programme est compilé avec les options d'optimisations qui conviennent.
Pour gcc, par exemple, il s'agit probablement d'utiliser -O3 (ou -O2).

[gangsoleil]

Par contre, quelqu'un pourrait-il me préciser ce qu'il en est de la rapidité d'accès à ce type de données ? Toujours par rapport à l'utilisation d'un int tout bête par exemple

Les optimisations de base des compilateurs sont souvent (beaucoup) plus performantes que ce qu'on croit, donc à ta place, je commencerai par l'implémenter avec une solution proposée ici, et ensuite seulement tu verras si tu as des problèmes de perfs. Et si oui, alors seulement tu utiliseras un profiler qui t'indiquera dans quelles classes/fonctions tu passes le plus de temps, et donc où faire tes optimisations.