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.

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 :question:

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 :question:

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 :D) 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 :aie:

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 :question:

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.

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...

Ah je n'avais pas vu qu'il existé une fonction equal_range pour un vector trié et effectivement c'est beaucoup mieux :mrgreen: