Discussion :

[Legro]

Bonjour
J'ai un problème de taile de tableau, mais les réponses plus haut ne m'aident pas.
Je cherche à déclarer un tableau 2 dimensions de 50000*50000 mais ça ne marche pas.
La limite semble se trouver un peu après 32000*32000.
Au départ c'était la mémoire qui faisait défaut, mais maintenat je me suis mis sur un ordinateur
avec 16GB de RAM, et en plus j'ai rempli mon tableau de tout petits trucs (un ou deux bits
par case) en faisant :

Code :

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

1
2
3
4
5
struct Truc { 
unsigned un : 1 ;
unsigned deux :1;
};
Truc truc [50000][50000];

Avec codeblooks ça compile et ça plante.
Avec visual studio ça fait une erreur de compilation en précisant qu'un tableau ne doit pas dépasser
une certaine taille (en hexa, avec tout plein de f)
Si quelqu'un sait me dire si on peut contourner ce problème... Merci

[ternel]

taille de truc = 2 * taille de unsigned = 2 * 64bits = 16 octets.
16 * 50 000 * 50 000 = 16 * 25 * 100 000 000 = 4 * 10 000 000 000 soit 40 giga.
Plus drole, cette taille est prise dans la pile, qui est généralement beaucoup plus petite.

As-tu besoin de tous ces 2,5 milliards d'éléments?

Regarde du coté des matrices creuses.
Sinon, un std::vector que tu encapsules dans une classe de "double tableau", avec value_type const& operator() (size_type i, size_type j) const { return inner[i + j * row_size]; }.

[dalfab]

Bonjour,

La taille ici est plutôt 50000*50000*sizeof(unsigned)
On peut la diviser par 8 en écrivant

Code :

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

1
2
3
4
struct Truc { 
 unsigned char un : 1 ;
 unsigned char deux :1;
 };

La demande devient 50000*50000*sizeof(char)=2.3G

[prgasp77]

As-tu besoin de tous ces 2,5 milliards d'éléments?

Regarde du coté des matrices creuses.
Sinon, un std::vector que tu encapsules dans une classe de "double tableau", avec value_type const& operator() (size_type i, size_type j) const { return inner[i + j * row_size]; }.

Très bon conseil . Pour aller plus loin, je suggèrerais à OP d'encapsuler une std::map<std::pair<size_type, size_type>, value_type> afin d'avoir une vrai matrice éparse. Voici l'exemple minimal que vous pourrez enrichir selon vos besoins :

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
#include <map>
 
template<class T>
class ParseMatrix
{
public:
    using size_type      = std::size_t;
    using value_type     = T;
    using container_type = std::map<std::pair<size_type, size_type>, value_type>;
private:
    container_type _data;
public:
    // EDIT : version const de l'opérateur() supprimé, voir dans les messages suivant
    value_type& operator()(size_type line, size_type col)
    {
        return _data[{line, col}];
    }
};

Et une petite démo live sur coliru.

[ternel]

Sauf que dans ton implémentation, la fonction const créé des 0 dans la map. Il vaut mieux avoir un 0 à coté, et le retourner.

[prgasp77]

C'est une amélioration possible, comme tant d'autres.

EDIT : ce qui précède est faux. Voir mon message suivant.

[prgasp77]

Sauf que dans ton implémentation, la fonction const créé des 0 dans la map. Il vaut mieux avoir un 0 à coté, et le retourner.

J'aimerais revenir là dessus. Vous avez en réalité parfaitement raison, et ma première approche ("c'est une optimisation possible") est complètement erronée. En effet, _data.operator[] est non-const et ne devrait pas être invoqué dans une fonction const. Une implémentation correcte ne définiraient pas de version constante de l'opérateur d'accès, mais définirait une fonction find à l'instar des conteneurs de la bibliothèque standard.


***

Ce qui suit est complètement théorique, si vous n'êtes pas intéressé par les méandres du standard ISO C++, passez votre chemin. Notez: lorsque j'utilise le vocabulaire du standard, je l'utilise en anglais car je ne connais pas sa traduction. Suggestions bienvenues.

La définition suivante :

Code :

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

1
2
3
4
    value_type const& operator()(size_type line, size_type col) const
    {
        return _data[{line, col}];
    }

rendrait le programme ill-formed si cette fonction était odr-used. En effet, _data.operator[] est non-const (comme nous l'avons vu ci-dessus). Pourtant, ce code compile parfaitement avec la dernière version de GCC ... pourquoi ?

Il semblerait que cela soit une conséquence des points suivants :

[temp.inst]/2

The implicit instantiation of a class template specialization causes the implicit instantiation of the declarations, but not of the definitions [...] of the class member functions [...].

et

[temp.res]/1

Knowing which names are type names allows the syntax of every template to be checked. The program is ill-formed, no diagnostic required, if:
- no valid specialization can be generated for a template [...] and the template is not instantiated, or
- [...]

Du fait que ParseMatrix::operator()(size_type line, size_type col) const n'est jamais appelée dans le programme exemple, [temp.inst]/2 assure seulement l'implicit instantiation de sa déclaration (qui est valide) mais pas de sa définition (qui, elle, est invalide) lors de l'explicit instantiation de ParseMatrix<std::string>. En revanche, si cette fonction était appelée, le programme serait effectivement ill-formed mais sans obligation de diagnostique.

Ce qui est amusant, c'est que si le type de ParseMatrix::_data n'était pas dépendant de l'argument template de ParseMatrix, tous les compilateurs ne réagirraient pas de la même manière. Tenez, prenez le programme suivant simplifié :

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
// ill-formed program (as expected)
// build with: g++ -std=c++17 -Wall -Wextra -Werror -pedantic
struct Data { void f() {} };
 
template<class T> struct Wrapper
{
    Data _data;
    void f() const { _data.f(); } // to err or not to err?
};
 
int main()
{
    Wrapper<void> w;
    (void) w;
}

La ligne marquée // to err or not to err? génère une erreur de compilation avec certains compilateurs (implementations) et pas avec d'autre. En effet [temp.inst]/2 "no diagnostic required". Et ce n'est pas un bug :

• gcc : ERREUR : https://godbolt.org/g/rw7Ufb
• clang : OK : https://godbolt.org/g/9HkF3a
• icc : OK https://godbolt.org/g/rfjdi4
• msvc : OK : https://godbolt.org/g/5tChCL

[Legro]

Merci de votre aide à tous.
Pour ce qui est de la taille en mémoire j'ai quand même l'impression qu'avec mon code ça ne devrait pas prendre plus que (50000*50000*2)/8
Donc 2.5 G.
Et en fait n'ayant pas besoin de tous les élément mais que de la moitié, mais qu'ils soient tout de même dans une matrice de largeur et hauteur
de 50000, j'avais codé

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
 
struct Truc 
{unsigned un :1;
unsigned deux :2;
};
int main ()
{
int taille =50000;
Truc ** truc = new Truc* [taille];
for (int i=0;i<taille;i++)
truc [i] = new Truc [taille-i];
 
// et tous les delete qui s'en suivent évidemment
 
return 0;
}

Et malgré tout ça plantait, alors que c'était dans le tas, et que je dispose de 16 G de RAM et que tout cela ne devrait pas prendre
plus de 1 Giga et quelques...
En tout cas encore une fois merci de vos réponses.

[koala01]

Salut,

La définition suivante :

Code :

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

1
2
3
4
    value_type const& operator()(size_type line, size_type col) const
    {
        return _data[{line, col}];
    }

rendrait le programme ill-formed si cette fonction était odr-used. En effet, _data.operator[] est non-const (comme nous l'avons vu ci-dessus).

Ca, tu peux le contourner assez facilement, grace au const_cast.

Car, après tout, c'est une fonctionnalité qui existe et, même s'il ne faut pas l'utiliser avec énormément de précautions, elle peut régulièrement nous sortir de l'embarras

C'est le cas ici, car, a priori, tu auras une version constante et une version non constante de ton opérateur (). Tu peux donc, grâce au const_cast, en utiliser la version non constante dans la version constante sous une forme proche de

Code :

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

1
2
3
4
5
6
7
/* permet à l'utilisateur de changer la valeur de l'élément */
value_type & operator()(size_type line, size_type col){
    return data[{line, col}];
}
value_type /* const & */ operator()(size_type line, size_type col) const{
    return const_cast<ParseMatrix &>(*this)[line, col];
}

grâce auquel le programme sera tout à fait bien formé Avec une assertion, si possible, sur l'existence même de l'élément, ce sera parfait

Il n'y a que le détail du type de retour: il serait pas mal d'avoir un trait de politique pour déterminer si la version constante doit renvoyer l'élément par valeur ou par référence constante, en fonction de la taille des données maintenues