Discussion :

[Olistan]

Bonjour,
Je souhaiterais avoir votre avis sur le meilleur choix du container et de l'algorithme du bout de code suivant.

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
 
typedef std::vector< size_t >  col;
typedef std::vector< col >  table;
 
void f( size_t i, size_t j )
{
  col& c1 = table[ i ];
  col& c2 = table[ j ];
  if( find( c1.begin(), c1.end(), j ) == c1.end() )
  {
      // Sorted insertion.
      c1.insert( lower_bound( c1.begin(), c1.end(), j ), j );
      c2.insert( lower_bound( c2.begin(), c2.end(), i ), i );
  }
}

Vu que les éléments des colonnes sont triés dans le container, utiliser un vecteur n'est certainement pas l'idéal. De plus, faire un find puis un lower bound peut certainement être réduit en une seule opération. Le coût le plus important est lors de la construction de la table.

Un tout grand merci pour vos conseils !

[Olistan]

J'ai utilisé un unordered_set à la place. Je pense que c'est déjà bien mieux (recherche avec table de haschage ?). De plus, j'évite le recours à un algorithme

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
 
typedef boost::unordered_set< size_t > col;
typedef std::vector< connection >           table;
 
  void f( size_t i, size_t j )
  {
    col& c1 = table[ i ];
    col& c2 = table[ j ];
 
    if( c1.find( j ) == c1.end() )
    {
      c1.insert( j );
      c2.insert( i );
    }
  }

Qu'en pensez-vous ?

[yan]

Salut,
faudrais plus de détail sur ce que tu fais aprés avec tes contenaire
pour te repondre.

[reptils]

http://cpp.developpez.com/faq/cpp/?p...hoix_conteneur

[Olistan]

Merci reptil pour le lien (que je connaissais déjà et je l'ai même collé sur mon bureau). Par contre il ne reprend pas les containers de boost / TR1. Après examen du diagramme ci-dessus, je partais donc vers un 'set' standard avant de découvrir la 'boost::unordered_set' qui apparement convient mieux pour les find mais j'ai pas vraiment compris les différences (dichotromie pour le set et table de hachage par défaut dans l'autre) ?

@Mongaulois: C'est vrai que j'ai été assez vague. En fait, par la suite, je ne fais que parcourir les colonnes du graphe. C'est pourquoi je pense que la construction est la partie la plus coûteuse.

[yan]

@Mongaulois: C'est vrai que j'ai été assez vague. En fait, par la suite, je ne fais que parcourir les colonnes du graphe. C'est pourquoi je pense que la construction est la partie la plus coûteuse.

Si aprés construction le contenue ne change pas(voir peu) alors utilise un vector. C'est le plus adapté.
Si il y as des ajout/retraire regulier et de manière trié, utilise un set.

Pour ta partie construction, tu peut utiliser le set, puis convertir en vector par la suite

[Olistan]

Intéressant !

Mais comment se fait-il que parcourir un vector plutôt qu'un set est plus adapté ?

Sinon, c'est la première fois que j'entend parler de conversion de set en vector ! Comment s'y prend-on ? On va quand même pas faire un copy ? Chacune des colonnes du graphe peut contenir plusieur centaines voir milliers d'éléments (d'où l'intérêt du find sur set plutôt que sur vector).

Et enfin pour le set, y a-t-il un intérêt à utiliser un boost::unordered_set ?

Merci !

[yan]

Intéressant !

Mais comment se fait-il que parcourir un vector plutôt qu'un set est plus adapté ?

Parce que les éléments son contigüe. Donc les accés successif sont sensé être plus rapide

Sinon, c'est la première fois que j'entend parler de conversion de set en vector ! Comment s'y prend-on ? On va quand même pas faire un copy ?

Ben oui

Chacune des colonnes du graphe peut contenir plusieur centaines voir milliers d'éléments (d'où l'intérêt du find sur set plutôt que sur vector).

Et enfin pour le set, y a-t-il un intérêt à utiliser un boost::unordered_set ?

Merci !

...
La je ne sais pas trop.
Peut tu expliqué brièvement tes structure et comment tu t'en sert?

[yan]

Au faite, comme c'est un graph, boost fournie une api pour ca :
http://www.boost.org/libs/graph/doc/..._contents.html

[Olistan]

Au faite, comme c'est un graph, boost fournie une api pour ca :
http://www.boost.org/libs/graph/doc/..._contents.html

Merci ! Bon, il ne me reste plus qu'à m'accrocher pour découvrir cette lib !