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 :

multimap ou vecteur trié -> programme parallèle


Sujet :

SL & STL C++

  1. #1
    Membre du Club
    Profil pro
    Inscrit en
    Avril 2010
    Messages
    58
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2010
    Messages : 58
    Points : 46
    Points
    46
    Par défaut multimap ou vecteur trié -> programme parallèle
    Bonjour,

    je me pose une question, j'ai un programme que je dois paralléliser pouvant contenir un nombre important de données et réalisant des opérations dessus. Ces données peuvent être identifiées par un id et plusieurs données peuvent posséder le même id. Chaque thread de mon programme doit récupérer l'ensemble des données possédant un certain id et travailler dessus.

    Ma question est pour un programme parallèle la meilleure solution est d'utiliser un multimap ou un vecteur trié selon l'id des données?

    Merci de vos réponses.

  2. #2
    Expert éminent sénior
    Avatar de koala01
    Homme Profil pro
    aucun
    Inscrit en
    Octobre 2004
    Messages
    11 612
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : Belgique

    Informations professionnelles :
    Activité : aucun

    Informations forums :
    Inscription : Octobre 2004
    Messages : 11 612
    Points : 30 611
    Points
    30 611
    Par défaut
    Salut,

    En gros, avant de pouvoir te répondre, il faudrait avoir quelques informations supplémentaires, parmi lesquelles, la réponse à quelques questions :
    Les id sont ils effectivement uniques ou peut on envisager que plusieurs éléments aient le meme id
    1. Vas tu ajouter des éléments de manière plus ou moins aléatoire, ou vas tu essentiellement insérer tous les éléments "au début du traitement" pour ne faire que "les manipuler" par la suite question:
    2. Lors de l'ajout des éléments, se fera-t-il dans un ordre plus ou moins trié ou dans un ordre particulièrement aléatoire


    En effet, je ne vois personnellement pas d'intérêt à travailler avec une multi map si tous les identifiants sont effectivement unique, une map me semblerait, par défaut, plus intéressante

    De même, il faut savoir que tu devras jouer avec des mutexes lors de l'ajout s'il se fait "à n'importe quel moment", ne serait-ce que pour avoir la certitude de ne pas avoir de "faux négatifs" (un élément non trouvé alors qu'un thread est, justement, occupé à l'insérer)

    Enfin, il faut savoir que, à algorithme de recherche identique (je pense bien évidemment à la dichotomie ) l'insertion d'un élément dans une (multi)map est globalement plus lente lorsqu'il s'agit de la remplir avec des éléments déjà triés que lorsqu'on insertion (dans les mêmes conditions) et le tri dans un vecteur.

    Par contre, si les éléments sont insérés dans un ordre aléatoire que tu décides d'attendre d'avoir besoin de rechercher les éléments pour les trier ou d'effectuer le tri après chaque insertion, le temps pris par l'insertion et / ou le tri sera globalement plus long que celui de l'insertion dans une (multi) map.

    Et comme le tri d'un vecteur doit, lui aussi, se faire sous la protection d'un mutex, et est donc susceptible de bloquer l'insertion suivante, ben, tu comprendras aisément que, selon l'usage que tu en feras, soit tu gagnera en temps d'exécution, soit, au contraire, tu y perdra énormément

    Tout cela pour dire qu'il faut déjà vraiment avoir une idée très précise de la manière dont les éléments vont arriver avant de pouvoir donner une réponse claire et définitive

    Mais, ceci dit, peut être les explications que je viens de donner te suffiront-elles pour choisir
    A méditer: La solution la plus simple est toujours la moins compliquée
    Ce qui se conçoit bien s'énonce clairement, et les mots pour le dire vous viennent aisément. Nicolas Boileau
    Compiler Gcc sous windows avec MinGW
    Coder efficacement en C++ : dans les bacs le 17 février 2014
    mon tout nouveau blog

  3. #3
    Membre du Club
    Profil pro
    Inscrit en
    Avril 2010
    Messages
    58
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2010
    Messages : 58
    Points : 46
    Points
    46
    Par défaut
    Désolé du retard, alors les éléments sont insérés au début du traitement et seulement lus dans le reste du programme. La clé n'est justement pas unique c'est pourquoi j'ai pensé au multimap car je dois rechercher un ensemble d’éléments qui ont une même caractéristique. J'ai donc remplacé mon vector par une multimap et le programme en séquentiel est largement plus rapide.

  4. #4
    Rédacteur/Modérateur
    Avatar de JolyLoic
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Août 2004
    Messages
    5 463
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 49
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Août 2004
    Messages : 5 463
    Points : 16 213
    Points
    16 213
    Par défaut
    Si tu n'as besoin de trier qu'une fois, au début, je suis très surpris que le programme soit plus rapide avec une map (simple ou multi) qu'avec un vecteur...
    Ma session aux Microsoft TechDays 2013 : Développer en natif avec C++11.
    Celle des Microsoft TechDays 2014 : Bonnes pratiques pour apprivoiser le C++11 avec Visual C++
    Et celle des Microsoft TechDays 2015 : Visual C++ 2015 : voyage à la découverte d'un nouveau monde
    Je donne des formations au C++ en entreprise, n'hésitez pas à me contacter.

  5. #5
    Membre du Club
    Profil pro
    Inscrit en
    Avril 2010
    Messages
    58
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2010
    Messages : 58
    Points : 46
    Points
    46
    Par défaut
    Ah je n'avais pas vu qu'il existé une fonction equal_range pour un vector trié et effectivement c'est beaucoup mieux

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. recherche un élément dans un vecteur trié
    Par jena dans le forum Signal
    Réponses: 5
    Dernier message: 10/12/2008, 13h02
  2. Réponses: 3
    Dernier message: 13/04/2008, 22h58
  3. programmation parallèle avec MPI
    Par salseropom dans le forum Algorithmes et structures de données
    Réponses: 1
    Dernier message: 03/08/2006, 10h45
  4. Programmation parallèle - Linux
    Par pilou254 dans le forum Autres éditeurs
    Réponses: 4
    Dernier message: 25/06/2006, 06h55
  5. [MFC] Programmation parallèle sous VC++
    Par Axiome dans le forum MFC
    Réponses: 4
    Dernier message: 14/12/2005, 01h10

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