Rekursion führt zu Speicherüberlauf

Question

Ich habe einen RAM von 2 GB. Wir haben eine Anwendung, die Export- / Importoperationen durchführt. Wir haben eine rekursive Funktion, die eine lokale Variable vom Typ Set hat, die bei jeder Iteration kontinuierlich gefüllt wird. Dieses Set wächst ständig und irgendwann haben wir keinen Speicher mehr.

Gibt es eine alternative Datenstruktur, die den Speicher optimal nutzen kann?

Hier ist der grobe Code

GetObjectsForExportImpl(long lExportOptions, __int64 numIdProject, XExportSets
     &exportSets, long lClientId, CComPtr ptrIPDServer,FILE *fp)
{
    XExportSets exportLocal;   //Das ist eine Struktur, die das Set enthält
    QueryObjectsForExport(lExportOptions, numIdProject, exportLocal,
         lClientId, ptrIPDServer);
    SetIDs::iterator it = exportLocal.setShared.begin();

    for (; it != exportLocal.setShared.end(); ++it)
    {
         //rekursiver Aufruf
         pExportObject->GetObjectsForExportImpl(lExportOptions,
             numIdProject, exportSets, lClientId, ptrIPDServer,fp);
    }
}

Answer 1

Eine alternative Struktur würde nicht viel helfen. Angenommen, Sie wechseln zu einer Klasse, die nur den halben Speicher verwendet. Sie verzögern trotzdem nur das Unvermeidliche.

Bei einer Strukturgröße von 2 GB müssen Sie in der Regel zu einer struktur auf Festplatte, einer Datenbank oder einer im Speicher abgebildeten Hashtabelle wechseln.

Answer 2

Behandeln Sie Datenstücke Stück für Stück anstatt alle auf einmal.

Das heißt:

while (not end-of-file) {
   data = read_some_information();
   export_some_information(data);
}

Es sei denn, Sie befinden sich in einem sehr spezifischen Fall, in dem Sie alle Daten benötigen, um einen Export durchführen zu können (was äußerst unwahrscheinlich ist)

Answer 3

Für einen Moment, vergleichen Sie Ihren ursprünglichen Methodenaufruf:

GetObjectsForExportImpl(
   long                  lExportOptions, 
   __int64               numIdProject, 
   XExportSets           &exportSets, 
   long                  lClientId, 
   CComPtr ptrIPDServer,
   FILE                  *fp
   )

mit Ihrem nachfolgenden rekursiven Aufruf:

hr = pExportObject->GetObjectsForExportImpl(
                         lExportOptions,
                         numIdProject,
                         exportSets,
                         lClientId,
                         ptrIPDServer,
                         fp);

Es sei denn, zwischen diesen beiden Aufrufen geschieht etwas Magisches, rufen Sie die Methode einfach mit dem eigenen Satz von Argumenten erneut auf. Ich vermute, dass Sie stattdessen 'exportLocal' anstelle von 'exportSets' verwenden wollten, weil sonst, was war der Sinn von exportLocal.setShared.begin()? Sie werden einfach weiterhin ein neues exportLocal erstellen, ihm sagen, dass es beginnen soll, sich wiederholen, usw.

Kurz gesagt, ich denke, das Problem liegt an einem Codierfehler, nicht an einem Problem mit der Rekursion.

Übrigens - können Sie sich eine Möglichkeit vorstellen, dies zu einer Schleife zu machen, anstatt einer Rekursion? Schleifen sind fast immer schneller, einfacher, leichter zu verstehen und schnell zu debuggen.

Answer 4

Entschuldigung - Ich kenne C++ nicht wirklich, aber ich kann vielleicht ein bisschen helfen. Wenn Sie mit Subskriptnotation auf Elemente zugreifen können und Zeiger auf die übergeordneten Elemente haben, können Sie einen Stapel verwenden, um eine Tiefensuche durchzuführen und die nicht unerheblichen Kosten der Rekursion zu vermeiden. Hier ist etwas C#-Code, den Sie übersetzen sollten:

Stack childIndex = new Stack();
childIndex.Push(0);

TreeNode workingFolder = GetNodeById(folderId);
TreeNode returnFolder = ShallowClone(workingFolder);

while (childIndex.Count > 0) {
    int idx = childIndex.Peek();
    if (idx < workingFolder.Children.Count) {
        visit(workingFolder.Children[idx]);

        // Zähler für diese Ebene erhöhen
        childIndex.Pop();
        childIndex.Push(idx + 1);

        // aktuelle Arbeitsordner ersetzen und neuen Index hinzufügen
        workingFolder = workingFolder.Children[idx];
        returnFolder = f;
        childIndex.Push(0);
    } else {
        // keine (weiteren) Kinder
        workingFolder = (workingFolder.Parent == null ? workingFolder : workingFolder.Parent);
        returnFolder = (returnFolder.Parent == null ? returnFolder : returnFolder.Parent);
        childIndex.Pop();
    }
}

Answer 5

Wenn Ihre Rekursion 2 GB Speicher verbraucht, werden Sie wahrscheinlich Probleme mit jeder Art von im Arbeitsspeicher befindlichen Datenstrukturen haben. Können Sie etwas von Ihrem Code posten, damit wir eine bessere Vorstellung davon bekommen, was Sie tun?

Eine Idee könnte sein, eine Datenbanktabelle zu verwenden, um das Set zu speichern, während Sie es erstellen. Für jede Rekursion könnte ein neuer Datensatz eingefügt werden, und der Datensatz könnte einen FK-Verweis auf den übergeordneten Datensatz in der Tabelle haben. Auf diese Weise können Sie die Rekursion auf- und absteigen, indem Sie den Elternverweisen in den Datensätzen folgen.