Rekursion führt zu nicht genügend Speicher

Question

Ich habe einen RAM von 2 GB. Wir haben eine Anwendung, die Export/Import-Operationen durchführt. Wir haben eine rekursive Funktion, die eine lokale Variable vom Typ Set hat, die bei jeder Iteration weiter gefüllt wird. Dieses Set wächst weiter und an einem Punkt fehlt uns der Speicher.

Gibt es alternative Datenstrukturen, die den Speicher optimal nutzen können?

Hier ist der grobe Code

GetObjectsForExportImpl(long lExportOptions, __int64 numIdProject, XExportSets 
    &exportSets, long lClientId, CComPtr<IEPIPDServer> ptrIPDServer,FILE *fp) 
{ 
    XExportSets exportLocal; //Thats a structure containing the Set 
    QueryObjectsForExport(lExportOptions, numIdProject, exportLocal, 
     lClientId, ptrIPDServer); 
    SetIDs::iterator it = exportLocal.setShared.begin(); 

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

Answer 1

Eine alternative Struktur würde nicht viel helfen. Angenommen, Sie sind zu einer Klasse gewechselt, die die Hälfte des Speichers belegt. Du bringst den Untergang nur hinaus.

Eine Strukturgröße von 2 GB bedeutet normalerweise, dass Sie zu einer plattenbasierten Struktur, einer Datenbank oder einer Memory-Mapping-Hashtabelle wechseln müssen.

Answer 2

Behandeln Sie Daten Stück für Stück und nicht alle gleichzeitig.

Das heißt:

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

Sofern Sie in einem ganz bestimmten Fall sind, wo Sie müssen alle Daten in der Lage sein, einen Export zu tun (was sehr unwahrscheinlich ist)

Answer 3

Wenn Ihr Rekursion isst Bis zu 2 GB Speicher werden Sie wahrscheinlich Probleme mit jeder Art von In-Memory-Datenstruktur 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. Sie könnten für jede Rekursion einen neuen Datensatz einfügen, und der Datensatz könnte eine FK-Referenz auf den übergeordneten Datensatz in der Tabelle haben. Auf diese Weise können Sie die Rekursion auf und ab gehen, indem Sie den übergeordneten Referenzen in den Datensätzen folgen.

Answer 4

Für einen Moment Ihrer ursprünglichen Methodenaufruf vergleichen:

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

auf Ihre spätere rekursiven Aufruf:

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

Es sei denn, ist etwas Magie zwischen denen geschieht, die Sie einfach die Methode erneut aufrufen mit seinen eigenen Argumenten. Ich vermute, dass Sie "exportLocal" statt "exportSets" dort einfügen wollten, denn sonst, was war der Sinn der exportLocal.setShared.begin()? Sie werden nur eine neue exportLocal neu erstellen, es zu beginnen, rekursiv, etc.

Kurz gesagt, ich denke, das Problem ist ein Kodierungsfehler, kein Problem mit der Rekursion.

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

Answer 5

Entschuldigung - ich weiß nicht wirklich C++, aber ich kann möglicherweise ein bisschen helfen. Wenn Sie die Subskriptnotation für den Zugriff auf Elemente verwenden können und Sie Zeiger auf die übergeordneten Elemente haben, können Sie einen Stapel verwenden, um eine Tiefenüberquerung durchzuführen und die nicht unerheblichen Rekursionskosten zu vermeiden.Hier einige C# -Code, die Sie sollten übersetzen können:

Stack<int> childIndex = new Stack<int>(); 
childIndex.Push(0); 

TreeNode<Folder> workingFolder = GetNodeById(folderId); 
TreeNode<Folder> returnFolder = ShallowClone(workingFolder); 

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

     // increment count for this level 
     childIndex.Pop(); 
     childIndex.Push(idx + 1); 

     // replace current working folders and push new index 
     workingFolder = workingFolder.Children[idx]; 
     returnFolder = f; 
     childIndex.Push(0); 
    } else { 
     // no (more) children 
     workingFolder = (workingFolder.Parent == null ? workingFolder : workingFolder.Parent); 
     returnFolder = (returnFolder.Parent == null ? returnFolder : returnFolder.Parent); 
     childIndex.Pop(); 
    } 
} 

Answer 6

Ich glaube nicht, die Rekursion viel mit Ihrem Problem zu tun hat. Das Problem ist nur, dass die Daten, die Sie erstellen, groß sind. Der Wechsel zu einer iterativen Lösung wird nicht helfen. Wie bereits erwähnt wurde, schreibe die Ausgabe beim Durchlaufen, anstatt sie in einer speicherinternen Struktur zu speichern.

Sie können jedoch minimieren, was auf dem Stapel geht, indem Sie Zeiger in Ihren rekursiven Aufrufen und nicht ganze Strukturen übergeben.