IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Langage C++ Discussion :

Matrice de booleen


Sujet :

Langage C++

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre averti
    Profil pro
    Inscrit en
    Janvier 2006
    Messages
    16
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2006
    Messages : 16
    Par défaut Matrice de booleen
    Bonjour,
    J'ai besoin dans mon programme d'une matrice de booleens de taille 256*256*256.

    La taille en mémoire serait donc de 2Mo.

    Or quand je compare la phase d'initialisation de mon programme, j'ai un écart de 33Mo environ lorsque j'ajoute la matrice. (donnée calculée avec le gestionnaire des tâches en tenant compte de la mémoire virtuelle)

    Sans matrice: 5,8Mo + 3,4 dans la MV
    Avec matrice 22,3Mo + 19,6 dans la MV


    Voici comment je crée la matrice:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    bool table[256][256][256];
    J'ai essayé une autre méthode avec les malloc mais ca prend meme quelques Mo de plus.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    bool*** table;
    //Allocation et initialisation du tableau de booleens
    	table = (bool***) malloc(256*sizeof(bool**));
    	for (int i=0; i<256; i++) {
    		table[i] = (bool**) malloc(256*sizeof(bool*));
    		for (int j=0; j<256; j++) {
    			table[i][j] = (bool*) malloc(256*sizeof(bool));
    			for (int k=0; k<256; k++) {
    				table[i][j][k] = 0;
     
    			}
    		}
    	}
    D'autre la création naïve bool table[256][256][256]; prendrait un espace de mémoire contiguë. N'y a t'il pas un risque de bug si la mémoire est trop fragmentée au moment de l'utilisation? (à moins que le système est assez inteligent pour ranger la mémoire si besoin)

    Que faire car c'est quand meme pas top cette utilisation excessive mémoire!

    Merci d'avance pour votre aide

  2. #2
    Invité
    Invité(e)
    Par défaut
    Il faudrait regarder la doc de ton compilateur, mais un booléen c'est en général stocké sur un octet (même si ca n'utilise qu'un bit). Donc un tableau de 256*256*256 booléens, ca fait 2^24 octets, ou 16 Mo (à mon avis, il y a un double compte quand tu ajoutes la MV).

    Si tu alloues cela comme un tableau de tableau de tableau, il faut rajouter la mémoire pour les pointeurs (4 octets par pointeur de 32 bits).

    L'intérêt de travailler à l'octet, c'est que les accès aux booléens seront nettement facilités. Et 16 Mo, sur une machine récente, ce n'est pas énorme.

    Sinon, tu peux soit utiliser un vector<bool>, qui utilise un bit par booléen, soit un tableau de bitset, par exemple des bitset<256>. (mais lit la doc de la STL si tu utilises l'un ou l'autre, c'est plein de pièges...)

    Francois

  3. #3
    Membre averti
    Profil pro
    Inscrit en
    Janvier 2006
    Messages
    16
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2006
    Messages : 16
    Par défaut
    Merci pour l'explication!

    Pour le compilateur j'utilise visual Studio 2005.

    Je vais donc rester sur la méthode simple bool table[256][256][256]; et tanpis pour la perte de mémoire...

    par contre pour le destructeur de l'objet je détruit manuellement la matrice oou c'est automatique?

    Je sais que si elle est créer avec des malloc il faut le faire sur chaque sous tableau, mais dans le cas de cette matrice crée avec bool table[256][256][256]; je détruis explicitement le tableau?

  4. #4
    Inactif  
    Avatar de Mac LAK
    Profil pro
    Inscrit en
    Octobre 2004
    Messages
    3 893
    Détails du profil
    Informations personnelles :
    Âge : 51
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations forums :
    Inscription : Octobre 2004
    Messages : 3 893
    Par défaut
    Si la matrice est déclarée de façon statique, tu n'as pas besoin de la détruire.

    Par contre, c'est hautement inefficace comme méthode pour stocker autant de booléens, ne serait-ce qu'à cause des alignements qui peuvent quadrupler la taille de ton tableau...

    Pour ma part, je serais plutôt parti sur l'utilisation d'un seul bit par booléen, avec une matrice de type unsigned long int table[256][256][8] et quelques bon templates/macros pour gérer ça : tu t'affranchis des optimisations (forcément optionnelles...) de la STL, et tu es certain de l'utilisation de ta mémoire.
    Mac LAK.
    ___________________________________________________
    Ne prenez pas la vie trop au sérieux, de toutes façons, vous n'en sortirez pas vivant.

    Sources et composants Delphi sur mon site, L'antre du Lak.
    Pas de question technique par MP : posez-la dans un nouveau sujet, sur le forum adéquat.

    Rejoignez-nous sur : Serveur de fichiers [NAS] Le Tableau de bord projets Le groupe de travail ICMO

  5. #5
    Membre averti
    Profil pro
    Inscrit en
    Janvier 2006
    Messages
    16
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2006
    Messages : 16
    Par défaut
    ne serait-ce qu'à cause des alignements qui peuvent quadrupler la taille de ton tableau...
    Je ne vois pas de quoi il s'agit?

    Pour ma part, je serais plutôt parti sur l'utilisation d'un seul bit par booléen, avec une matrice de type unsigned long int table[256][256][8] et quelques bon templates/macros pour gérer ça
    dans ce cas pour obtenir le bool correspondant à i on fait (on prend le pb en une dimension pour simplifier)

    + les 3 bits de plus haut poids donnent le numéro de la case du tableau
    ça se code avec:

    + les 5 bits de plus bas poids donnent un nombre entre 0 et 31 qui correspond à la place du bit cherché dans le long int de la case

    Par contre ça m'a l'air plus couteux en opération (à moins que le modulo % soit optimisé en cas de puissance de 2...)

    i%32 donne donc la place du bit entre 0 et 31, on fait un décalage puis on prend le bit de plus faible poids

    Ca donnerait:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    bool valeureTable(int i) { // i entre 0 et 255
    return ( ( table[ i >>5 ] ) >> (i%32) ) % 2;
    }
    Je trouve ca pas très beau (impossible de trouver une fonction donnant directement le nième bit d'un long int.)

    mais n'est ce pas trop couteux en opérations?

    C'est pour un traitement d'image et chaque pixel demande un accès à la matrice256*256*256 (qui correspond à l'espace des couleurs)

    Donc pour traiter un flux vidéo, j'ai pas interet que ca soit trop long.

    Par contre ça pourrait peut être aller un peut plus vite avec la meme méthode sur un char table[256][256][32]
    avec return ( ( table[ i >>3 ] ) >> (i%8) ) % 2;

    (ca dépend si le décalage de bit est moins couteux que le modulo, mais ca revient peut être au même)

    Ou alors coder carrément un type de 256bits avec une fonction pour atteindre le ieme bit, mais il y a peut être un risque que ca soit moins performant?

    J'attends vos commentaires avant de me mettre à recoder mon objet.

    Merci encore!

  6. #6
    Membre Expert
    Avatar de Joel F
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Septembre 2002
    Messages
    918
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Service public

    Informations forums :
    Inscription : Septembre 2002
    Messages : 918
    Par défaut
    Citation Envoyé par Mac LAK Voir le message
    Pour ma part, je serais plutôt parti sur l'utilisation d'un seul bit par booléen, avec une matrice de type unsigned long int table[256][256][8] et quelques bon templates/macros pour gérer ça : tu t'affranchis des optimisations (forcément optionnelles...) de la STL, et tu es certain de l'utilisation de ta mémoire.
    c'est deja ce que fait std::bitset<N> si je ne m'abuse:

    http://codepad.org/I4BplhrE

    sachant que bitset::operator[] fait aussi la tambouille pour extraire le booleen compressé.

  7. #7
    Membre averti
    Profil pro
    Inscrit en
    Janvier 2006
    Messages
    16
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2006
    Messages : 16
    Par défaut
    Ca a l'air super pour ce que je veux faire bitset!

    En plus l'accès semble se faire comme pour un simple tableau
    (table[i][j][k] )

    Je n'aurais donc que la déclaration de table à modifier!

    par contre pour le destructeur, je suppose qu'il faudra faire:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    for (int i=0; i<256; i++) {
            for (int j=0; j<256; j++) {
    			~table[i][j](); 
    		}
    	}

  8. #8
    Inactif  
    Avatar de Mac LAK
    Profil pro
    Inscrit en
    Octobre 2004
    Messages
    3 893
    Détails du profil
    Informations personnelles :
    Âge : 51
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations forums :
    Inscription : Octobre 2004
    Messages : 3 893
    Par défaut
    Citation Envoyé par etienne007 Voir le message
    Je ne vois pas de quoi il s'agit?
    Tu peux, suivant les optimisations, n'avoir qu'un seul octet tous les 32 bits, pour des raisons de performances. C'est pour ça que j'ai mis comme élément "terminal" de ma matrice un entier 32 bits et non pas un octet. Ainsi, peu importe l'alignement, tes données (sur une machine 32 bits) seront contigües et sans "pertes" au niveau des accès à la mémoire (un CPU 32 bits lit toujours des mots de 32 bits, même si tu n'as demandé qu'un octet).

    Citation Envoyé par etienne007 Voir le message
    Je trouve ca pas très beau (impossible de trouver une fonction donnant directement le nième bit d'un long int.)
    Ce n'est pas fait pour être "beau", c'est fait pour être efficace...
    C'est plutôt que tu fonctionnes avec des décalages "purs", opérations qui sont extrêmement rapides. Le but derrière n'est pas d'avoir un joli bit valant 0 ou 1, mais un booléen, quelque chose que l'on peut filer directement à "if" pour faire une opération. Donc, tu vas extraire brutalement le bit, et éventuellement caster directement dans un bool au travers d'une macro.
    Exemple :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    #define GETBIT(Matrix,i,j,k) (bool)(Matrix[(i)][(j)][(k)>>5] & (1<<((k) & 31)))
    Cela renvoie directement un bool, mais on pourrait aussi le laisser renvoyer un entier 32 bits qui vaudra soit zéro, soit "pas zéro".
    Tu vas avoir de même une macro de positionnement de bit fonctionnant de façon similaire :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    #define SETBIT(Matrix,i,j,k,value) if (value) { Matrix[(i)][(j)][(k)>>5] |= (1<<((k) & 31))) } else { Matrix[(i)][(j)][(k)>>5] &= ~(1<<((k) & 31))) }
    Bon, là, c'est fait avec des macros, mais tu peux le faire avec des templates si ça te "parle" plus. Cela ne changera pas grand-chose au final, tant que le code est inliné au maximum et qu'il n'utilise que des opérations "simples" (indirections, décalages, AND/OR/NOT binaires).

    Citation Envoyé par etienne007 Voir le message
    C'est pour un traitement d'image et chaque pixel demande un accès à la matrice256*256*256 (qui correspond à l'espace des couleurs)
    Hmmm ? Est-ce pour compter le nombre de couleurs ? Si oui, il y a beaucoup plus efficace que cette méthode...

    Citation Envoyé par etienne007 Voir le message
    (ca dépend si le décalage de bit est moins couteux que le modulo, mais ca revient peut être au même)
    Avec les optimisations activées, cela revient NORMALEMENT au même si la valeur de modulo est constante. Ce n'est pas forcément vrai si c'est en debug ou si c'est variable. Par exemple, "i % 32" est optimisé avec un décalage, mais "i % value" (value étant une variable contenant 32) ne le sera pas.

    [3DArchi : sur la digression relative aux perfs de la STL, cf cette discussion]
    Mac LAK.
    ___________________________________________________
    Ne prenez pas la vie trop au sérieux, de toutes façons, vous n'en sortirez pas vivant.

    Sources et composants Delphi sur mon site, L'antre du Lak.
    Pas de question technique par MP : posez-la dans un nouveau sujet, sur le forum adéquat.

    Rejoignez-nous sur : Serveur de fichiers [NAS] Le Tableau de bord projets Le groupe de travail ICMO

Discussions similaires

  1. Réponses: 11
    Dernier message: 17/03/2010, 17h42
  2. Matrice de filtrage ?
    Par gimlithedwarf dans le forum Traitement d'images
    Réponses: 2
    Dernier message: 24/08/2002, 09h44
  3. Gestion de matrice
    Par bzd dans le forum C
    Réponses: 4
    Dernier message: 12/08/2002, 18h19
  4. Comment définir le type matrice ?
    Par charly dans le forum Langage
    Réponses: 7
    Dernier message: 15/06/2002, 21h01

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo