Rekursiv Maximalwert aus Integerfeld auslesen



  • Hallo, ich hab mir ein rekursives Programm geschrieben, welchen den Maximalwert eines Integerfeldes ausgibt. Das funktioniert auch soweit, nur wenn ich mehr als 90000 Werte einlese, dann bricht das Programm einfach ab. Kann mir jemand sagen warum, oder was ich ändern muss damit es auch mit 1.000.000 Werten klappt?

    Hier erstmal der Code:

    int maximum(int *feld, int anz) // Hört bei 900000 Werten auf
    {
        int i=0;
        if(anz == 0) return(*feld); // Falls nur noch 1 Zahl existiert, das Maximum zurückgeben
        i = maximum(feld,anz-1);    // Die Funktion selber wieder aufrufen
        if(*(feld+anz) > i)         // Vergleicht letzten und aktuellen Wert
            return(*(feld+anz));    // Gibt den größeren der beiden Werte zurück
        else return(i);
    
        return (i);                 // Gibt zum Schluss den größten Wert zurück
    }
    

    Danke



  • Wird wohl an der Stackgröße liegen. Sprich: Dein Stack ist zu klein für 1000000 Rekursionen. Was du machen kannst ist:

    a) Den Stack vergößern. Das hängt aber von der Platform ab, welche wir noch nicht kennen.

    oder

    b) Keine rekursive Lösung machen 😉

    edit: kann man bei 0 Sekunden unterschied "zu langsam" sagen? *g*



  • Deine Rekursion geht zu tief, du zerschießt dir den Stack. Warum machst du das nicht iterativ?



  • rekursiv geht es auch mit beliebigen feldgrößen.

    //ungetestet
    int maximum(int *feld, int anz)
    {
      //feld aufteilen in 0 bis mitte-1 | mitte | mitte+1 bis anz-1
      int mitte=anz/2;
      //ergebnis wird das größte maximum  der teilfelder
      //erstmal die mitte nehmen
      int max=feld[mitte];
      //falls links  nicht leer ist, das dazunehmen
      if(mitte-1>0){
         int max2=maximum(feld,mitte-1);
          if(max2>max)
            max=max2;
      }
      //falls rechts  nicht leer ist, das auch noch dazunehmen
      if((anz-1)-(mitte+1)>0){
         int max2=maximum(feld+mitte+1,(anz-1)-(mitte+1));
          if(max2>max)
            max=max2;
      }
       return max;
    }
    


  • volkard schrieb:

    rekursiv geht es auch mit beliebigen feldgrößen.

    doch nicht wirlich 'beliebig', oder?
    🙂



  • Doch.



  • Bashar schrieb:

    Doch.

    um das zu erklären: ich teile das feld ins zwei hälfen von denen ich jeweils das maximum abfrage. pro reinindietiefegehung der iteration halbiere ich die feldgröße.

    bei feldgröße 2 muss ich einmal tiefgehen, habe dabei zwei abbiegungen. macht zusammen 2.

    bei feldgröße 4 muss ich 2-mal tiefgehen, habe dabei zwei abbiegungen und nach jeder abbiegung noch zwei. macht zusammen 4.

    bei feldgröße 8 muss ich 3-mal tiefgehen, habe dabei zwei abbiegungen und nach jeder abbiegung noch zwei, und nach jeder davon noch zwei. macht zusammen 8.

    bei feldgröße 16 muss ich 4-mal tiefgehen, ...
    bei feldgröße 32 muss ich 5-mal tiefgehen,
    bei feldgröße 64 muss ich 6-mal tiefgehen,
    bei feldgröße 128 muss ich 7-mal tiefgehen,

    allgemien gilt,

    bei feldgröße (2 hoch x) muss ich x-mal tiefgehen.

    nehmen wir mal ganz fetten speicher mit sauviel platz. sagen wir mal, du hast 64GB ram.
    das sind 2^37 Bytes. (nur "hoch 37", weil sich mit jedem hoch+1 die sache verdoppelt, das geht da ganz fix.). dann reicht es, 37-mal teiferzugehen.

    ja, das bestätigt Bashars aussage, denke ich.



  • ich hab' deinen (ungetesteten) code mal rauskopiert und die anzahl der 'tiefergehungen' zählen lassen:
    (links: feldgrösse, rechts: rekursionen)

    1 0
    2 0
    4 1
    8 2
    16 6
    32 14
    64 30
    128 62
    256 126
    512 254
    

    sieht doch nach mehr aus 😉



  • Oder man lässt es sich vom Compiler wegoptimieren 😃

    int maximum(int* feld, size_t anz, int max = 0)
    {
    	return anz == 0 ? max : maximum(feld + 1, anz - 1, std::max(*feld, max));
    }
    

    Mit VC++8 im Release-Modus mit einer "Rekursionstiefe" von 100 Mio. getestet.



  • @Pale dog: Den Stack interressiert aber nicht die Anzahl der rekursiven Aufrufe, sondern die Rekursionstiefe - und die liegt im Bereich O(log n).



  • CStoll schrieb:

    @Pale dog: Den Stack interressiert aber nicht die Anzahl der rekursiven Aufrufe, sondern die Rekursionstiefe - und die liegt im Bereich O(log n).

    wieso das? für jeden aufruf muss mindestens die rücksprungadresse auf dem stack gespichert werden.

    btw, wenn man einen algo hat, der immer halbiert und dann sich selbst wieder aufruft bekommt man bei einem startwert von 32 etwa sowas:

    32-16-8-4-2
    16-8-4-2
    8-4-2
    4-2
    2
    

    das sind dann 15 aufrufe (einer zuerst, 14 als rekursion)
    das deckt sich auch mit meinem 'messergebnis'
    🙂



  • pale dog schrieb:

    CStoll schrieb:

    @Pale dog: Den Stack interressiert aber nicht die Anzahl der rekursiven Aufrufe, sondern die Rekursionstiefe - und die liegt im Bereich O(log n).

    wieso das? für jeden aufruf muss mindestens die rücksprungadresse auf dem stack gespichert werden.

    Aber nur bis zur Rückkehr des Aufrufes. D.h. beim zweiten rekursiven Aufruf innerhalb der Funktion kann der Stack-Bereich wiederverwendet werden, den du beim ersten Aufruf genutzt hast.

    btw, wenn man einen algo hat, der immer halbiert und dann sich selbst wieder aufruft bekommt man bei einem startwert von 32 etwa sowas:

    32-16-8-4-2
    16-8-4-2
    8-4-2
    4-2
    2
    

    das sind dann 15 aufrufe (einer zuerst, 14 als rekursion)
    das deckt sich auch mit meinem 'messergebnis'
    🙂

    Ja, insegesamt hast du 15 Aufrufe, aber von denen sind maximal 5 zur selben Zeit "aktiv" und belegen kostbaren Stack-Speicher.
    (für die Laufzeit des Programms mag die Gesamtzahl der rekursiven Aufrufe möglicherweise ausschlaggebend sein, für den Speicherbedarf (des Stacks) zählt die Rekursionstiefe)



  • Es sind zwar 15 Aufrufe, aber die Tiefe ist trotzdem nur 5. Denn bevor die zweite Hälfte eines jeden Feldes betrachtet wird ist der rekursive Aufruf zur Betrachtung der ersten Hälfte längst zurückgekehrt.



  • alles klar. 👍
    entschuldigt meine blödheit 😉



  • pale dog schrieb:

    alles klar. 👍
    entschuldigt meine blödheit 😉

    Ich bin gestern auch drüber gestolpert 😉



  • Finde aber generell, dass man eher eine iterative Struktur wählen sollte, da dann die Stacks wegfallen -> schneller.



  • Hey,
    Ich möchte mich bei euch bedanken, meine Frage ist definitiv beantwortet!

    Die rekursive Programmierung war nur eine Hausaufgabe, ich habe nur mit einem Freund wetten wollen, dass mein Programm schneller ist als seins. Um die Zeit messen zu können brauchte ich halt ein paar Zahlen mehr und schwups war der Stack voll wie ich jetzt so schön ausführlich berichtet bekommen habe.

    Vielen Dank

    F.Saxen


Anmelden zum Antworten