Discussion :

[befalimpertinent]

Je viens d'écrire un algorithme qui utilise notamment un vector pour effectuer un marquage d'éléments dans une boucle.
Une première version de cet algo est la suivante :

Code :

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

1
2
3
4
5
6
7
8
 
int i;
for(i=0;i<MAX;i++)
{
  vector<int> marked(nb_elems,-1);
  /*.. lot of thing*/
  /*.. lot of thing*/
}

Comme je n'utilise le vector que dans la boucle, je l'ai déclaré à l'intérieur en suivant la règle qui veut qu'on réduise la portée de l'existence des variables au maximum.

Tout marche correctement mais en vue d'une optimisation j'aimerai savoir si la version suivante n'est pas plus rapide et/ou moins gourmande en terme de mémoire.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
{
  vector<int> marked(nb_elems,-1);
  int i;
  for(i=0;i<MAX;i++)
  {
    marked.resize(nb_elems,-1);//nb_elems peut varié
    /*.. lot of thing*/
    /*.. lot of thing*/
  }
}//fin de portée du vector

Contrairement au code précédent, je n'alloue qu'une seule fois marked au début. Puis éventuellement sur un resize si la taille à changé. Est-ce correct ?

Qu'en pensez vous

[yan]

Contrairement au code précédent, je n'alloue qu'une seule fois marked au début. Puis éventuellement sur un resize si la taille à changé. Est-ce correct ?
Qu'en pensez vous

Oui c'est presque la meilleur façon
Le top serait de savoir la taile max qu'aura ton vector et de reserver cette taille des le debut.
Sinon, en gros, le resize va realloué que si il y as besoin. C'est a dire quand la taille va être supérieur que la mémoire qu'il possède. Ainsi ce code ne devrait pas faire de réallocation

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
{
  vector<int> marked(nb_max_elems,-1);
  int i;
  for(i=0;i<MAX;i++)
  {
    marked.resize(nb_elems,-1);//nb_elems peut varié
    /*.. lot of thing*/
    /*.. lot of thing*/
  }
}

[koala01]

Salut,

En plus, la réallocation d'un vector se fait, sauf erreur, en O=1, et donc, tant que le redimentionnement ne se fait pas de manière inutile, tu ne pourra sans doute pas trouver plus rapide

[Pacorabanix]

La fonction reserve ne sert pas à ça au fait ? A éviter que la réalocation devienne lourde en recopiant le vecteur complètement ailleurs a cause d'un manque de place contigüe ?

[JolyLoic]

En plus, la réallocation d'un vector se fait, sauf erreur, en O=1

Elle ne peut se faire en O(1) que si on diminue la taille. Toute augmentation est a priori en O(1). C'est quand on fait n push_back que l'on est sur chacun en O(1) amorti (certains sont en O(1), d'autres en O(n), mais ces derniers sont suffisamment peu nombreux pour qu'en moyenne, on reste en O(1)).

[JolyLoic]

La fonction reserve ne sert pas à ça au fait ?

Tout à fait. Elle réserve l'espace mémoire, mais contrairement à resize, elle ne construit pas les éléments du tableau, ce qui est plus rapide.

[befalimpertinent]

Merci pour toutes vos précisions .

Le top serait de savoir la taile max qu'aura ton vector et de reserver cette taille des le debut.

J'avais envisager cette solution mais malheureusement je n'ai aucune possibilité de connaitre cette taille max avant la boucle for.
A vrai dire je risque de faire des resize de quelques elements à chaque tour de boucle.
Cela me permet d'accéder à mes éléments déjà construit avec l'operator[] (en plus comme les indices correspondent avec les indices d'autres tableaux c'est tout benef ) et de ne pas faire de push_back.

[yan]

Merci pour toutes vos précisions .


J'avais envisager cette solution mais malheureusement je n'ai aucune possibilité de connaitre cette taille max avant la boucle for.
A vrai dire je risque de faire des resize de quelques elements à chaque tour de boucle.
Cela me permet d'accéder à mes éléments déjà construit avec l'operator[] (en plus comme les indices correspondent avec les indices d'autres tableaux c'est tout benef ) et de ne pas faire de push_back.

Tu peut approximé par 2 fois la première taille voir 3.
ET tu fait un reserve.
Mais il me semble que vector fait un truc comme ca. Quand tu fait un push back, et qu'il n'y as plus de place, il agrandi la zone memoire par 2(ou autre facteur).