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

SL & STL C++ Discussion :

Optimisation choix container/algorithme


Sujet :

SL & STL C++

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre averti
    Profil pro
    Inscrit en
    Mars 2008
    Messages
    15
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : Mars 2008
    Messages : 15
    Par défaut Optimisation choix container/algorithme
    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 !

  2. #2
    Membre averti
    Profil pro
    Inscrit en
    Mars 2008
    Messages
    15
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : Mars 2008
    Messages : 15
    Par défaut
    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 ?

  3. #3
    yan
    yan est déconnecté
    Rédacteur
    Avatar de yan
    Homme Profil pro
    Ingénieur expert
    Inscrit en
    Mars 2004
    Messages
    10 035
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : Ingénieur expert
    Secteur : High Tech - Multimédia et Internet

    Informations forums :
    Inscription : Mars 2004
    Messages : 10 035
    Par défaut
    Salut,
    faudrais plus de détail sur ce que tu fais aprés avec tes contenaire
    pour te repondre.

  4. #4
    Membre éclairé
    Profil pro
    Inscrit en
    Juillet 2004
    Messages
    410
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juillet 2004
    Messages : 410

  5. #5
    Membre averti
    Profil pro
    Inscrit en
    Mars 2008
    Messages
    15
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : Mars 2008
    Messages : 15
    Par défaut
    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.

  6. #6
    yan
    yan est déconnecté
    Rédacteur
    Avatar de yan
    Homme Profil pro
    Ingénieur expert
    Inscrit en
    Mars 2004
    Messages
    10 035
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : Ingénieur expert
    Secteur : High Tech - Multimédia et Internet

    Informations forums :
    Inscription : Mars 2004
    Messages : 10 035
    Par défaut
    Citation Envoyé par Olistan Voir le message
    @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

Discussions similaires

  1. Choix d'algorithmes pour jeu de dames
    Par mick009 dans le forum Débuter
    Réponses: 0
    Dernier message: 12/02/2009, 16h09
  2. [Optimisation] Choix du compilateur
    Par Nanoc dans le forum C++
    Réponses: 65
    Dernier message: 22/08/2008, 11h01
  3. Réponses: 61
    Dernier message: 01/08/2008, 22h56
  4. Optimisation de l'algorithme
    Par axel119 dans le forum Servlets/JSP
    Réponses: 3
    Dernier message: 14/12/2007, 15h29
  5. Optimisation -> choix des services à activer
    Par infotron dans le forum Mandriva / Mageia
    Réponses: 20
    Dernier message: 25/05/2004, 12h57

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