Manière professionnelle de produire un gros problème sans remplir d'énormes tableaux: C ++, libérer de la mémoire d'une partie d'un tableau

20

Je suis en train de développer une simulation physique, et comme je suis plutôt novice en programmation, je continue à rencontrer des problèmes lors de la production de gros programmes (problèmes de mémoire principalement). Je connais l'allocation et la suppression de mémoire dynamique (nouveau / supprimer, etc.), mais j'ai besoin d'une meilleure approche de la façon dont je structure le programme.

Disons que je simule une expérience qui se déroule sur quelques jours, avec un taux d'échantillonnage très élevé. J'aurais besoin de simuler un milliard d'échantillons et de les parcourir.

En version super simplifiée, nous dirons qu'un programme prend les tensions V [i] et les additionne en cinq:

c'est-à-dire NewV [0] = V [0] + V [1] + V [2] + V [3] + V [4]

alors NewV [1] = V [1] + V [2] + V [3] + V [4] + V [5]

alors NewV [2] = V [2] + V [3] + V [4] + V [5] + V [6] ... et cela continue pour un milliard d'échantillons.

En fin de compte, j'aurais V [0], V [1], ..., V [1000000000], alors que les seuls que je devrais stocker pour la prochaine étape sont les 5 derniers V [i] s.

Comment supprimer / désallouer une partie du tableau afin que la mémoire soit libre de réutiliser (disons V [0] après la première partie de l'exemple où elle n'est plus nécessaire)? Existe-t-il des alternatives à la structure d'un tel programme?

J'ai entendu parler de malloc / free, mais j'ai entendu qu'ils ne devraient pas être utilisés en C ++ et qu'il existe de meilleures alternatives.

Merci beaucoup!

tldr; que faire des parties de tableaux (éléments individuels) dont je n'ai plus besoin et qui occupent une énorme quantité de mémoire?

Drummermean
la source
2
Vous ne pouvez pas désallouer une partie d'un tableau. Vous pouvez le réallouer à un tableau plus petit ailleurs, mais cela peut s'avérer coûteux. Vous pouvez utiliser à la place une structure de données différente telle qu'une liste chaînée. Vous pouvez peut-être également stocker les étapes dans Vau lieu de dans un nouveau tableau. Fondamentalement, cependant, je pense que votre problème est lié à vos algorithmes ou à vos structures de données, et comme nous n'avons pas de détails, il est difficile de savoir comment le faire efficacement.
Vincent Savard
4
Note latérale: les SMA de longueur arbitraire peuvent être calculés particulièrement rapidement avec cette relation de récurrence: NewV [n] = NewV [n-1] - V [n-1] + V [n + 4] (votre notation). Mais gardez à l'esprit que ces filtres ne sont pas particulièrement utiles. Leur réponse en fréquence est sincère, ce qui n'est presque jamais ce que vous voulez (lobes latéraux très élevés).
Steve Cox le
2
SMA = moyenne mobile simple, pour tous ceux qui se demandent.
Charles
3
@SteveCox, la façon dont il l'a écrit, il a un filtre FIR. Votre récidive est le formulaire IIR équivalent. Dans les deux cas, vous pouvez conserver un tampon circulaire des N dernières lectures.
John R. Strohm
@ JohnR.Strohm la réponse impulsionnelle est identique et finie
Steve Cox

Réponses:

58

Ce que vous décrivez, "lissage par cinq", est un filtre numérique à réponse impulsionnelle finie (FIR). Ces filtres sont implémentés avec des tampons circulaires. Vous ne conservez que les N dernières valeurs, vous gardez un index dans le tampon qui vous indique où se trouve la valeur la plus ancienne, vous écrasez la valeur la plus ancienne actuelle par la plus récente à chaque étape et vous incrémentez l'index de manière circulaire à chaque fois.

Vous conservez vos données collectées, que vous allez contrôler, sur disque.

Selon votre environnement, cela peut être l'un de ces endroits où vous feriez mieux d'obtenir une aide expérimentée. Dans une université, vous mettez une note sur le babillard du département d'informatique, offrant un salaire étudiant (ou même des tarifs de conseil aux étudiants) pour quelques heures de travail, pour vous aider à analyser vos données. Ou peut-être que vous offrez des points de possibilité de recherche de premier cycle. Ou quelque chose.

John R. Strohm
la source
6
Un tampon circulaire semble en effet être ce que je recherche! J'ai maintenant installé les bibliothèques boost C ++ et inclus boost / circular_buffer.hpp, et fonctionne comme prévu. Merci, @John
Drummermean
2
seuls les filtres FIR très courts sont implémentés sous forme directe dans les logiciels, et les SMA ne le sont presque jamais.
Steve Cox
@SteveCox: La formule des bords de fenêtre que vous avez utilisée est assez efficace pour les filtres entiers et à virgule fixe, mais elle est incorrecte pour les virgules flottantes, où les opérations ne sont pas commutatives.
Ben Voigt
@BenVoigt je pense que vous vouliez répondre à mon autre commentaire, mais oui, cette forme introduit un cycle limite autour d'une quantification qui peut être très délicate. heureusement cependant, ce cycle limite particulier se trouve être stable.
Steve Cox
Vous n'avez pas vraiment besoin de boost pour un tampon circulaire pour cette utilisation uu Vous utiliserez beaucoup plus de mémoire que nécessaire.
GameDeveloper du
13

Chaque problème peut être résolu en ajoutant un niveau supplémentaire d'indirection. Alors fais ça.

Vous ne pouvez pas supprimer une partie d'un tableau en C ++. Mais vous pouvez créer un nouveau tableau contenant uniquement les données que vous souhaitez conserver, puis supprimer l'ancien. Ainsi, vous pouvez créer une structure de données qui vous permet de "supprimer" les éléments que vous ne voulez pas de l'avant. Ce qu'il va réellement faire, c'est créer un nouveau tableau et copier les éléments non supprimés dans le nouveau, puis supprimer l'ancien.

Ou vous pouvez simplement utiliser std::dequece qui peut déjà le faire. deque, ou "file d'attente à double extrémité", est une structure de données destinée aux cas où vous supprimez des éléments d'une extrémité tout en ajoutant des éléments à l'autre.

Nicol Bolas
la source
30
Chaque problème peut être résolu en ajoutant un niveau d'indirection supplémentaire ... sauf à de nombreux niveaux d'indirection.
YSC
17
@YSC: et l'orthographe :)
Courses de légèreté avec Monica
1
pour ce problème particulier std::dequeest la voie à suivre
davidbak
7
@davidbak - Quoi? Il n'est pas nécessaire d'allouer et de libérer constamment de la mémoire. Un tampon circulaire de taille fixe qui est alloué une fois au moment de l'initialisation est bien mieux adapté à ce problème.
David Hammen
2
@DavidHammen: Peut-être, mais 1) La bibliothèque standard n'a pas de "tampon circulaire de taille fixe" dans sa boîte à outils. 2) Si vous avez vraiment besoin d'une telle optimisation, vous pouvez faire des trucs d'allocation pour minimiser les réallocations deque. C'est-à-dire, stocker et réutiliser les allocations comme demandé. dequeSemble donc une solution parfaitement adéquate au problème.
Nicol Bolas
4

Les réponses FIR et SMA que vous avez obtenues sont bonnes dans votre cas, mais je voudrais profiter de l'occasion pour proposer une approche plus générique.

Ce que vous avez ici est un flux de données: au lieu de structurer votre programme en 3 grandes étapes (obtenir des données, calculer, résultat de sortie) qui nécessitent de charger toutes les données en mémoire à la fois, vous pouvez plutôt le structurer comme un pipeline .

Un pipeline commence par un flux, le transforme et le pousse vers un puits.

Dans votre cas, le pipeline ressemble à:

  1. Lire les éléments du disque, émettre les éléments un par un
  2. Recevez les éléments un par un, pour chaque élément reçu, émettez les 5 derniers reçus (là où votre tampon circulaire entre)
  3. Recevez les éléments 5 à la fois, pour chaque groupe, calculez le résultat
  4. Recevez le résultat, écrivez-le sur le disque

C ++ a tendance à utiliser des itérateurs plutôt que des flux, mais pour être honnête, les flux sont plus faciles à modéliser (il existe une proposition de plages qui seraient similaires aux flux):

template <typename T>
class Stream {
public:
    virtual boost::optional<T> next() = 0;
    virtual ~Stream() {}
};

class ReaderStream: public Stream<Item> {
public:
    boost::optional<Item> next() override final;

private:
    std::ifstream file;
};

class WindowStream: public Stream<Window> {
public:
    boost::optional<Window> next() override final;

private:
    Window window;
    Stream<Item>& items;
};

class ResultStream: public Stream<Result> {
public:
    boost::optional<Result> next() override final;

private:
    Stream<Window>& windows;
};

Et puis, le pipeline ressemble à:

ReaderStream itemStream("input.txt");
WindowStream windowStream(itemsStream, 5);
ResultStream resultStream(windowStream);
std::ofstream results("output.txt", std::ios::binary);

while (boost::optional<Result> result = resultStream.next()) {
    results << *result << "\n";
}

Les flux ne sont pas toujours applicables (ils ne fonctionnent pas lorsque vous avez besoin d'un accès aléatoire aux données), mais lorsqu'ils le sont, ils basculent: en fonctionnant sur une très petite quantité de mémoire, vous gardez le tout dans le cache du processeur.


Sur une autre note: il semble que votre problème soit "embarrassant parallèlement", vous voudrez peut-être diviser votre gros fichier en morceaux (gardez à l'esprit, pour le traitement par des fenêtres de 5, que vous devez avoir 4 éléments communs à chaque limite) puis traitez les morceaux en parallèle.

Si le CPU est le goulot d'étranglement (et non les E / S), vous pouvez l'accélérer en lançant un processus par cœur que vous avez après avoir divisé les fichiers en quantités à peu près égales.

Matthieu M.
la source