Je dois lire dans un fichier un nombre inconnu de lignes et les sauvegarder dans une structure (je voudrais éviter un pré-reproducteur pour compter le nombre total d'éléments). Après la phase de lecture, je dois faire des calculs sur chacun des éléments de ces lignes.
J'ai compris deux manières:
Utilisez Utilisez une liste liée chaque fois que je lis une ligne. De cette façon, la phase d'allocation est plus rapide mais la phase de calcul est plus lente.
Qu'est-ce qui vaut mieux d'un point de vue de la complexité? realloc à chaque fois que je lis une ligne. De cette façon, la phase d'allocation est lente mais la phase de calcul est plus facile grâce à l'accès à l'index.
3 Réponses :
À quelle fréquence allez-vous traverser la liste liée? Si ce n'est qu'une fois aller pour la liste liée. Quelques choses encore: Vill il y a beaucoup de petites allocations? Vous pouvez faire quelques tampons plus petits pour dire 10 lignes et lier ces tours. Mais c'est toute une question de profilage.
Je ferais d'abord la chose la plus simple et voyez si cela correspond à mes besoins que puis je pense à optimiser.
Parfois, on déteste trop de temps en pensant à l'optimum, même lorsque la deuxième meilleure solution correspond également aux besoins parfaitement.
Sans plus de détails sur la façon dont vous allez utiliser les informations, il est un peu difficile de commenter la complexité. Cependant, voici quelques réflexions:
Comme les autres utilisateurs ont déjà indiqué:
L'optimisation prématurée est la racine de tout le mal
Donald Knuth
J'ai une proposition différente à l'aide de
realloc : dans le conteneur C ++ stl thestd :: vecteur se développe chaque fois qu'un objet est inséré et pas assez d'espace disponible. La taille de la croissance dépend de la taille pré-allouée en cours mais est spécifique à la mise en œuvre. Par exemple, vous pouvez enregistrer le nombre réel d'objets préallocalisés. Si la taille s'épuise, vous appelezréaffecter avec la double quantité d'espace comme actuellement attribué. J'espère que c'était un peu compréhensible!La refuge est bien entendu que vous allouerez de plus en plus d'espace que vous ne consommerez et vous aurez besoin.
La deuxième racine de tout le mal fait sauter des classes "théorie", abandonnant entièrement l'optimisation et l'écriture de 50 millions de lignes de code de hipster pendant 3 décennies 10 000 fois plus lentement que de simples C, échouent de manière misérable chaque fois qu'une contrainte d'échelle est atteinte, et causer une perte catastrophique de la foi des investisseurs dans l'ensemble du secteur des technologies chaque douzaine d'années ...
A évité votre réponse et je suis en train de mettre en œuvre de cette façon aussi. Tout ce que je dis, c'est que l'optimisation du code est la suivante: comment vous "obtenez GUD" et que DKNuth meme peut être obsolète donné une partie de la python cauchemarish de ces jours-ci.
Liste liée pour la lecture puis Mallock'ing pour l'informatique?