[c++] Variabel geschachtelte FOR-Schleifen

[Ineluki]

Ich bin gerade auf ein interessantes Problem gestossen ...

Nehmen wir an, ich habe eine Liste L beliebiger Laenge, die in jedem Eintrag vier Gleitkommawerte enthaellt: Min, Max, delta und value (eine Zaehlvariable).

Nun moechte ich daraus ineinandergeschachtelte Forschleifen machen, in der form:

Code:

for( L[0].value = L[0].min; L[0].value < L[0].max; L[0].value += L[0].delta)
  for( L[1].value = L[1].min; L[1].value < L[1].max; L[1].value += L[1].delta)
    for( L[2].value = L[2].min; L[2].value < L[2].max; L[2].value += L[2].delta)
      ...
        for( L[L.size()-1].value = L[L.size()-1].min; L[L.size()-1].value < L[L.size()-1].max; L[L.size()-1].value += L[L.size()-1].delta)
          { code }

Das Problem ist: Man kann soetwas nicht hardcoden, da man nicht weiss, wie lang die liste ist, denn diese haengt unter Umstaenden vom Userinput ab. Und man kann auch keine Forschleife ueber Forschleifen laufen lassen, da diese ja ineinander geschachtelt werden muessen.

Das einzige, was mir zur Loesung einfaellt, waere eine Rekursion anzuwenden und in jedem Funktionsaufruf eine For-Schleife zu realisieren. Allerdings waere das in meinem Code etwas problematisch ... und auch vom Stack her sehr verschwenderisch.

Ideen, Vorschlaege ?

[uncreative]

Ich könnte mich auch komplett irren aber wäre das nicht in etwa das hier?:

Code:

for(int i = 0; i<L.size();i++)
{
    for(L[i].value = L[i].min; L[i].value<L[i].max; L[i].value += L[i].delta)
    {code;}
}

Immerhin iterierst du doch für jeden wert in L immer in gleicherweise.
Naja ich hoffe das ist es.

[Ineluki]

Ich könnte mich auch komplett irren aber wäre das nicht in etwa das hier?:

Code:

for(int i = 0; i<L.size();i++)
{
    for(L[i].value = L[i].min; L[i].value<L[i].max; L[i].value += L[i].delta)
    {code;}
}

Immerhin iterierst du doch für jeden wert in L immer in gleicherweise.
Naja ich hoffe das ist es.

...

Nein, das ist es nicht. Ausgerollt ergibt dein Code folgendes:

Code:

N = L.size();
for(L[0].value = L[0].min; 
     L[0].value<L[0].max; 
     L[0].value += L[0].delta) {code;}
for(L[1].value = L[1].min; 
     L[1].value<L[1].max; 
     L[1].value += L[1].delta) {code;}
...
for(L[N].value = L[N].min; 
     L[N].value<L[N].max; 
     L[N].value += L[N].delta) {code;}

Das ist von Komplexitaet M*N, wobei M die durchschnittliche Laenge der einzelnen Schleifen ist.

Bei mir saehe der code anders aus.

Code:

N = L.size();
for(L[0].value = L[0].min; 
  L[0].value<L[0].max; 
  L[0].value += L[0].delta) {
for(L[1].value = L[1].min; 
  L[1].value<L[1].max; 
  L[1].value += L[1].delta) {
...
for(L[N].value = L[N].min; 
  L[N].value<L[N].max; 
  L[N].value += L[N].delta) {code;} ... } }

Das ist Komplexitaet M^N

[Desmulator]

Code:

int depth = 0;
while(depth != -1){
    L[depth].value += L[depth].delta;
    if(L[depth].value > L[depth].max) { depth--; }
    if(depth = L.size()-1) { code. }
    else { depth++ };
}

Ich weiß nicht obs geht, aber vielleicht ist es ja ein Gedanklicher anstoß.

Vor dem Edit:
Da du nicht endlich arbeitest wirst du wohl um Rekursion nicht drum rum kommen.

Aber ein andere Gedanke, vielleicht kannst du ja eine weiteres Array einbauen, welches die durchläufe der jeweiligen Tiefe speichert. Nun brauchst du noch eine weitere Variable die die Tiefe angibt. Du durchläufst die Schleife und springst dann in der Tiefe ein weiter, schließlich, nach Vollendung der letzten Schleife wird die Tiefenzeiger wieder um eins gesenkt, dann musst du noch an der richtigen Stelle wieder einsetzen. Weiß nicht ob das so irgendwie machbar ist.

Aber mal eine andere Frage, was ist den der Sinn bzw. die Zweckmäsigkeit der Schleifenverschachtelung? Wie das momentan aussieht würdest du einfach nur immer wieder die Schleifen durchlaufen ohne, dass dabei etwas anderes raus kommen würde, bzw. bis auf das der Code X mal ausgeführt wird. Da könntest du es allerdings berechnen, wie oft er sich das reinziehen soll. Was ich nicht weiß ist, wenn du jetzt auf die Variablen zugreifen willst, dann bin ich auch irgendwie ratlos. Rekursion.
Kannst ja mit Assembler arbeiten und den Stack selber verwalten. ^^

[Manni]

Code:

int depth = 0;
while(depth != -1){
    L[depth].value += L[depth].delta;
    if(L[depth].value > L[depth].max) { depth--; }
    if(depth = L.size()-1) { code. }
    else { depth++ };
}

Ich weiß nicht obs geht, aber vielleicht ist es ja ein Gedanklicher anstoß.

...

Das könnte funktionieren, allerdings fehlt noch ein Zurücksetzen von L[depth].value bei depth--.

EDIT: Ansonsten könntest du auch noch versuchen, aus den for-Schleifen Listen (oder in Python Generatoren) zu machen. Je nach Anwendung lässt sich vielleicht was damit anfangen....

[Desmulator]

Das könnte funktionieren, allerdings fehlt noch ein Zurücksetzen von L[depth].value bei depth--.

...

Code:

int depth = 0;
while(depth != -1){
    L[depth].value += L[depth].delta;
    if(L[depth].value > L[depth].max) { L[depth].value = L[depth].min; depth--; }
    if(depth = L.size()-1) { code. }
    else { depth++ };
}

[Ineluki]

Code:

int depth = 0;
while(depth != -1){
    L[depth].value += L[depth].delta;
    if(L[depth].value > L[depth].max) { L[depth].value = L[depth].min; depth--; }
    if(depth = L.size()-1) { code. }
    else { depth++ };
}

...

Wow .. das ist wirklich eine klevere Loesung ^__^

Nun ja .. ich habs mittlerweile umstrukturiert und doch mit Rekursion gemacht.
Allerdings finde ich das Thema interessant genug, um es hier weiter zu verfolgen. Ist ja ohnehin nicht allzuviel los.

Worum es geht ...
In einem Inputfile bastel ich ueber Schluesselwoerter eine Modellfunktion zusammen, die von meheren nichtlinearen (P0 bis Pn) und meheren linearen (A0 bis Am) Parametern abhaengt.

F = A[0] * f[0](P0, P1, ..., Pn) + A[1] * f1(P0, P1, ..., Pn) + ... A[m-1] * f[m-1](P0, P1, ..., Pn) + A[m]

Die nichtlinearen P Parameter (effektiv Achsen in hochdimensionalen Raeumen) werden dann nach Benutzervorgabe mit den Schleifen abgerastert. An jedem Punkt wird ueber die restlichen linearen Parameter A0 bis Am eine multilineare Optimierung durchgefuehrt und die Regressionsguete R2 bestimmt. Danach wird, um moeglichst das Globale Optimum im Parameterraum P zu finden vom Rasterpunkt mit bester Regressionsguete eine nichtlineare Optimierung ueber alle Parameter P0 bis Pn und A0 bis Am gemacht.

Da die Anzahl der Parameter ( m und n ) vom Inputfile abhaengt, weiss man vorher nicht, wieviele Schleifen ineinander zu schachteln sind. Zudem sind die Funktionen f als Klassen (mit einer vrtuellen Methode) vom selben Basistyp abgeleitet um maximale Erweiterbarkeit zu gewaehrleisten. Nicht alle Funktionen f brauchen alle Parameter P0 bis Pn (die meisten haben nur 1 oder 2 Parameter). Das ganze laeuft dann ueber einen Levenberg-Marquardt-Solver zur Ermittlung minimaler Fehlerquadrate (Regression) bezueglich einiger Messwerte. Die Funktionen f sind selbst hochkomplexe Berechnungen aus quantenchemischen Rechnungen.

Wie man sieht, wird der Code nicht einfach haeufig ausgefuehrt, sondern die Werte der Parameter haben schon eine Bewandnis.

[Kyuu]

Ich habe mir erlaubt Desmulators iterative Lösung umzuschreiben, denn im Moment ist sie vor lauter Tipp- und Logikfehlern weit davon entfernt, mit Inelukis for-Schleifen-Ansatz äquivalent zu sein. ^^

Code:

// wir gehen davon aus, dass die Liste mindestens ein Element enthält
L[0].value = L[0].min;
int depth = 0;
while (true)
{
    if (L[depth].value < L[depth].max)
    {
        if (depth == L.size()-1)
        {
            // code...
        }
        else
        {
            depth++;
            L[depth].value = L[depth].min;
            continue;
        }
    }
    else if (--depth == -1)
    {
        break;
    }

    L[depth].value += L[depth].delta;
}

Falls der Wunsch besteht, werde ich die korrigierten Fehler angeben.

[Desmulator]

Falls der Wunsch besteht, werde ich die korrigierten Fehler angeben.

...

Mich würdes echt mal interessieren.

[Kyuu]

Mich würdes echt mal interessieren.

...

1. Das Inverse des Ausdrucks "a < b" ist nicht "a > b", sondern "a >= b". (Danke an DFYX für die Berichtigung.) Falls bei dir nämlich a und b gleich sind, wird der auskommentierte Code ausgeführt, in Lukis Ansatz wäre es nicht der Fall.

2. Die Zuweisung im Bedingungsblock der zweiten Verzweigung ist der erste Grund für eine unendlichen Schleife, da der Variable 'depth' immer ein konstanter Wert zugewiesen wird, der ungleich '-1' und für die Abbruchbedingung der Schleife genau dieser Wert ausschlaggebend ist. Die Zuweisung sieht zwar cool aus, ist aber in den meisten Fällen ein Programmierfehler, so wie in diesem Fall.

3. Die 'value's der Listenelemente werden zwar nach Mannis Bemerkung beim Rücksprung zurückgesetzt, es fehlt aber eine Initialisierung dieser vor der ersten Benutzung nach dem Eintreten in die Schleife. Kein gravierender, aber für einen Vergleich beider Ansätze dennoch wichtiger Punkt.

4. Dieser Fehler ist etwas subtiler, denn um die Fehlerstelle zu erkennen, muss man das Programm in Gedanken ablaufen lassen. Es reicht schon der einfachste Fall von einer Liste mit einem Element und dessen 'delta' größer als die Differenz seiner 'max' und 'min'. Beim Eintritt in die Schleife ist 'depth' gleich 0. Nun wird 'value' um 'delta' erhöht und ist damit größer als 'max', d.h. der if-Block der ersten Verzweigung wird ausgeführt und führt damit - neben einer, an dieser Stelle nebenläufigen Änderung an 'value' - zu einer Verringerung von 'depth' um eins. Jetzt müsste man annehmen, dass ein 'depth'-Wert von -1 zum Abbruch der Schleife führen muss, aber weit gefehlt: Die nächste Verzweigung testet, ob 'depth' dem letzten Element in der Liste entspricht (was nicht der Fall ist, denn -1 ist ungleich 0) und falls nicht, wird 'depth' um eins erhöht. Nun ist 'depth' wieder gleich 0 und der Schleifenblock zu Ende, was zum Test der Abbruchbedingung der Schleife führt: Ist 'depth' gleich -1? Oder: Ist 0 gleich -1? Nein. Kein Abbruch, die Schleife wird mit den gleichen Werten fortgesetzt, die schon beim Eintritt gegeben waren. Der zweite Grund für eine unendliche Schleife. Funktioniert genauso mit allen anderen 'delta'-Werten und Listengrößen.

Editierter Punkt 5: Bei Lukis for-Schleifen-Ansatz gibt es den Test, ob 'value' kleiner 'max' ist, schon vor dem Erhöhen von 'value' um 'delta'. Bei dir ist das nicht der Fall, so dass du immer wieder Ausführungen des auskommentierten Codes überspringst und alleine das schon keine Äquivalenz zulässt.

Die korrigierten Fehlerstellen und eine Umstrukturierung, um einige Stellen zu beseitigen, die ich als unglücklich gelöst empfand und die auch teilweise mit den obigen Fehlern zusammenhingen, ergibt dann den von mir geposteten Code.

Da die Idee hinter deiner Lösung ok war, fand ich es schade, dass es bei der Umsetzung so happerte, was mich schließlich zur Korrektur reizte.

[DFYX]

1. Die äquivalente Umformung des Ausdrucks "a < b" ist nicht wie auf den ersten Blick vermutet "b > a", sondern "b >= a".

...

Öh, nein. a < b und b > a sind äquivalent. Was du vielleicht meinst, ist das Inverse der Ausdrücke. Das wäre a >= b bzw. b <= a.

[Kyuu]

Öh, nein. a < b und b > a sind äquivalent. Was du vielleicht meinst, ist das Inverse der Ausdrücke. Das wäre a >= b bzw. b <= a.

...

Ah, perfekt erkannt, danke. Editiert.