Wie vermeide ich memory leaks bei rekursiver Programmierung?

*john 0

Am leichtesten geht das so

boost::shared_array<komplexeZahl>
FastFourier (int const N, komplexeZahl const& f) {
    // beim Rest brauchst Du keine Hilfe - oder?

    boost::shared_array<komplexeZahl> r (new komplexeZahl[N]);

    return r;
}

Das Problem ist dann aber, dass ich die dynamische Variable lösche, die ich mit return zurückgeben möchte.
also sowas:

delete[] Coeff;
return Coeff;

geht doch dann nicht.

Nexus

Du müsstest den Speicher, den du hier

Coeff=new komplexeZahl[N];

angefordert hast, wieder freigeben. Ich bin mir jetzt nicht sicher, was U und G bei dir sind (du hast geschrieben auch Felder), aber bevor du sie per Zuweisungsoperator überschreibst, solltest du sie löschen (wenn ihre Elemente auch Zeiger sind, diese auch freigeben).

delete[] G;
G=FastFourier(M,g)
delete[] U;
U=FastFourier(M,u)

Aber du musst auch schauen, dass du den zurückgegebenen Wert auch immer schön löschst (nach der Rückgabe, wenn er nicht mehr benötigt wird). Ich würd dir sowieso zu std::vector oder anderen Containern raten.

drakon schrieb:

Du kannst den Speicher einfach vor dem return wieder freigeben.

Nein, kann er nicht, er gibt ja den auf dem Heap angelegten Zeiger Coeff zurück.

Kann mir nicht vorstellen, dass man das nicht einfacher Designen kann. Braucht man für Fast Fourier wirklich ständig nene Speicher? Wäre dann ja nicht sehr fast.

drakon

Nexus schrieb:

drakon schrieb:

Du kannst den Speicher einfach vor dem return wieder freigeben.

Nein, kann er nicht, er gibt ja den auf dem Heap angelegten Zeiger Coeff zurück.

Jop. Stimmt, habe ich übersehen. Würde daher auch eher zu einem std::vector raten.

Vielen Dank, für eure Antworten!

*john 0

martin l schrieb:

Das Problem ist dann aber, dass ich die dynamische Variable lösche, die ich mit return zurückgeben möchte.

Deshalb sollst Du auch ein Shared Array verwenden, oder Du entwirfst die Funktion grundsätzlich anders.

camper

~john schrieb:

oder Du entwirfst die Funktion grundsätzlich anders.

Das wäre auf jeden Fall bedenkenswert. Funktionsimplementationen, die mal dort allokierten Speicher zurückgeben oder auch mal nicht, sind grundsätzlich zu hinterfragen.
In diesem speziellen Fall fällt z.B. auf, dass die Zahl der insgesamt benötigten Zahlen bereits vor der ersten Rekursion feststeht. Man könnte also den gesamten benötigten Speicher im voraus allokieren und die Funktionen auf diesem Speicher arbeiten lassen.

Ok der Beitrag ist schon ne Weile her.
Ich bin aber gerade wieder über ein ähnliches Problem gestolpert.
Ich denke, wenn man das Feld in eine Klasse packt, dann kann das Feld zurückgegeben werden und beim beenden der Funktion wird dann der Destruktor des Objekts noch aufgerufen.
Dort kann man dann den Speicher nach return wieder freigeben.

Und da die FFT ja eh nur mit Feldgrößen der Potenz von 2 arbeitet, könnte man zur Not auch so 10-15 Funktionen mit festen Arraygrenzen schreiben, was natürlich ziemlich unelegant wäre. Aber die FFT war ja auch nur ein Beispiel für eine typische schnelle Rekursion.

asc

martin l schrieb:

Ok der Beitrag ist schon ne Weile her.

Und sollte daher ruhen. Im Zweifel lieber einen neuen Thread öffnen.

martin l schrieb:

...
Ich denke, wenn man das Feld in eine Klasse packt, dann kann das Feld zurückgegeben werden und beim beenden der Funktion wird dann der Destruktor des Objekts noch aufgerufen.
Dort kann man dann den Speicher nach return wieder freigeben.

Wenn du ein Array in eine Klasse kapselst (nehmen wir für ein Beispiel mal die schon existierende TR1 Klasse std::tr1::array), arbeitest du mit einer Kopie (sofern diese nicht wegoptimiert wird).

// Ungetestet
template<int N>
std::tr1::array<int, N>
Foo() {
    std::tr1::array<int, N> r;
    // ...
    return r; // Hier wird eine Kopie (sofern keine Compileroptimierung
              // möglich ist) zurückgegeben.
}

int main()
{
    std::tr1::array<int, 3> a = Foo<3>();
}

volkard

~john schrieb:

Am leichtesten geht das so

boost::shared_array<komplexeZahl>
FastFourier (int const N, komplexeZahl const& f) {
    // beim Rest brauchst Du keine Hilfe - oder?

    boost::shared_array<komplexeZahl> r (new komplexeZahl[N]);

    return r;
}

Schon, aber statt wieder zu boosteln, sollte man das Designproblem lösen, fürchte ich.

volkard

martin l schrieb:

Aber die FFT war ja auch nur ein Beispiel für eine typische schnelle Rekursion.

Die typische schnelle Rekursion arbeitet total inplace.

size_t const unterschwelleFuerRekursion=13;//gerne auch =1
void machwas(Foo* begin,Foo* end){
   size_t anzahl=end-begin;
   if(anzahl<=unterschwelleFuerRekursion){
      machsIterativ(begin,end);//gerne auch machNix(); bei uFR=1
   }
   else{
      Foo* mitte=begin+anzahl/2;
      vorbereitung(begin,mitte,end);
      machwas(begin,mitte);
      machwas(mitte,end);
      nachbereitung(begin,mitte,end);
   }
}