Performance Relative of std:: vector vs. std:: list vs. std:: slist?
Pour une simple liste liée dans lequel l'accès aléatoire à la liste des éléments n'est pas une exigence, y at-il des avantages importants (performance ou autre) à l'aide de std::list au lieu de std::vector ? Si rétro-transversal est nécessaire, serait-il plus efficace d'utiliser std::slist et reverse() la liste avant d'itérer sur ses éléments?
6 réponses
comme d'habitude la meilleure réponse aux questions de performance est à profil les deux implémentations pour votre cas d'utilisation et de voir ce qui est plus rapide.
en général si vous avez des insertions dans la structure de données (Autre qu'à la fin) alors vector peut être plus lent, sinon dans la plupart des cas vector est censé mieux fonctionner que list si seulement pour problèmes de localité de données , cela signifie que si deux éléments que sont adjacents dans le jeu de données sont adjacents dans la mémoire, puis l'élément suivant sera déjà dans le cache du processeur et n'aura pas à biper la mémoire dans le cache.
gardez aussi à l'esprit que l'espace au-dessus d'un vector est constant (3 pointeurs) alors que l'espace au-dessus d'un list est payé pour chaque élément, cela réduit également le nombre d'éléments complets (données plus au-dessus) qui peuvent résider dans le cache à tout moment.
structure de données par défaut à laquelle il faut penser en C++ est le vecteur .
considérer les points suivants...
1] Transversal:
Les noeuds de liste sont dispersés partout dans la mémoire et donc list traversal mène à cache missses . Mais la traversée des vecteurs est douce.
2] Insertion et suppression:
En moyenne 50% des éléments doivent être déplacés quand vous faites cela à un vecteur, mais les caches sont très bons à cela! Mais, avec les listes, vous devez traverser au point d'insertion/suppression... de nouveau... cache rate!
Et étonnamment les vecteurs gagnent cette affaire aussi!
3] Conservation:
Lorsque vous utilisez des listes, il y a 2 pointeurs par élément(vers l'avant et vers l'arrière) donc une liste est beaucoup plus grande qu'un vecteur!
Vecteurs avez juste besoin d'un peu plus de mémoire que les éléments réels besoin.
Vous devez avoir une raison de ne pas utiliser un vecteur.
Référence:
J'ai appris cela en parlant du Seigneur Bjarne Stroustrup: https://youtu.be/0iWb_qi2-uI?t=2680
tout Simplement pas. La liste a des avantages par rapport au vecteur, mais l'accès séquentiel n'en est pas un - si c'est tout ce que vous faites, alors un vecteur est meilleur.
cependant.. un vecteur est plus coûteux à ajouter des éléments supplémentaires qu'une liste, surtout si vous insérez au milieu.
comprendre comment ces collections sont mises en œuvre: un vecteur est un tableau séquentiel de données, une liste est un élément qui contient les données et des pointeurs vers le prochain élément. Une fois que vous aurez compris cela, vous comprendrez pourquoi les listes sont bonnes pour les inserts, et mauvaises pour l'accès aléatoire.
(ainsi, l'itération inverse d'un vecteur est exactement la même que pour l'itération en avant - l'itérateur soustrait juste la taille des éléments de données à chaque fois, la liste doit encore Sauter à l'élément suivant via le pointeur)
si vous avez besoin de traverser à l'envers une lisière est peu susceptible d'être l'infrastructure de données pour vous.
une liste conventionnelle (doublement) liée vous donne le temps constant d'insertion et de suppression n'importe où dans la liste; un vecteur donne le temps amorti constant d'insertion et de suppression seulement à la fin de la liste. Pour un vecteur d'insertion et de suppression le temps est linéaire ailleurs qu'à la fin. Ce n'est pas toute l'histoire; il y a aussi des facteurs constants. Un vecteur est un plus simple infrastructure de données qui présente des avantages et des inconvénients selon le contexte.
La meilleure façon de comprendre cela est comprendre comment ils sont mis en œuvre. Une liste liée comporte un pointeur suivant et un pointeur précédent pour chaque élément. Un vecteur est un tableau d'éléments traités par index. De cela, vous pouvez voir que les deux peuvent faire efficace en avant et en arrière traversal, tandis que seul un vecteur peut fournir un accès aléatoire efficace. Vous pouvez également voir que la mémoire aérienne d'un list est par élément alors que pour le vecteur il est constant. Et vous pouvez également voir pourquoi le temps d'insertion est différent entre les deux structures.
quelques repères rigoureux sur le sujet: http://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html
comme d'autres l'ont noté, le stockage de mémoire contigu signifie std::vecteur est meilleur pour la plupart des choses. Il n'y a pratiquement aucune bonne raison d'utiliser std::list sauf pour de petites quantités de données (où tout peut rentrer dans le cache) et/ou où l'effacement et la réinsertion sont fréquents. Les garanties de complexité ne concernent pas performances réelles en raison de la différence entre la vitesse de mémoire cache et la vitesse de mémoire principale (200x) et de la façon dont l'accès à la mémoire contiguë affecte l'utilisation de la mémoire cache. Voir Chandler Carruth (google) parler de la question ici: https://www.youtube.com/watch?v=fHNmRkzxHWs
et le discours de Mike Acton sur le Design orienté vers les données ici: https://www.youtube.com/watch?v=rX0ItVEVjHc
voir cette question pour plus de détails sur les coûts:
quelles sont les garanties de complexité des conteneurs standard
si vous avez une liste et que vous voulez maintenant la Parcourir dans l'ordre inverse, pourquoi ne pas changer le type pour lister partout?