J'ai un problème avec une limite de mémoire vraiment serrée et difficile. Je suis un geek CPP et je veux réduire mon utilisation de la mémoire. S'il vous plaît donnez-moi des conseils.
Un de mes amis a recommandé de prendre des fonctions dans mes structures en dehors d'eux. Par exemple, au lieu d'utiliser: p>
int start; int end; bool flag; node* left; node* right;
7 Réponses :
Non, les fonctions de membre régulières ne font pas la classe ou la structure plus grandes. Présentation d'une fonction peut (sur de nombreuses plateformes) Ajoutez un POINTER TVTABLE à la classe. Sur x86 qui augmenterait la taille par quatre octets. Plus aucune mémoire ne sera requise lorsque vous ajoutez des fonctions virtuelles, mais - un pointeur suffit. La taille d'un type de classe ou de structure n'est jamais nulle (indépendamment de la totalité des variables de membre ou des fonctions virtuelles). C'est pour vous assurer que chaque instance occupe son propre espace mémoire ( source , section 9.0.3).
Merci. Et avez-vous des suggestions?
User12345: Je ne le fais pas, car comme Nick Meyer a souligné dans un commentaire à votre poste, il est difficile de discuter d'une optimisation de l'utilisation de la mémoire en général. Tu dois être plus précis.
Merci quand même. C'était une bonne aide.
Vous pouvez utiliser des drapeaux de compilation pour faire une certaine optimisation. Si vous utilisez g ++, vous pouvez tester avec: -o2
Il y a de grands discussions sur le sujet:
Techniques d'optimisation C ++
Devrions-nous toujours optimiser "dans le petit"?
Malheureusement, le juge le compile, pas moi!
Juge ? Faites-vous un concours de programmation? Pourriez-vous donner des détails sur le problème? Si vous avez atteint la limite de mémoire, votre algorithme n'est probablement pas le bon.
Pardon. Je viens d'ajouter plus d'informations
À mon avis, le meilleur moyen de réduire la mémoire consiste à considérer votre compréhension de l'espace algorithmique au lieu de simplement faire des optimisations de code fines. Reconsidérer des choses comme des tables de programmation dynamiques, des copies inutiles, généralement toute chose qui est discutable en termes d'efficacité de la mémoire. Essayez également de libérer des ressources de mémoire tôt chaque fois qu'elles ne sont plus nécessaires.
Je suppose que par le sous-texte de votre question que la majorité de votre utilisation de la mémoire est des données, pas de code. Voici quelques conseils:
char au lieu de INT ou sans signé Char s'il est 0 à 255. Utilisez également int16_t ou uint16_t pour les gammes de -32768..32767 et 0..65535.
- Réorganisez les éléments de structure afin que les éléments plus grands arrivent en premier, de sorte que l'alignement des données ne laissait pas d'espace mort au milieu de la structure. Vous pouvez également contrôler généralement le rembourrage via des options du compilateur, mais il est préférable de rendre la mise en page optimale en premier lieu.
- Utilisez des conteneurs qui n'ont pas beaucoup de frais généraux. Utilisez
vecteur au lieu de la liste , par exemple. Utilisez boost :: ptr_vector < / a> au lieu de std :: vecteur contenant partagé_ptr .
- Évitez les méthodes virtuelles. La première méthode virtuelle que vous ajoutez à une structure ou à une classe ajoute un pointeur caché à un circuit bancaire.
C'était une bonne aide. Merci
Les deux possibilités ne sont pas du tout équivalentes:
f () est une fonction de membre du noeud .
- dans la seconde,
f () est une fonction libre (ou nom d'espace de noms). (Notez également que la signature de deux f () est différente.)
Notez maintenant que, dans le premier style, f () est une fonction inline . Définir une fonction de membre à l'intérieur du corps de classe le rend en ligne. Bien que l'inlinage ne soit pas guranteed, il ne s'agit que d'un indice du compilateur. Pour les fonctions avec de petits corps, il peut être bon de les aligner, car cela éviterait la fonction d'appel sur la tête. Cependant, je n'ai jamais vu que pour être un facteur de fabrication de fabriquer. Si vous ne voulez pas ou si f () n'est pas qualifié pour l'inlinage, vous devez définir Il en dehors du corps de classe (probablement dans un fichier .cpp) comme: xxx Si l'utilisation de la mémoire est un problème dans votre code, les sujets ci-dessus ne sont pas pertinents. Explorer ce qui suit pourrait vous donner un indice
- Trouvez les tailles de toutes les classes de votre programme. Utilisez
Tailleof pour trouver ces informations, par exemple Tailleof (noeud)
- Trouvez quel est le nombre maximum d'objets de chaque classe que votre programme crée.
-
Utilisation des deux séries d'informations ci-dessus, estimez le pire des cas de mémoire par votre programme
Utilisation de la mémoire pire des cas = N1 * Tailleof (Node1) + N2 * Taille de taille (Node2) + ...
Si le numéro ci-dessus est trop élevé, vous avez les choix suivants:
- Réduire le nombre d'instances maximales de classes. Cela ne sera probablement pas possible car cela dépend de l'entrée du programme, et qui dépasse votre contrôle
- Réduisez la taille de chaque classe. Ceci est dans votre contrôle cependant.
Comment réduire la taille des classes? Essayez d'emballer les membres de la classe compacte pour éviter Emballage .
Comme d'autres l'ont dit, avoir des méthodes n'augmente pas la taille de la structure à moins que l'une d'entre elles est virtuelle.
Vous pouvez utiliser des champs de bit pour compresser efficacement les données (ceci est particulièrement efficace avec votre booléen ...). En outre, vous pouvez utiliser des indices au lieu des pointeurs, pour sauver quelques octets.
N'oubliez pas d'allouer vos nœuds dans de gros morceaux plutôt que de manière individuelle (par exemple, à l'aide de nouvelles [] une fois, pas régulièrement de plusieurs fois) pour éviter la gestion de la mémoire.
Si vous n'avez pas besoin de la pleine flexibilité, vos pointeurs de nœud fournissent, vous pourrez peut-être les réduire ou les éliminer. Par exemple, Heapsort a toujours un arbre binaire presque complet. La mise en œuvre standard utilise donc un arbre implicite, qui n'a pas besoin de pointeurs du tout.
Surtout surtout, trouver un algorithme différent peut changer complètement le jeu ...
Pour votre exemple final (l'arborescence), vous pouvez utiliser un hack intelligent avec XOR pour remplacer les deux pointeurs de nœud avec un seul pointeur de nœud, comme décrit ici . Cela ne fonctionne que si vous parcourez l'arborescence dans le bon ordre, cependant. Évidemment, cela fait mal la lisibilité du code, alors devrait être une autre recours.
Merci pour ce lien .. Intéressant, je souhaite y avoir pensé quand je codérissait pour des contraintes de mémoire très très étroites avec des systèmes embarqués.
Que fait votre programme? Quels algorithmes utilisent-t-il? Il est difficile de parler d'optimisations en termes généraux.
Si vous êtes sous Linux, vous pouvez utiliser Valgrind / Massif pour voir où se passe votre tas
Le remplacement des fonctions des membres avec des fonctions libres n'affectera pas la taille du code au moindre. Cependant, il sera plus facile de faire des erreurs comme passer de la valeur plutôt que de la référence.
Pouvez-vous indiquer l'URL du problème? Ou peut-être plus de code? Sinon, n'ayant aucune perte de mémoire / aucun nœud supplémentaire créé les seules choses que vous pouvez effectuer est d'utiliser
court au lieu deint mais cela dépend de la taille du problème ..@ Loïc Février: Ce n'est pas un problème public. Mais voici un problème similaire et plus facile: z-trening.com/tasks.php? show_task = 5000000081
@ user12345: C'est le même problème? Quel est le nombre de "cartes" dans votre cas?
La taille d'entrée est la même. Le problème est légèrement différent mais la différence est dans son temps pas la taille et je la résout en moins de 0,7 seconde.
L'arbre est un binaire? Ensuite, vous n'avez pas besoin de vos nœuds, utilisez simplement des tableaux pour stocker vos informations. Compte tenu d'un nœud
i les enfants sont2i et2i + 1 . Vous n'avez pas besoin de vos deux pointeurs.Utilisez-vous une récursion sur le code ou le passage des données par copie au lieu de vous référer?
Vous avez raison. Si stupide de moi.
@ user12345: Une fois que vous aurez changé votre code pourriez-vous nous dire à quel point l'utilisation de la mémoire est faible?