Bonjour à tous,
je me demandais si le parcours d'un ensemble (Set) serait plus rapide que celui d'une liste ou d'un vecteur (ou même d'une map) pour un nombre d'élément inférieur à 5.
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
rapidité de parcours d'un set
Bonjour à tous,
je me demandais si le parcours d'un ensemble (Set) serait plus rapide que celui d'une liste ou d'un vecteur (ou même d'une map) pour un nombre d'élément inférieur à 5.
vector est le plus rapide
Pour un nombre d'éléments inférieur à 5 fais un tableau de taille 5 tout simplement.
J'ai oublié de préciser qe je ne connais pas d'avance la taille du tableau.
Taille = 5 c'est une estimation.
Je sais q'en java les vecterr sont à proscrire par rapport aux listes:
http://bruce-eckel.developpez.com/li...aduction/tij2/
Type Get Iteration Insert Remove
tableau 1430 3850 na na
ArrayList 3070 12200 500 46850
LinkedList 16320 9110 110 60
Vector 4890 16250 550 46850
Qu'en est-il en c++
la complexité est la suivante pour les operation de liste
O(n)+ pour les vector
constant pour les list
O(n) pour les deque
O(log(n))+ pour les map, set
mais soit rassuré la difference est insignifiante pour des conteneur si petit que les tiens...
ZaaN, merci d'éviter de dire n'importe quoi.
L'insertion dans un vecteur en en O(1) amorti.
L'insertion dans une liste est en O(1).
L'insertion dans une deque en en O(1) amorti.
L'insertion dans un set est en O(log n).
Je ne vois pas trop à quoi ton "+" correspond.
Encore une imprecision de ma part : il se peut que je parcours plusieurs millions de fois ce contener de taille à priori inf à 5.Envoyé par ZaaN
Il est vrai que les complexités cités devraient avoir un impact insignifiant sur un conteneur de taille 5.
Mais qu'en ai-t-il lorsque l'on parcours 1 millions de fois un conteneur de taille 5?
Quel conteneur serait le plus rapide en terme de parcours (de lecture) en excluant le tableau qui ne pourras être de 2 dimenions variables (car inconnue lors de l'initialisation)
Les complexités citées ne concernaient pas le parcours. Le parcours de tous les conteneurs est en O(n). Mais std::vector (ou les tableaux C) sera un peu plus rapide car c'est le conteneur le plus simple et ses éléments sont contigus en mémoire.
merci pour vos réponses
Répondre avec citation
Partager