(C++) à la Recherche de conseils pour réduire l'utilisation de la mémoire

J'ai un problème avec un très tendue et dure limite de mémoire. Je suis un RPC geek et je veux réduire mon utilisation de la mémoire. Merci de me donner quelques conseils.

Un de mes amis a recommandé de prendre des fonctions à l'intérieur de mon structs d'eux.
par exemple au lieu d'utiliser:

struct node{
   int f()
   {}
}

il m'a recommandé d'utiliser:

int f(node x)
{}

est-ce réellement de l'aide?

Remarque: j'ai beaucoup de copies de mon struct.

voici quelques informations:

Je code une sorte de segment de l'arbre pour un exercice de problème sur un site de juge. Je reçois des nœuds de l'arborescence dans une struct. mon struct a ces variables:

  int start;
  int end;
  bool flag;
  node* left;
  node* right;

La limite de la mémoire est de 16 MO et je suis en utilisant 16.38 MO.

Quel est votre programme? Quels algorithmes t-il? Il est difficile de parler des optimisations en termes généraux.
si vous êtes sur linux, alors vous pouvez utiliser valgrind/massif de voir où votre tas va
Le remplacement des fonctions de membre avec des fonctions libres de ne pas affecter la taille du code dans le moindre. Cependant, il sera plus facile de faire des erreurs comme le passage par valeur plutôt que de référence.
Pouvez vous indique l'URL du problème ? Ou peut-être plus de code ? Sinon, en supposant qu'aucune perte de mémoire / pas de nœuds supplémentaires créé les seules choses que vous pourriez faire est d'utiliser short au lieu de int mais cela dépend de la taille du problème..
Février: Ce n'est pas un problème public. mais voici un semblable et plus facile problème:z-trening.com/tasks.php?show_task=5000000081
c'est le même problème ? Quel est le nombre de "cartes" dans votre cas ?
La taille de saisie est la même. Le problème est légèrement différent, mais la différence est, en son temps, pas de la taille et je suis le résoudre en moins de 0,7 secondes
L'arbre binaire est un ? Alors vous n'avez pas besoin de votre nœuds, il suffit d'utiliser des tableaux pour stocker vos informations. Étant donné un nœud i les enfants sont 2i et 2i+1. Vous n'avez pas besoin de deux pointeurs.
Êtes-vous à l'aide de toute la récursivité sur le code ou la transmission des données par copie et non par référence?
Vous avez raison. Si idiot de moi.
une fois que vous aurez changé votre code pourriez-vous nous dire comment faible de l'utilisation de la mémoire s'est passé ?
Il a utilisé 14.72 MO

InformationsquelleAutor |

c++memory-management

9

Non, membre régulier des fonctions de ne pas faire de la classe ou structure plus grande. L'introduction d'un virtuel fonction peut (sur de nombreuses plateformes) ajouter un vtable pointeur vers la classe. Sur x86, ce qui permettrait d'augmenter la taille de quatre octets. Pas plus de mémoire sera nécessaire lorsque vous ajoutez des fonctions virtuelles, -- il y a un pointeur est suffisant. De la taille d'une classe ou d'un type struct n'est jamais nulle (indépendamment du fait qu'il a tout membre de variables ou de fonctions virtuelles). C'est pour s'assurer que chaque instance occupe son propre espace mémoire (source, section 9.0.3).
- Merci. et avez-vous des suggestions?
- user12345: je n'ai pas, parce que Nick Meyer a souligné dans un commentaire à votre post, il est difficile de discuter de l'utilisation de la mémoire optimisation en général. Vous devez être plus précis.
- Merci quand même. Il a été d'une grande aide.
InformationsquelleAutor Martin Törnwall
21

Je devine par le sous-texte de votre question que la majorité de votre utilisation de la mémoire est de données, pas de code. Voici quelques conseils:
- Si vos plages de données sont limitées, profitez-en. Si la portée d'un nombre entier est -128 à 127, utilisez char au lieu de int, ou unsigned char si elle est de 0 à 255. De même, l'utilisation int16_t ou uint16_t pour des gammes de -32768..32767 et 0..65535.
- Réorganiser les éléments de la structure de sorte que le plus grand des éléments viennent en premier, de sorte que les données d'alignement ne laissez pas d'espace mort dans le milieu de la structure. Vous pouvez aussi, généralement, de contrôle de remplissage via les options du compilateur, mais c'est juste pour mieux faire la mise en page optimale en premier lieu.
- Utilisez des contenants qui n'ont pas beaucoup de frais généraux. Utilisation vector au lieu de list, par exemple. Utilisation boost::ptr_vector au lieu de std::vector contenant shared_ptr.
- Éviter de méthodes virtuelles. La première méthode virtuelle que vous ajoutez à une structure ou classe ajoute un pointeur caché pour un vtable.
- Cela a été d'une grande aide. Merci
InformationsquelleAutor Mark Ransom
5

À mon avis, la meilleure façon de réduire la mémoire est de considérer votre algorithmique complexité de l'espace au lieu de justing faire amende optimisations de code. Reconsidérer les choses comme la programmation dynamique des tables, des inutiles, des copies, en général quelque chose qui est discutable en termes d'efficacité de mémoire. Aussi, essayez de libérer les ressources de la mémoire au début à chaque fois qu'ils ne sont plus nécessaires.

InformationsquelleAutor Ahmed K. Atwa Mohamed
1

Pour votre dernier exemple (l'arbre), vous pouvez utiliser un piratage intelligent avec XOR pour remplacer les deux nœud pointeurs avec un nœud unique pointeur, comme décrit ici. Cela ne fonctionne que si vous traversez l'arbre dans le bon ordre, cependant. De toute évidence ce phénomène nuit à la lisibilité du code, il doit donc être quelque chose comme un dernier recours.
- Merci pour ce lien.. des choses Intéressantes, j'avais pensé à ça quand j'étais codant pour très, très serré, les contraintes de mémoire w/ systèmes embarqués.
InformationsquelleAutor
0

Vous pouvez utiliser des indicateurs de compilation à faire une certaine optimisation. Si vous êtes à l'aide de g++, vous pouvez le tester avec: -O2

Il y a de grandes discussions sur le sujet:

C++ Techniques D'Optimisation

Devons-nous continuer à optimiser "la petite"?

Constantes et d'optimisation du compilateur en C++

Quelles sont les connus C/C++ optimisations pour GCC
- Malheureusement, Le juge de la compile, pas moi!
- Vous devez ajouter cette information à la question.
- Le juge ? Faites-vous de la programmation du concours ? Pourriez-vous donner des détails sur le problème ? Si vous avez atteint la limite de mémoire alors votre algorithme est probablement pas la bonne.
- Désolé. J'ai juste ajouté plus d'info
InformationsquelleAutor karlphillip
0

Les deux possibilités ne sont pas toutes équivalentes:
- Dans la première, f() est une fonction membre de node.
- Dans le second, f() est un logiciel gratuit (ou de l'espace-champ) de la fonction. (Note également que la signature de deux f() sont différentes.)
Maintenant de noter que, dans le premier style, f() est un inline de la fonction membre. La définition d'une fonction membre à l'intérieur du corps de classe fait en ligne. Bien que l'in-lining n'est pas garantis, c'est juste une indication pour le compilateur. Pour les fonctions avec des petits corps, il peut être bon de l'inclure, comme il permettrait d'éviter l'appel de fonction-dessus de la tête. Cependant, je n'ai jamais vu que comme un facteur très important.

Si vous ne souhaitez pas ou si f() ne pas qualifiy pour l'in-lining, vous devez définir à l'extérieur du corps de classe (sans doute dans une .fichier cpp) comme:
```
 int node::f() { /* stuff here */ }
```
Si l'utilisation de la mémoire est un problème dans votre code, puis très probablement les sujets ci-dessus ne sont pas pertinents. Explorant ce qui suit pourrait vous donner un indice
- Trouver des tailles de toutes les classes dans votre programme. Utilisation sizeof pour trouver cette information, par exemple, sizeof( noeud)
- Trouver quel est le nombre maximum d'objets de chaque classe que votre programme est en cours de création.
- À l'aide de ces deux séries d'informations, estimation pire des cas, l'utilisation de la mémoire par votre programme
  
  Pire des cas, l'utilisation de la mémoire = n1 * sizeof( node1 ) + n2 * sizeof( ud2 ) + ...
Si le nombre est trop élevé, vous avez les choix suivants:
- Réduire le nombre maximum d'instances de classes. Ce ne sera probablement pas possible car cela dépend de l'entrée au programme, et qui est au-delà de votre contrôle
- Réduire la taille de chaque classes. C'est dans votre contrôle si.
Comment réduire la taille des classes? Essayez d'emballer les membres de la classe compacte pour éviter emballage.

InformationsquelleAutor
0

Comme d'autres l'ont dit, avoir des méthodes de ne pas augmenter la taille de la structure, à moins que l'un d'eux est virtuel.

Vous pouvez utiliser bitfields pour compresser efficacement les données (ce qui est particulièrement efficace avec votre booléen...). Aussi, vous pouvez utiliser les indices de la place des pointeurs, pour économiser quelques octets.

N'oubliez pas de bien répartir vos nœuds en gros morceaux plutôt qu'individuellement (p. ex., à l'aide de [nouveau] une fois, ce n'est pas une nouvelle à plusieurs reprises) pour éviter de gestion de la mémoire de frais généraux.

Si vous n'avez pas besoin de toute la flexibilité de votre nœud pointeurs de fournir, vous pouvez être en mesure de réduire ou de les éliminer. Par exemple, heapsort a toujours un quasi-pleine arbre binaire, de sorte que la mise en application des normes utilise implicite de l'arbre, qui n'a pas besoin de pointeurs à tous.

Par-dessus tout, de trouver un algorithme différent peut changer complètement le jeu...

InformationsquelleAutor

Vous devez vous connecter pour publier un commentaire.