std::vector : créations répétées, ou assign ?

Version imprimable

20/12/2011, 13h33
oodini

std::vector : créations répétées, ou assign ?

Bonjour,

Je dois faire de manière répétée un traitement qui se sert de diverses matrices, que j'implémente avec des vecteurs de vecteurs. Leurs dimensions ne changent pas, mais je dois réinitialiser les valeurs à chaque fois. Le nombre d'éléments (des ints) dans ces matrices peut aller jusqu'à plusieurs centaines.

Dois-je créer une bonne fois pour toutes ces matrices, et faire de manière répétée des assign(0), ou créer localement les matrices dans un souci de localité/lisibilité ?

Quel est le coût de construction/destruction d'un vecteur de vecteurs de int ?
20/12/2011, 14h50
Davidbrcz

Citation:

Envoyé par oodini

Bonjour,

Je dois faire de manière répétée un traitement qui se sert de diverses matrices, que j'implémente avec des vecteurs de vecteurs. Leurs dimensions ne changent pas, mais je dois réinitialiser les valeurs à chaque fois. Le nombre d'éléments (des ints) dans ces matrices peut aller jusqu'à plusieurs centaines.

Dois-je créer une bonne fois pour toutes ces matrices, et faire de manière répétée des assign(0), ou créer localement les matrices dans un souci de localité/lisibilité ?

Quel est le coût de construction/destruction d'un vecteur de vecteurs de int ?

A la base, des vecteurs des vecteur c'est bof bof. Mais pour le calcul matriciel, c'est carrément pas top. Et plusieurs centaines de int ? C'est rien du tout (à moins que tu ais oublié milliers)

Sinon, pour la performance de tableau multi index refait main : http://www.developpez.net/forums/d10...-3-dimensions/
20/12/2011, 14h51
themadmax

L’implémentation des STLs n'est pas unique.
Slogan de l'Extreme programming: "N'optimiser qu'à la toute fin." et en anglais sa claque mieu: "Leave Optimization till last;"
20/12/2011, 14h59
bretus

Citation:

Envoyé par themadmax

L’implémentation des STLs n'est pas unique.
Slogan de l'Extreme programming: "N'optimiser qu'à la toute fin." et en anglais sa claque mieu: "Leave Optimization till last;"

Exception sur les calcul matriciels : Prendre directement une bibliothèque optimisée. Pour ce cas présent, pourquoi ne pas prendre boost::numeric::ublas?
20/12/2011, 15h09
oodini

Citation:

Envoyé par Davidbrcz

A la base, des vecteurs des vecteur c'est bof bof. Mais pour le calcul matriciel, c'est carrément pas top.

Je n'ai jamais parlé de calculs. C'est un tableau à double entrée, c'est tout.
20/12/2011, 15h31
bretus
Citation:

Envoyé par oodini

Je n'ai jamais parlé de calculs. C'est un tableau à double entrée, c'est tout.

Qui peut le plus, peut le moins ;) Je pense que tu t'embête avec ton vecteur de vecteur pour garder l'accès sous la forme :
Code:

1 2 mat[i][j] = 15;
Si tu encapsules ton stockage et que tu acceptes l'appel en :
Code:

1 2 mat(i,j) = 15;
Tu te laisseras la possibilité de modifier ton stockage sous-jasent...

Salut,

Si c'est, simplement, un tableau à double entrée (sans l'aspect "calcul matriciel" ), je présumes que toutes tes lignes sont composées du même nombre de colonnes :aie:

Dés lors, au lieu de travailler sur un vecteur de vecteur (ce qui est quand meme non seulement difficile, mais surtout assez hasardeux :aie:), je te conseillerais de créer ta classe perso "Vector2D" (ou n'importe quel autre nom qui te semblerait adapté :D) qui utiliserait un (unique) vecteur de (nombre_ligne * nombre_colonne) élément et dont l'opérateur () renverrait l'élément se trouvant à l'index ( colonne* nombre_ligne + ligne), sous une forme proche de (je la rend template pour lui permettre de s'adapter à tous les besoins :D)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
template <typename T>
class Vector2D
{
    public:
        typedef T value_type;
        Vector2D( size_t nbRows,size_t nbLines):nbLines(nbLines),nbRows(nbRows),vector(nbLines*nbRows){}
        value_type const & operator()  ( size_t row, size_t line) const
        {
            assert(line < nbLines);
            assert(row < nbRows);
            return vector[row*nbLines + line];
        }    
        value_type & operator()  ( size_t row, size_t line)
        {
            /* cette manière de faire a surement de quoi surprendre mais elle
             * présente deux avantages : 
             * 
             * - permettre d'avoir quand meme une version constante
             *   et une version non constante de l'opérateur
             * - éviter la duplication de code
             *
             * même si le deuxième avantage peut sembler mineur, le fait est
             * que, dans le cas (peu probable il est vrai :D ) où l'on devrait
             * modifier le comportement de l'opérateur, il ne faudrait le faire
             * qu'à un seul endroit, et donc d'éviter d'avoir un comportement 
             * pour la version constante et un autre pour la version non 
             * constante (ce qui pourrait arriver avec la duplication de code,
             * si on pense à modifier l'un mais pas l'autre :aie: )
             *
             */
            return const_cast<value_type &>(
                static_cast<const Vector2D<value_type>*>(this)->(line, row));
 
        }    
    private:
        size_t nbLines;
        size_t nbRows;
        std::vector<value_type> vector;
};

Si les nombres de lignes et de colonnes sont fixes et définis clairement par avance, on peut très bien décider d'utiliser des tableaux de tailles fixes, hein ;)

l'utilisation en est relativement simple:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int main()
{
    size_t nbLines = 10:
    size_t nbRows = 100;
    Vector2D v( nbLines, nbRows);
    for(size_t row = 0; row < nbRows; row++)
        for(size_t line = 0;line <nbLines; line++)
            v( row, line) =  row * nbLines + line;
 
    for(size_t row = 0; row < nbRows; row++)
    {
        for(size_t line = 0;line <nbLines; line++)
        {
            std::cout <<"v["<<row<<"] ["<<line<<"] = "
                      <<v( row, line)<<std::endl;
        }
        std::cout<<std::endl;
    }
    return 0;
}

21/12/2011, 13h50
oodini

Toutes vos suggestions sont appréciées, mais en répondent pas à ma question : quid du coût de l'allocation, par rapport à une simple réinitialisation des données via assign() dans le cas du vecteur de la STL, ou par une boucle dans les autres cas ?
23/12/2011, 10h29
jblecanard

Citation:

Envoyé par oodini

Toutes vos suggestions sont appréciées, mais en répondent pas à ma question : quid du coût de l'allocation, par rapport à une simple réinitialisation des données via assign() dans le cas du vecteur de la STL, ou par une boucle dans les autres cas ?

C'est assez compliqué, car un vecteur n'occupe pas en mémoire la taille que renvoie size(). L'allocation et la libération de mémoire se fait différemment de manière à ne pas surcharger l'OS avec des allocations récurrentes.

Dans tous les cas, quelles que soit la structure de données que tu choisis, le mieux est de ne pas recréer la matrice. En effet, si tu la recrées, tu devras aussi faire un assign des valeurs pour les initialiser, en plus de l'allocation mémoire ! En gardant à l'esprit que l'allocation de mémoire fait partie des choses les plus coûteuses dans un programme, pour moi la réponse est claire et nette : pas de recréation mais assignation des valeurs à zéro pour la suite du traitement.
27/12/2011, 10h54
3DArchi

Salut,

Il me semble assez difficile de répondre dans l'absolu si une technique sera meilleure qu'une autre dans la mesure où comme le dit jblecanard localement il peut ne pas y avoir de réallocation ou celle-ci peut être à un coût très négligeable s'il ne se passe rien entre la libération et l'allocation (optimisation de l'allocateur, de l'os, etc.)

Ce que je te recommanderais dans un tel cas est de te construire un petit benchmark pour évaluer tes différentes options, surtout si tes outils de génération et tes machines cibles sont assez homogènes. Dans le cas contraire, essayer de faire différents tests sur plusieurs machines. Et si les résultats ne sont pas flagrants, prendre celle qui facilite l'écriture et la maintenance de ton code, une optimisation non évidente pouvant s'avérer pénalisante in fine.

Si tu as un tel problème, est ce que des approches // ne sont pas alors plus pertinentes pour bénéficier d'un bonne montée en charge.
27/12/2011, 14h05
oodini

Ma question ne se faisait pas (encore) dans le cadre d'une optimisation à tout crin, car le logiciel sur lequel je travaille n'en est pas à ce stade.

Je me suis juste posé la question au moment où je codais sur quelle était la meilleure pratique dans ce cas cas de figure. Il est pour l'instant exclu que je fasse des tests pour comparer les deux solutions.
28/12/2011, 10h19
3DArchi

Citation:

Envoyé par oodini

Ma question ne se faisait pas (encore) dans le cadre d'une optimisation à tout crin, car le logiciel sur lequel je travaille n'en est pas à ce stade.

Je me suis juste posé la question au moment où je codais sur quelle était la meilleure pratique dans ce cas cas de figure. Il est pour l'instant exclu que je fasse des tests pour comparer les deux solutions.

Citation:

Envoyé par themadmax

"N'optimiser qu'à la toute fin."

:D