3. stack dynamisch vergrößern

stack dynamisch vergrößern

  • T

    Hallo zusammen.
    Ich habe einen in C++ implementierten algorithmus der leider rekursiv läuft.
    Wenn ich die Funktion von VBA aus aufrufe gibt es einen stack-overflow.
    Den Code als Schleife zu implementieren fällt für mich aus da ich den Code nicht geschrieben habe und ihn auch nicht ganz verstehe.
    Weiß vielleicht jemand ob es möglich ist den Stack im Programmcode wachsen zu lassen? Finde dazu leider bei google nichts

    Danke schonmal im voraus

    0
  • A

    Öhm, wie viel Rekursionen macht der denn??? 😮 Meinste nicht das es dann eher eine Endlos-Rekursion ist?

    Aber die Stackgröße kannst du dem Compiler übergeben, also nicht zur Laufzeit.

    0
  • T

    Das kommt auf den C++ Compiler (bzw. den Linker) an. Die gängisten Compiler besitzen dafür eine Option, um den Anfangsstack als auch den Maximalwert zu setzen (der Stack wird vom Betriebssystem dann dynamisch vergrößert).
    Der Maximalwert beträgt meistens standardmäßig 1 MB (0x00100000).

    0
  • J

    Soweit ich weiß, gibt es einen dynamischen Stack nur unter den *nixen, unter Windows ist die Größe immer fest. Bei Visual-C++ kannst du dem Linker die Stackgröße mit /STACK:[Anzahl der Bytes] mitteilen...

    Grüße,

    Martin

    0
  • T

    achso ok.. danke schonmal im voraus

    0
  • P

    gib uns doch mal die wesentlichen Bestandteile des algos, vielleicht kann man den ja so umstricken, dass er iterativ verlaeuft oder anderweitig platzsparender ist.

    0
  • T

    äh.. danke für die info mein ich

    0
  • T

    hab mitlerweile einen anderen algorithmus im internet gefunden. Und die Rekursion war wirklich nicht zu lösen. Aber vielen dank für die Mühe

    0
  • P

    OT: *gruebel* gabs nichtmal irgendeinen Beweis, dass jede Rekusrion auch iterativ loesbar ist?

    0
  • C

    pumuckl schrieb:

    OT: *gruebel* gabs nichtmal irgendeinen Beweis, dass jede Rekusrion auch iterativ loesbar ist?

    Ja, die allgemeine Lösung läuft darauf hinaus, den Callstack der rekursiven Aufrufe in den Algorithmus zu integrieren 😉

    @Tom: Was war denn das für ein Algorithmus?

    0
  • A

    pumuckl schrieb:

    OT: *gruebel* gabs nichtmal irgendeinen Beweis, dass jede Rekusrion auch iterativ loesbar ist?

    Mag sein. Aber ich löse ehrlich gesagt rekursive Aufgaben besser rekursiv. Das geht Gehirnmäßig einfacher, als wenn man eine rekursive Aufgabe in iterativ umdenken muß.

    Aber der Beweis würde mich schon interessieren, keine Frage.

    0
  • ?

    was gibts da viel zu beweisen. bei jedem rekursiven funktionsaufruf werden lokale variablen und parameter auf den (call)stack gelegt. das macht man einfach selber, also (while)schleife und bei jedem durchgang die benötigten parameter auf einen eigenen stack.

    0
  • T

    @CStoll

    Das war ein Algorithmus zur Berechnung einer convexen Hülle für eine Menge von Messwerten. Das Problem war folgender Code:

    protected static void quicksort(int lo, int hi)
    {
        int i=lo, j=hi;
        Point q=p[(lo+hi)/2];
        while (i<=j)
        {
            while (p[i].isLess(q)) i++;
            while (q.isLess(p[j])) j--;
            if (i<=j) exchange(i++, j--);
        }
        if (lo<j) quicksort(lo, j);
        if (i<hi) quicksort(i, hi);
    }

    Mir ist für diesen Fall leider keine Lösung mit einer Schleife eingefallen.
    Und recursiver Code kommt nicht in Frage, weil die Anzahl der Messwerte nicht begrenzt ist. Können also auch viele Tausend sein.

    mfg Tom

    0
  • B

    Zum Glück ist Quicksort recht populär, da hat sich jemand schon Gedanken zu gemacht 🙂

    //Quicksort iterativ   (im Vergleich zur rekursiven Funktion ganz schön kompliziert)
procedure sortieren(var aa:array of real;von,bis:integer);
   var p,i,j:integer;
begin
  p:=bis;
  while p> 1 do Begin
    p:=p div 2;
    i:=von;
    repeat
      if aa[i+p]<aa[i] then BEgin
        tausche(aa[i],aa[i+p]);
        j:=i;
        while j-p>=von do BEGin
          if aa[j]<aa[j-p] then bEgin
             tausche(aa[j],aa[j-p]);
             j:=pred(j)
          eNd  else j:=0;
        END;
      ENd;
      i:=succ(i)
    until i+p>bis
  End;
end;

    Ist in Delphi und einfach von hier kopiert, vielleicht gehts ja.. Aber du musst wirklich viele Datensätze haben, ich hatte bei Quicksort noch nie einen Stack-Überlauf 😕

    0
  • H

    Es geht jetzt nicht ernsthaft ums sortieren ... 😮

    0
  • A

    Öhm, also ich hab jetzt eher an eine Baumstruktur gedacht, die ich durchlaufen muß oder so. Bei sowas kommt bei mir Rekursion höchstens zum Einsatz. Ach ja, zum Sortieren, benutze ich die Standardlib. 😉

    0
  • T

    Nein Stop. So wie ich das sehe ist das nicht der quicksort zum auf- oder absteigenden sortieren von Zahlen. Dieser Code hier sortiert glaub irgendwie anders. Der Sortiert irgendwie die Werte relativ zu irgend einem anderen Wert.

    0
  • P

    TomTom85 schrieb:

    Nein Stop. So wie ich das sehe ist das nicht der quicksort zum auf- oder absteigenden sortieren von Zahlen. Dieser Code hier sortiert glaub irgendwie anders. Der Sortiert irgendwie die Werte relativ zu irgend einem anderen Wert.

    Stimmt, das ist einfach quicksort im Sinne von Point::isLess() - was sich im Grunde aufs gleiche rauskommt. Im Klartext: Wo normalerweise ein "if (a < b)" steht, steht hier ein "if a.isLess(b)" - vom Sinn her ists genau das selbe wie Zahlen sortieren.

    0
Anmelden zum Antworten