Professioneller Weg, um ein großes Problem zu produzieren, ohne große Arrays zu füllen: C ++, freier Speicher aus einem Teil eines Arrays

20

Ich entwickle eine Physiksimulation und da ich in der Programmierung noch nicht so weit bin, habe ich immer wieder Probleme beim Erstellen großer Programme (hauptsächlich Speicherprobleme). Ich kenne mich mit dynamischer Speicherzuweisung und -löschung (neu / löschen usw.) aus, benötige jedoch einen besseren Ansatz für die Strukturierung des Programms.

Angenommen, ich simuliere ein Experiment, das einige Tage lang ausgeführt wird, mit einer sehr hohen Abtastrate. Ich müsste eine Milliarde Proben simulieren und überfliegen.

Als supervereinfachte Version sagen wir, ein Programm nimmt die Spannungen V [i] und summiert sie in fünf:

dh NewV [0] = V [0] + V [1] + V [2] + V [3] + V [4]

dann ist NewV [1] = V [1] + V [2] + V [3] + V [4] + V [5]

dann ist NewV [2] = V [2] + V [3] + V [4] + V [5] + V [6] ... und das geht für eine Milliarde Abtastungen weiter.

Am Ende hätte ich V [0], V [1], ..., V [1000000000], wenn stattdessen die einzigen, die ich für den nächsten Schritt speichern müsste, die letzten 5 V [i] wären. s.

Wie würde ich einen Teil des Arrays löschen / freigeben, damit der Speicher wieder verwendet werden kann (sagen Sie V [0] nach dem ersten Teil des Beispiels, in dem er nicht mehr benötigt wird)? Gibt es Alternativen zur Strukturierung eines solchen Programms?

Ich habe von malloc / free gehört, aber gehört, dass sie nicht in C ++ verwendet werden sollten und dass es bessere Alternativen gibt.

Vielen Dank!

tldr; Was mache ich mit Teilen von Arrays (einzelnen Elementen), die nicht mehr benötigt werden und sehr viel Speicher beanspruchen?

Schlagzeuger
quelle
2
Sie können die Zuordnung eines Teils eines Arrays nicht aufheben. Sie könnten es einem kleineren Array woanders zuweisen, aber dies kann sich als teuer erweisen. Möglicherweise können Sie stattdessen eine andere Datenstruktur verwenden, z. B. eine verknüpfte Liste. Möglicherweise können Sie die Schritte auch in Veinem neuen Array speichern . Grundsätzlich denke ich jedoch, dass Ihr Problem entweder in Ihren Algorithmen oder in Ihren Datenstrukturen liegt, und da wir keine Details haben, ist es schwierig zu wissen, wie man es effizient macht.
Vincent Savard
4
Randnotiz: Mit dieser Wiederholungsrelation können SMAs beliebiger Länge besonders schnell berechnet werden: NewV [n] = NewV [n-1] - V [n-1] + V [n + 4] (Ihre Notation). Beachten Sie jedoch, dass dies keine besonders nützlichen Filter sind. Ihr Frequenzgang ist ein sinc, der so gut wie nie das ist, was Sie wollen (wirklich hohe Nebenkeulen).
Steve Cox
2
SMA = einfacher gleitender Durchschnitt für alle, die sich fragen.
Charles
3
@SteveCox, so wie er es geschrieben hat, hat er einen FIR-Filter. Ihre Wiederholung ist das entsprechende IIR-Formular. In beiden Fällen erhalten Sie einen Umlaufpuffer der letzten N Messwerte.
John R. Strohm
@ JohnR.Strohm die Impulsantwort ist identisch und endlich
Steve Cox

Antworten:

58

Was Sie als "Glätten um fünf" bezeichnen, ist ein digitales Filter mit endlicher Impulsantwort (FIR). Solche Filter werden mit kreisförmigen Puffern implementiert. Sie behalten nur die letzten N Werte bei, Sie behalten einen Index in dem Puffer, der Ihnen sagt, wo sich der älteste Wert befindet, Sie überschreiben den aktuell ältesten Wert bei jedem Schritt mit dem neuesten und Sie schrittweise den Index jedes Mal.

Sie speichern Ihre gesammelten Daten, die Sie zerstören werden, auf der Festplatte.

Abhängig von Ihrer Umgebung ist dies möglicherweise einer der Orte, an denen Sie besser auf erfahrene Hilfe angewiesen sind. An einer Universität schreiben Sie im Fachbereich Informatik eine Notiz an die Pinnwand und bieten Studentenlöhne (oder sogar Beratungsgebühren für Studenten) für einige Stunden Arbeit an, damit Sie Ihre Daten besser verarbeiten können. Oder bieten Sie Undergraduate Research Opportunity-Punkte an? Oder so.

John R. Strohm
quelle
6
Ein kreisförmiger Puffer scheint in der Tat das zu sein, wonach ich suche! Ich habe jetzt die Boost-C ++ - Bibliotheken installiert und die Datei boost / circular_buffer.hpp hinzugefügt und arbeite wie erwartet. Vielen Dank, @ John
Drummermean
2
Nur sehr kurze FIR-Filter werden direkt in Software implementiert, SMAs fast nie.
Steve Cox
@SteveCox: Die von Ihnen verwendete Formel für Fensterränder ist für Ganzzahl- und Festkommafilter recht effektiv, für Gleitkommazahlen, bei denen Operationen nicht kommutativ sind, ist sie jedoch falsch.
Ben Voigt
@BenVoigt Ich denke, Sie wollten auf meinen anderen Kommentar antworten, aber ja, diese Form führt einen Grenzzyklus um eine Quantisierung ein, der sehr knifflig sein kann. Zum Glück ist dieser bestimmte Grenzzyklus jedoch stabil.
Steve Cox
Für diese Verwendung benötigen Sie keinen Boost für einen Umlaufpuffer. Uu Sie benötigen viel mehr Speicher als benötigt.
GameDeveloper
13

Jedes Problem kann durch Hinzufügen einer zusätzlichen Indirektionsebene gelöst werden. Also mach das.

Sie können einen Teil eines Arrays in C ++ nicht löschen. Sie können jedoch ein neues Array erstellen, das nur die Daten enthält, die Sie behalten möchten, und dann das alte Array löschen. So können Sie eine Datenstruktur erstellen, mit der Sie Elemente, die Sie nicht möchten, von vorne "entfernen" können. Eigentlich wird ein neues Array erstellt, und die nicht entfernten Elemente werden in das neue Array kopiert. Anschließend werden die alten Elemente gelöscht.

Oder du könntest einfach nutzen std::deque, was das schon effektiv kann. deque, oder "Double-Ended Queue", ist eine Datenstruktur, die für Fälle vorgesehen ist, in denen Sie Elemente von einem Ende löschen, während Sie Elemente zum anderen hinzufügen.

Nicol Bolas
quelle
30
Jedes Problem kann durch Hinzufügen einer zusätzlichen Indirektionsebene gelöst werden ... mit Ausnahme vieler Indirektionsebenen.
YSC
17
@YSC: und Rechtschreibung :)
Leichtigkeit Rennen mit Monica
1
Für dieses besondere Problem std::dequeist der Weg zu gehen
Davidbak
7
@davidbak - Was? Es ist nicht erforderlich, ständig Speicher zuzuweisen und freizugeben. Ein Ringpuffer mit fester Größe, der zur Initialisierungszeit einmal zugewiesen wird, ist für dieses Problem wesentlich besser geeignet.
David Hammen
2
@DavidHammen: Vielleicht, aber 1) Die Standardbibliothek hat keinen "Zirkelpuffer mit fester Größe" in ihrem Toolkit. 2) Wenn Sie eine solche Optimierung wirklich benötigen, können Sie einige Zuweisungsaufgaben ausführen, um die Neuzuweisungen zu minimieren deque. Das heißt, Speichern und Wiederverwenden von Zuordnungen nach Bedarf. Also dequescheint eine vollkommen adäquate Lösung für das Problem zu sein.
Nicol Bolas
4

Die FIR- und SMA-Antworten, die Sie erhalten haben, sind in Ihrem Fall gut, aber ich möchte die Gelegenheit nutzen, um einen allgemeineren Ansatz voranzutreiben.

Was Sie hier sehen , ist ein Strom von Daten: statt Strukturierung Ihres Programms in drei großen Schritten (get Daten, Berechnung, Ausgabeergebnis) , die auf einmal alle Daten im Speicher erfordern Laden Sie stattdessen es als eine Struktur kann Pipeline .

Eine Pipeline beginnt mit einem Stream, wandelt ihn um und schiebt ihn in eine Senke.

In Ihrem Fall sieht die Pipeline folgendermaßen aus:

  1. Lesen Sie die Elemente von der Festplatte und geben Sie sie einzeln aus
  2. Einzelne empfangene Artikel, für jeden empfangenen Artikel werden die letzten 5 gesendet
  3. Erhalte 5 Items gleichzeitig, für jede Gruppe berechne das Ergebnis
  4. Erhalten Sie das Ergebnis, schreiben Sie es auf die Festplatte

C ++ verwendet eher Iteratoren als Streams, doch um ehrlich zu sein, lassen sich Streams einfacher modellieren (es gibt einen Vorschlag für Bereiche, die Streams ähneln würden):

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;
};

Und dann sieht die Pipeline so aus:

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";
}

Streams sind nicht immer anwendbar (sie funktionieren nicht, wenn Sie zufälligen Zugriff auf die Daten benötigen), aber wenn sie es sind, rocken sie: Wenn Sie auf einer sehr kleinen Speicherkapazität arbeiten, behalten Sie alles im CPU-Cache.


Ein weiterer Hinweis: Es scheint, dass Ihr Problem "peinlich parallel" ist. Sie möchten Ihre große Datei möglicherweise in Blöcke aufteilen. und dann die Stücke parallel verarbeiten.

Wenn CPU der Engpass ist (und nicht E / A), können Sie ihn beschleunigen, indem Sie einen Prozess pro Kern starten, den Sie haben, nachdem Sie die Dateien in ungefähr gleichen Mengen aufgeteilt haben.

Matthieu M.
quelle