C++ Optimierungsdurchläufe ohne verschachtelte Schleifen?

T_55 · 18. September 2016

Hallo,

wenn eine Berechung von Werten mehrerer Variablen abhängt und man möchte alle Kobinationen der Werte durchlaufen lassen, dann habe ich bisher immer verschachtelte Schleifen benutzt. Zum Beispiel gibt es 3 integer Variablen mit Anfangs und Endwert sowie dem Stufenabstand. Also wenn alle von 1 bis 5 laufen sollen mit dem Stufenabstand 2 dann durchläuft jedes 1, 3, 5. In Kombination sollten es also es also 27 Durchläufe geben.

Optimal wäre, wenn man die zu nutzenden Variablen und damit dessen Anzahl flexibel wählen könnte und dann noch angibt in welchem Wertebereich mit welcher Stufengröße diese durchlaufen werden. Und ohne das man wie bei verschachtelten Schleifen alles vorher festlegen muss.

Geht das auch ohne verschachtelte Schleifen? Gibt es in c++ irgendwelche Lösungen, Algos, Libs etc, wo man sowas flexibler machen kann? Ich habe gesehen das es für NN Optimierungsalgos gibt, könnte man sowas in der Richtung einsetzten?
Mein Beispiel ist eher Bruteforce aber ich fände es auch nicht verkehrt, wenn für die Zukunft eine möglichen Lösung, gleich alles, also optional andere Optimierungsalgos möglich machen könnte. Aber vor allem möchte ich erstmal die unflexiblen Schleifen loswerden.

Grüße

wusu · 18. September 2016

Schau dir rekursive templates und parameter packs mal an. Ansonsten müsste man wissen, was du eigentlich machen willst, damit man dir effektiv helfen kann.

VikingGe · 18. September 2016

Ist die Anzahl der Variablen erst zur Laufzeit bekannt oder schon zur Compile-Zeit?
Fall 1: Nimm ein dynamisches Array (à la std::vector) und implementiere auf diesem eine Art Zähler.
Fall 2: Siehe Beitrag über mir.

Ansonsten wäre etwas Code zur Veranschaulichung wirklich super

T_55 · 19. September 2016

Statt der verschachtelten Schleifen wäre genial wenn man im Code einfach die gewünschten Variablen auswählt und startwert, stufe und ende definiert. Im Code unten, der so natürlich nur als unfertige Idee zu sehen ist, werden die Definierungen im Code vorgegeben, was im Prinzip auch per Konsole oder gui vorgegeben werden könnte. Mit jeder Kombinationsmöglichkeit wird dann zb eine Berechnung ausgeführt. Hier mal eine Idee, weiß allerdings nicht wie ich die Funktionen dazu bringe das zu tun was ich in die Kommentare geschrieben hab ;-)

Code:

void variablendefinition(int &Variable, int startwert, int stufe, int ende)
{
   // merkt sich irgendwie jede definition
}

int run_kombinationen()
{
    // weißt den entsprechenden variablen die werte der aktuellen kombination zu
    // liefert solange 1 zurück bis alle kombinationen durch sind.
}

int main()
{
   // vorhandene variablen
   int a;
   int b;
   int c;
   int d;
   int e;

   // ---------------------------------------------------------------
   // beispiel mit 3 variablen in kombination
   // definiere evt durch funktion die zu nutzenden variablen:
   variablendefinition(a, 2, 2, 8); // 2,4,6,8
   variablendefinition(b, 10, 5, 43); // 10,15,20,25,30,35,40
   variablendefinition(c, 1, 1, 5); // 1,2,3,4,5

   // führe alle kombinationen aus
   while(run_kombinationen() == 1)
   {
      // führe zb Berechnung durch
      berechnung();
   }
   // reset
   // ---------------------------------------------------------------

   // ---------------------------------------------------------------
   // beispiel mit 2 variablen in kombination
   // definiere evt durch funktion die zu nutzenden variablen:
   variablendefinition(d, 20, 20, 150); // 20,40,60,80,100,120,140
   variablendefinition(e, 0, 100, 937); // 0,100,200,300,400,500,600,700,800,900

   // führe alle kombinationen aus
   while(run_kombinationen() == 1)
   {
      // führe zb Berechnung durch
      berechnung();
   }
   // reset
   // ---------------------------------------------------------------

}

VikingGe · 19. September 2016

Ich poste einfach mal eine Lösungsidee und versuche dann, so gut das um diese Uhrzeit noch geht, diese zu erklären. Ich weiß auch nicht, wie gut du allgemein im Programmieren bist, ein blutiger Anfänger scheinst du aber auf jeden Fall nicht zu sein.

Der Code ist hier nicht getestet und gewinnt auch keinen Schönheitsvwettbewerb, aber so in der Art kann sollte man das machen können:

Code:

class CounterElement {
public:
  CounterElement(int min, int max, int step)
  : _min(min), _max(max), _step(step), _value(min) { }

  bool increment() {
    const int next = this->_value + this->_step;
    const bool overflow = next > this->_max;
    this->_value = overflow ? this->_min : next;
    return overflow;
  }
private:
  int _min;
  int _max;
  int _step;
  int _value;
};


class Counter {
public:
  explicit Counter(std::vector<CounterElement>&& e)
  : _digits(std::move(e)) { }
  
  template<typename Fn>
  void run(const Fn& fn) {
    do {
      fn(this->_digits);
    } while (!this->increment());
  }
private:
  std::vector<CounterElement> _digits;
  
  bool increment() {
    for (size_t i = 0; i < this->_digits.size(); i++) {
      if (!this->_digits[i].increment())
        return false;
    }
    return true;
  }
};

Das implementiert im Grunde für jede Kombination einen Zähler, wo jede "Ziffer" überlaufen kann, wobei dann die increment-Methode true liefert und anschließend die nächste Stelle inkrementiert wird. Sprich: An Stelle 0 hast du deine Zahl, die von 2 bis 10 gehen soll und immer um 2 erhöht wird - erreicht sie 12, wird sie stattdessen auf 2 gesetzt und die nächste Ziffer einen Schritt hochgezählt.

Damit erhält man a) alle Kombinationen, bis die letzte Ziffer selbst überläuft, und b) ist der Zähler danach auch sofort wieder im Ursprungszustand, sodass man ihn gleich noch einmal verwenden kann. Für jede Kombination wird eine Lambda-Funktion ausgeführt:

Code:

Counter counter({
  CounterElement(2, 8, 2),
  CounterElement(10, 43, 5),
  CounterElement(1, 5, 1),
});

counter.run([] (const std::vector<CounterElement>& elements) {
  for (size_t i = 0; i < elements.size(); i++)
    std::cout << elements[i].value() << " ";
  std::cout << std::endl;
});

Ausgabe sollte, wenn alles klappt, etwa so aussehen:

Code:

T_55 · 19. September 2016

Respekt, vielen Dank! Jetzt werd ich mich erstmal hinsetzen und versuchen jede Zeile zu verstehen und dabei OOP üben ;-)

Ich bekomme noch ein Fehler bei std::cout << elements.value() << " ";
error: const value_type has no member named value

Grüße

Balou72 · 19. September 2016

Also elements ist ein std::vector<CounterElement>.

Daher ist elements ein CounterElement.

Und das hat keine Methode value(). Die musst Du noch implementieren.

T_55 · 19. September 2016

OOP ist genau meine Schwachstelle da muss ich noch lernen. Ich hab noch nicht verstanden wo eigentlich die Ursprungsvariablen sind dessen Werte dann manipuliert werden bei jedem Durchlauf. Irgendwo muss doch eine Referenz dieser übegeben werden oder?

Fonce · 19. September 2016

Aber bitte angewöhnen at() für die zugriffe auf Container Elemente zu nutzen. Damit werden dann auch Bound Checks durchgeführt.

VikingGe · 20. September 2016

Warum, wenn die Größe als Zählervariable benutzt wird? Das macht meines Erachtens nur dann Sinn, wenn der Index aus einer "unsicheren" Quelle stammt, also tatsächlich zu groß werden kann.

Edit: Kann man natürlich auch mit Iteratoren lösen, macht den Code aber auch nicht schöner.

Fonce · 20. September 2016

Weil es so z.B. von Bjarne Stroustrup und Herb Sutter in der GSL definiert ist.
https://github.com/isocpp/CppCoreGu...nctions-and-types-that-are-not-bounds-checked

Die deutlich schönere Variante zu der for Schleife mit Zähler wäre übrigens.

Code:

for (auto& digit : _digits) {
  if (!digit.increment()) { return false; }
}

auch das nutzen von "this->" ist ziemlich überflüssig und macht den Code nur schwerer lesbar.

Code:

bool increment() {
	const int next = _value + _step;
	const bool overflow = next > _max;
	_value = overflow ? _min : next;
	return overflow;
}

Suche

C++ Optimierungsdurchläufe ohne verschachtelte Schleifen?

T_55

Lieutenant

wusu

Cadet 3rd Year

VikingGe

Gast

T_55

Lieutenant

VikingGe

Gast

T_55

Lieutenant

Balou72

Cadet 2nd Year

T_55

Lieutenant

Fonce

Captain

VikingGe

Gast

Fonce

Captain

Ähnliche Themen