Salut,
dansle cadre d'un projet, je dois parser un gros fichier, puis de stocker des elemets un par un dans un vector!
mais là, un probleme se pose: quelle est la meilleur solution pour faire cela
Compter le nombre d'elements, et faire un seul vector::resize au debut!
oubien lire le fichier directment, et a chque nouveau element, on fait un vector::push_back
seulement, pour la deuxieme solution, je ne sais pas si beaucoup</puce> reallocations font faire baisser les performances, a moins que la classe vector soit asser intelligente pour prevoir un peu plus d'espace a chaque reallocation(je ne suis pas sur qu'elle le fait)
Tout dépend de comment (à quel niveau) tu programmes.
L'optimisation devrait être la dernière chose à laquelle tu penses quand tu programmes. Le plus simple est de faire des push_back et de toute façon tu ne verras certainement pas la différence par rapport à un code qui fait un resize en premier.
meme si j'opte pour la deuxieme solution, je ne serais pas obligé de faire ni resize ni reserve? et c'est la STL qui s'en eccupe?
Citation : Nanoc
Tout dépend de comment (à quel niveau) tu programmes.
L'optimisation devrait être la dernière chose à laquelle tu penses quand tu programmes. Le plus simple est de faire des push_back et de toute façon tu ne verras certainement pas la différence par rapport à un code qui fait un resize en premier.
c'est pour un chargeur de fichier OBJ utilisable par OpenGl! ma question etait plustot est ce que les performances avec resize au debut sont egales a celles obtenues avec push_back
avec egales je veux dire tresmninimes
Si tu veux faire un resize, tu devras compter le nombre d'éléments et par conséquent parcourir toute ta liste deux fois (une pour compter une pour remplir). Alors qu'avec des push_back, la STL devra s'occuper de réallouer de temps-en-temps la mémoire que le vector utilise. En faisant un resize, tu garantis un algorithme en O(n) dans le cas des push_back, ce sera plutôt du O(n^2) amorti pour autant que cette notation ait un sens.
Mais encore une fois, ne te pré-occupe pas de ce genre de choses, c'est un détail insignifiant. Je pense que tu n'as de loin pas le niveau pour te pré-occuper de ce genre de différences.
au niveau d'un chargement de mesh, normalement, tu es hors boucle principale, pendant la phase de chargement : tu n'es pas dans une zone critique, tu n'es pas a quelques diziemes de secondes pres.
Néanmoins, si tu connais - avant - la taille finale de ton tableau, fait un reserve, et des push_back : tu n'auras donc qu'un seul réalloc au niveau de reserve
Si tu ne connais pas, et que c'est couteux en calcul de connaitre, alors tant pis, fait des push_back qui te feront quelques réallocs.
Mais comme je disais, c'est pas grave car tu n'es pas en zone critique.
L'optimisation devrait être la dernière chose à laquelle tu penses quand tu programmes.
Pas d'accord, s'il apprend (c'est bon pour nous aussi) immédiatement à penser aux conséquences de ses choix d'implantations il fera de meilleurs programmes plus rapidement. L'optimisation est quelque chose de difficile surtout si les choix d'implantation on été mal fait. Enfin je ne parles pas ici de changer les post-++ par des pré-++ mais de faire des choix qui peuvent changer le fonctionnement de l'application ou du système.
Pour la question présente, elle n'est pas si importante. Ajouter ou retirer un appel à resize() et ajouter la taille de la liste au début du fichier ce n'est pas si grave. Au moins, il fait preuve d'un travail de réflexion sur le projet.
merci MatteX!
finalement, voila ma maniere de proceder:
-faire sans reserve ni resize qu debut, jusquà ce que mon chargeur marche
-a la fin du projet, j'ajouterai eventuellement une methode qui va utiliser un reserve, le code source va rester le meme
Chaque chose en son temps.
Comme tu le dit l'optimisation est quelque chose de difficile.
S'il passe son temps à vouloir tout optimiser ca ne lui permettra pas de faire de meilleurs programmes plus rapidement. Avant optimiser faut comprendre ce que l'on fait. Surtout que l'optimisation est souvent source de bug car on veut aller trop vite.
Mais ses questions sont légitime, et personne ne lui reproche de les poser, au contraire. Mais vue son problème, il passe une journée a choisir s'il va utiliser resize ou un push_back... C'est quand même une sacré perte de temps... (ce n'est pas une critique bien sur, tous le monde fait pareil :P)
je pose cette question surtout parceque j'ai deja commencé un chargeur d'obj(qui lit seulement les positions des vertex) (qui marche en plus)mais je l'ai vite laisser tomber al'eau parceque je n'avais pas tout prevu des le debut!
j'avais une methode ui retourne le nombre de keys dansun fichier( int Count(string key); pour les intimes)
donc voila, j'ai envi de toutrecommencer
Alors qu'avec des push_back, la STL devra s'occuper de réallouer de temps-en-temps la mémoire que le vector utilise. En faisant un resize, tu garantis un algorithme en O(n) dans le cas des push_back, ce sera plutôt du O(n^2) amorti pour autant que cette notation ait un sens.
Mais encore une fois, ne te pré-occupe pas de ce genre de choses, c'est un détail insignifiant. Je pense que tu n'as de loin pas le niveau pour te pré-occuper de ce genre de différences.
Ah non clairement, entre du O(n²) et du O(n), ce n'est pas insignifiant du tout.
Cependant, std::vector<>::push_back() est garanti de complexité amortie constante !! C'est-à-dire qu'en moyenne, ça coûte juste quelque chose de l'ordre d'une copie, c'est pour ça que se casser la tête dès le début sur ça est un détail signifiant.
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Recueil de code C et C++ http://fvirtman.free.fr/recueil/index.html