3. Komplexer Algorithmus in Klasse?

Komplexer Algorithmus in Klasse?

  • E

    Hi,

    mich sträubts gerade etwas. Ich schreibe einen Algorithmus für dynamische Programmierung, d.h. ich habe eine mathematische, rekursive Formel, die auf den Ergebnissen der letzten Iteration aufbaut und aus zig Schleifen besteht, für die es wiederum einen vorgefertigten Algorithmus gibt, um das zu lösen.

    In diesem Zusammenhang sind die Ergebnisse der letzten Iteration notwendig. Zudem werden diverse Hilfsarrays am Anfang berechnet, die man dann während der Berechnung ständig braucht.

    Würde ich das in eine Klasse stecken, hätte das den Vorteil, dass ich nicht jeder Funktion ständig mein Sammelsurium an Variablen mitgeben müsste. Zudem wären von Anfang an berechnete Hilfsarrays ebenfalls automatisch Attribute, denn gerade die zu übergeben finde ich unschön und unübersichtlich.

    Problem: Irgendwie sträubt es sich in mir, dass ein Algorithmus zu einer Klasse wird. Benutzen würde man das Ding eh nur so:

    Calculation calc(/* zig Parameter */);
calc.calculate(); // evtl. auch im ctor, aber da die Rechnung aufwendig ist vll auch eher nicht
// Zugriff mit diversen Gettern auf die heterogenen Ergebnisse

    Spricht da etwas gegen oder wie würdet ihr so was lösen? Einfach brav alle Variablen immer überall mitschleppen, Hauptsache keine Klasse nutzen?

    Ich weiß halt nicht, ob das c++-idiomatisch als Klasse gestaltet werden sollte oder nicht, ich bin da hin- und hergerissen. Kann eine komplexe Berechnung einer Klasse entsprechen? Ich weiß nicht...

    Vielleicht hat hier jemand Gedanken dazu, die mich weiterbringen. Dankeschön schon Mal 🙂

    0
  • K

    Alles zu schwammig.

    0
  • E

    Nö, ist ne Grundsatzfrage. Für mehr Details und nen tieferen Einstieg müsste ich hier auf unveröffentlichte Paper verweisen, die auf dem ganzen SCM-Grundlagenwissen aufbauen. Hilft Dir das zur Beantwortung der Frage weiter, würdest Du die Paper lesen, Dir das Hintergrundwissen aneignen und dann antworten? Ich denke nicht.

    Wsl enthält der OP einfach unnötige Details, die ich dazu schrieb in der Hoffnung nicht wieder einen "ist zu schwammig"-Beitrag abzukriegen. Die eigentliche Grundsatzfrage ist:

    Ist es ok (idiomatisch) einen Algorithmus mit vielen Zwischenergebnissen und vielen Variablen in eine Klasse auszulagern, damit man sich für die Funktionen für die Teile eines Algorithmuses spart die ganzen Variablen mitzuschleppen?

    Wenn das nicht zu beantworten ist: Welche Details über den Algorithmus sind notwendig, um diese Frage zu beantworten?

    0
  • D

    Eisflamme schrieb:

    Ist es ok (idiomatisch) einen Algorithmus mit vielen Zwischenergebnissen und vielen Variablen in eine Klasse auszulagern, damit man sich für die Funktionen für die Teile eines Algorithmuses spart die ganzen Variablen mitzuschleppen?

    Das ist (für mich) völlig in Ordnung.

    Hat auch den Vorteil, dass du Teile des Algorithmus leicht austauschen/widerverwenden könntest, falls das mal nötig werden sollte (Template Method).

    0
  • ?

    du solltest dich fragen ob es in ein Klassenkonzept passt.

    Für mich wäre da wichtig:

    Beschreibt dies einen größeren Zusammenhang in der Mathematik. Beispiel: Matritzenrechnung im 2D Raum. Dort würde eine Klasse Sinn machen da ich Sie so einsetzen könnte:

    Matrix2D Matrix;
CPunkt2D NullPunkt(0.0,0.0);
Matrix.Rotiere(NullPunkt,PI/2);

    und später dann

    std::vector<CPunkt2D> vPunkte; 
vPunkte.push_back(123,321);

    um dann nachdem ich meine Punkte habe diese um einen Nullpunkt rotieren zu lassen

    Matrix.Transform( vPunkte );

    So lässt sich ein großer Zusammenhang in der Mathematik sehr schnell kapieren. Ich konnte diese Klasse sofort verwenden und hatte kaum Anlaufschwierigkeiten. Matritzen hatte ich erst wesentlich später kapiert. Das ich aber so einen Punkt um einen Nullpunkt rotieren lassen konnte das kapierte ich schnell.

    Für mich gilt heute. Die kleinen Zusammenhänge bilde ich in freien Funktionen ab oder statischen Funktionen in einer Klasse. Da ich hier auf 25 Jahre alten C Code aufbaue bin ich meist dazu gezwungen auf die Funktionen aufzubauen die schon da sind.

    Für die großen Zusammenhänge dann Anwendungsbezogene Funktionen in einer Klasse. Diese müssen beliebig nacheinander Anwendbar sein und dürfen sich nicht stören gegenseitig oder die Logik erlaubt dies.

    z.B. bei der Matrixklasse kann ich auch

    Matrix2D Matrix;
CPunkt2D NullPunkt(0.0,0.0);
Matrix.Rotiere(NullPunkt,PI/2);
Matrix.Rotiere(NullPunkt,PI/2);
Matrix.Rotiere(NullPunkt,PI/2);
Matrix.Rotiere(NullPunkt,PI/2);

    so rotieren und wäre beim .Transform() wieder auf dem gleichen Punkt ( +- Fließkommaabweichung )

    0
  • E

    Nein, es gibt keinen größeren Kontext, den man sinnvoll als Klasse abbilden könnte. Von meinem Idiom-Verständnis von C++ sollte es eigentlich keine Klasse sein, ABER es hat eben massive Vorteile beim Schreiben des Codes es in einer Klasse zu handhaben. Das ist mein Konflikt.

    Variante wäre eben die Klasse rein in der cpp-Datei zu nutzen und die Schnittstelle nach außen hin über eine simple Funktion anzubieten. Dann merkt der Benutzer nicht, dass das eine Klasse ist.

    Ich weiß aber nicht, ob diese Lösung wirklich das idiomatische Problem löst, denn faktisch ist es eben doch eine Klasse. Oder ist das dann hier so gut wie egal, solange man das nach außen hin schön versteckt?

    0
  • Mod

    Du willst es also in eine Klasse packen, um im Rahmen deines Algorithmus quasi globale Variablen zu haben? Das klingt mir nicht nach einer guten Idee, aus eben den Gründen, die auch normalerweise gegen globale Zustände sprechen.

    0
  • O

    Ja, packs in eine Klasse. Das kann "in the long run" auch Vorteile haben, weil du den Algorithmus dann auch zum Beispiel neustarten kannst, wenn das vorherige Ergebnis nur leicht angepasst werden muss.

    //edit es macht auch Sinn, weil du so einfacher zugriffe auf die Zwischenergebnisse hast, wenn du deinen Algorithmus am Ende auswertest.

    0
  • E

    SeppJ:
    Interessante Betrachtungsweise und echt nicht abwegig. Aber die Nachteile für globale Variablen finde ich in dem Rahmen nicht zutreffend:
    - Tests kann man hier ja trotzdem gut machen
    - Übersichtlichkeit geht nicht verloren, sondern steigt (genauer betrachtet diskutabel; aber die Unübersichtlichkeit von globalen Variablen sehe ich hier nicht, wir haben ja immerhin den klar definierten Scope des Algorithmuses, der durch die Klasse repräsentiert wird; für genau diesen Scope sind die Variablen ja auch gedacht)
    - Lokalität der Variablen ist hier genau so im Funktions- wie im Klassenfall
    - namespace pollution spielt hier keine Rolle

    Eigentlich fällt mir überhaupt kein Argument gegen globale Variablen ein, was hier greifen würde. Was hast Du denn im Kopf?

    Na ja, ich finde halt, dass es ordentlich aufbläht, z.B.

    std::vector<int> calculateHelperArray1(/* params */);
std::vector<int> calculateHelperArray2(/* params */);

struct results
{
    // multiple variables
};

struct subAlgorithm1Results
{
    // multiple other variables
};

struct subAlgorithm2Results
{
    // multiple again other variables
};

subAlgorithm1Results subAlgorithm1(/* params */);
subAlgorithm2Results subAlgorithm2(/* params */);

results calculate(/* params */)
{
    auto helperArray1 = calculateHelperArray1(/* params */);
    auto helperArray2 = calculateHelperArray2(/* params */);

    // ein paar Schleifen, in der folgender Code vorkommt, aber egal
    auto results1 = subAlgorithm1(/* params */, helperArray1);
    auto results2 = subAlgorithm2(/* params */, helperArray2);

    // das jetzt mit nem dritten Algorithmus verbinden oder so
    return calculateResults(results1, results2);
}

    Mein Code sieht nicht so aus, aber was dazu kommt ändert an der Fragestellung wenig (hoffe ich, ist immer gefährlich so was zu skizzieren).

    Im Rahmen einer Klasse könnte ich mir sparen:
    - Die Übergabe der ganzen Parameter
    - solche "Extra"variablen wie helperArray1, helperArray2
    - u.U. Hilfsstrukturen wie subAlgorithmXResults (wobei ich das durchaus etwas grenzwertig finde)

    Und:
    - Der Code wird (teilweise wegen obiger Ersparnisse) kürzer und imo dadurch übersichtlicher

    otze:
    Stimmt, das sind weitere Vorteile. 🙂

    0
  • C

    Globale Variablen sind grundsätzlich schlecht, z.B. auch für Parallelisierbarkeit.
    Vielleicht will ja jemand in Zukunft zwei Ergebnisse mit unterschiedlichen Parametern gleichzeitig berechnen?
    In meinem "Idiom-Verständnis von C++" ist es jedenfalls wesentlich wichtiger keine globalen Variablen zu verwenden,
    als intern irgendwo das Klassenkonzept genau passend anzuwenden!

    Ob man diese Klasse dann dem Benutzer zeigt, hängt davon ab, ob er mehr als eine Methode sinnvoll benutzen kann.

    Falls es nur darum geht Ergebnisse abzufragen ist eine result-Struktur/Klasse und eine calculate funktion imho besser geeignet,
    zumindest wenn man die Resultate auch mit einem anderen Algorithmus berechnen könnte.

    0
  • E

    In meinem "Idiom-Verständnis von C++" ist es jedenfalls wesentlich wichtiger keine globalen Variablen zu verwenden,
    als intern irgendwo das Klassenkonzept genau passend anzuwenden!

    Ich bin nicht sicher, ob ich oder Du da etwas missverstanden haben, aber in unserem Fall setzt SeppJ ja die Attribute einer Klasse mit globalen Variablen gleich (im Bezug auf die Nachteile jedenfalls); tatsächliche globale Variablen haben wir hier nirgendwo.

    0
  • K

    Nö

    Doch.

    ist ne Grundsatzfrage

    Ach, denkst du, dass alle Probleme loesbar durch dynamische Programmierung grundsaetzlich gleich implementiert werden? Wenn ja, wo ist dein Problem?

    0
  • N

    Eisflamme schrieb:

    Problem: Irgendwie sträubt es sich in mir, dass ein Algorithmus zu einer Klasse wird.

    Das ist ein Dogma, das von den schlechten Beispielen in C++-Büchern à la class InsertionSort : public Sort herrührt. Es kann durchaus Sinn machen, Algorithmen als Objekte zu betrachten. Mittlerweile haben Funktionen in C++ durch std::function sowieso First-Class-Status. Die LEMON-Bibliothek benutzt auch Klassen, um Graphen-Algorithmen zu repräsentieren. Das hat den Vorteil, dass man recht viel Kontrolle über die Ausführung hat und gezielt Resultate abfragen kann.

    Wenn du aber sowieso immer nur algorithmus.run() hast, ist die Frage natürlich berechtigt, ob sich eine Klasse lohnt. Eine Möglichkeit wäre auch, intern (d.h. nicht im API) eine Klasse zu verwenden, wenn dadurch die Implementierung vereinfacht wird.

    Eisflamme schrieb:

    Eigentlich fällt mir überhaupt kein Argument gegen globale Variablen ein, was hier greifen würde. Was hast Du denn im Kopf?

    Mit Klasse haben alle Memberfunktionen Zugriff auf alle Daten des Algorithmus. Ohne Klasse sieht man genauer, welche Daten an welche Funktionen übergeben werden. Das kann also durchaus dazu führen, dass du Wartung und Tests einfacher durchführen kannst, weil du Seiteneffekte minimierst und klarere Ablaufpfade hast. Ist halt eher ein funktionaler Ansatz.

    Deine Frage ist übrigens nicht zu schwammig. Aber knivil spielt gerne den nicht zufriedenstellbaren Skeptiker 🙂
    Man kann ein Problem bzw. die Vor- und Nachteile verschiedener Lösungsansätze auch diskutieren, ohne alles bis ins letzte Detail zu kennen.

    0
  • E

    Nexus:
    Danke auch Dir, Du bringst sehr viele nützliche Informationen. 🙂

    Ja, ich glaube der Unterschied, wie viel Kontrolle man haben möchte und ob man noch mehr macht als nur die eine Funktion aufzurufen machen viel aus. Mich stört noch immer ein bisschen, dass man mehr Code schreibt und die Parameterübergabe etwas lästig ist.

    Vermutlich ist es aber zweckdienlich structs AlgorithmInput, AlgorithmOutput zu definieren. Damit wird das etwas reduziert. Es bleiben dann halt noch die Nachteile, dass man bei Parametern a-g in der struct einen zu viel übergibt, wenn eine Funktion nur a-f braucht. Oder man müsste für jeden Fall Extrastrukturen definieren.

    Die Klasse rein für die Implementierung zu nutzen finde ich gut, wobei das am Problem selbst nicht viel ändert, finde ich.

    Ich tendiere jetzt erstmal dazu den Algorithmus als Funktion mit In/Out-structs lösen und später dann vielleicht eine Klasse draus basteln, wenn wirklich mehr Kontrolle dazu kommt. Dafür muss ich zwar ein bisschen mehr Schreibarbeit in Kauf nehmen, aber das scheint mir zurzeit der beste Kompromiss zu sein.

    Falls noch weitere Ideen oder Meinungen kommen, sehr gerne!

    0
  • N

    Eisflamme schrieb:

    Es bleiben dann halt noch die Nachteile, dass man bei Parametern a-g in der struct einen zu viel übergibt, wenn eine Funktion nur a-f braucht. Oder man müsste für jeden Fall Extrastrukturen definieren.

    Oder die entsprechenden Parameter einfach leer (als Defaultwert) lassen.

    Du kannst dich auch fragen, wie du die Strukturen am besten initialisierst. Abzuwägen ist zwischen Aussagekraft, Codekompaktheit und Implementierungsaufwand. Ein paar Möglichkeiten:

    // 1. Memberweise
// Sehr simpel und mächtig, aber geht nicht in temporären Ausdrücken
Input i;
i.position = Vector2(2, 3);
i.rotation = 90.f;
function(i);

// 2. Konstruktoren
// Kompakte, aber wenig aussagekräftige Ausdrücke
function( Input(Vector2(2, 3), 90.f) );

// 3. Named Constructor Idiom
// Aussagekräftig, aber Kombination muss vorhanden sein
function( Input::fromPositionAndRotation(Vector2(2, 3), 90.f) );

// 4. Named Parameter Idiom
// Aussagekräftig und kompakt, aber viel Implementierungsaufwand
function( Input().position(2, 3).rotation(90.f) );

// 5. Boost.Parameter
// Nette Syntax, aber verwendet schwarze Magie
function(position = Vector2(2, 3), rotation = 90.f);
    0
  • E

    Ja, ich tendiere da meist zu Variante2, weil die IDE einem die Namen eh nennt, wenn man draufklickt. Für einen schnellen Überblick finde ich auch so was okay:

    Input(Vector2f(2, 3) /* position */, 90.f /* rotation */);

    denn bei der Eingabe weiß man ohnehin, was erwartet wird, da kann man es kurz dazutippen. Und wenn man den Code überfliegt, ist es angenehm, dass es dabei steht. Kann man natürlich nicht überall konsequent durchziehen, finde ich aber in Ordnung.

    0
  • J

    Klar ne klasse draus machen. Alles andere ist ab einer gewissen Komplexität unsinnig. Was wäre die Alternative? Funktionen machen, die sich ständig alles übergeben? Irgendwann zu unleserlich, also packt man den kompletten state in ne struct und übergibt den an die funktionen... Aber hey, das ist genau das was C++ mit klassen macht, nur dass der this-parameter implizit übergeben wird.

    Das machen afaik auch so ziemlich alle bibliotheken, die nichttriviale Algorithmen implementieren.

    0
  • N

    Oder die Hardcore-Variante ⚠

    // 5. Boost.Parameter
// Nette Syntax, aber verwendet schwarze Magie
function(position = Vector2(2, 3), rotation = 90.f);
    0
  • ?

    Jester schrieb:

    Klar ne klasse draus machen. Alles andere ist ab einer gewissen Komplexität unsinnig. Was wäre die Alternative?

    Wie die Implementation aussieht ist völlig unabhängig vom Interface.

    Ich habe sehr oft

    // header:
int komplexer_algorithmus(params);

// impl:
namespace {
  struct algorithmus_klasse { ... };
}
int komplexer_algorithmus(params)
{
  algorithmus_klasse alg; // algorithmus_klasse darf nur ich benutzen
  alg.init(params)
  meine_daten.run();
  return meine_daten.result();
}

    Wenn es zu viele Parameter werden, fasst man diese halt in Klassen zusammen, wie es Nexus vorgeschlagen hat. Wie der DP-State gehalten wird ist Implementierungsdetail.

    Nun kommt es aber vor, dass der State über verschiedene Aufrufe beibehalten werden sollte. Das geht bei Bedarf aber ähnlich:

    class DP_State {
  friend class algorithmus_klasse;
  // private Daten, nach aussen unsichtbar
};
// header:
int komplexer_algorithmus(params, DP_State& dp);
int komplexer_algorithmus(params) { DP_State dp; return komplexer_algorithmus(params, dp); }

    Im Prinzip geht es darum, zwischen

    // A
State s1;
s1.run(...);

// B
State s2;
s2.run(...);
s2.run(...);

    und

    // A
run(...);

// B
State s;
run(..., s);
run(..., s);

    zu entscheiden.

    In einer Sprache, die Templates und ADL hat, ist ganz klar die zweite Variante zu bevorzugen.

    Gibt ein paar Leute, die sind noch nicht ganz in C++ angekommen (z.B. die von LEMON), aber heutzutage liegt der Konsens bei Variante 2.

    0
  • J

    Das ist doch nur die frage welchen zucker man im interface außenrum streut. Ich dachte das hier wäre eine frage wie man Algorithmen implementiert, daher meine Antwort.

    Wenn es natürlich im Gegensatz nur drum geht zu fragen mit welchen zucker man drum rumklebt, dann will ich nix gesagt haben, nicht meine baustelle. Ich frag mich dann aber warum überhaupt das Wort Algorithmus in der Aufgabenstellung drinsteht.

    0
Anmelden zum Antworten