Komplexer Algorithmus in Klasse?

daddy_felix

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).

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 )

Eisflamme

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?

SeppJ

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.

otze

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.

Eisflamme

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.

C14

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.

Eisflamme

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.

knivil

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?

Nexus

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.

Eisflamme

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!

Nexus

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);

Eisflamme

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.

Jester

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.

Nexus

Oder die Hardcore-Variante

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

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.

Jester

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.

Nexus

nichttrivialer schrieb:

Im Prinzip geht es darum, zwischen
// [...]
State s2;
s2.run(...);
s2.run(...);
und
// [...]
State s;
run(..., s);
run(..., s);
zu entscheiden.

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

Warum? Die Unterschiede sind für den Aufrufer nur syntaktisch. Genauso könnte man sagen, in einer Sprache, die OOP hat, ist ganz klar die erste Variante zu bevorzugen. Eine semantische Alternative ist der funktionale Ansatz, weil dadurch Seiteneffekte kontrollierbarer sind:

State s;
s = run(..., s); // Übergabe als Kopie oder Move
s = run(..., s);

nichttrivialer schrieb:

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.

Würde ich nicht sagen. Die Entwickler haben einiges drauf. Hinter den Klassen stecken ziemlich generische und wiederverwendbare Komponenten -- und im Gegensatz zu Boost.Graph haben sie es dennoch geschafft, ein vernünftiges Interface anzubieten. LEMON ist meiner Meinung nach eine recht schöne C++-Bibliothek.

Nexus schrieb:

Warum? Die Unterschiede sind für den Aufrufer nur syntaktisch.

Nein, die freie Funktion lässt sich überladen.

namespace FremdesModul {
  class Spezialfall;
  void run(Spezialfall const& m, State& s)
  { /* besserer Algorithmus */ }
}
Spezialfall m;
run(m); // ruft run(Spezialfall const&, State&) durch das run(...)-Template ohne State-Parameter auf
State s;
run(m, s); // run(Spezialfall const&, State&)

Gut, das ginge natürlich auch wieder, wenn man in der Klasse eine Indirektion einbaut.

Aber es gibt hier einen zweiten Punkt:

Eine semantische Alternative ist der funktionale Ansatz, weil dadurch Seiteneffekte kontrollierbarer sind:

Mein Ansatz ist der funktionale Ansatz. State ist der Seiteneffekt. Du kannst ohne Seiteneffekt arbeiten (ohne Parameter), ohne Seiteneffekt mit bereits vorhandenem State (dafür braucht es noch eine zusätzliche Funktion

int run(params, State const& s)
{
  State copy = s;
  return run(params, copy);
}

) oder mit Seiteneffekt.

Und funktional bedeutet Seiteneffekt kontrollierbar (State ist hier unsere Monade).

Setz das mal mit Klassen um. Dazu bräuchtest du Verrenkungen wie

class MyAlgorithm {
  int run(params) { ... }
  int run(params) const { MyAlgorithm copy = *this; return copy.run(params); }
};

und das für jede Klasse, die run implementiert (es sei denn, man macht einen CRTP-Workaround, was noch hässlicher ist). Die freie Funktion mit ADL braucht das nur einmal.

Gut, auch das liesse sich in Klassen umsetzen, aber Funktionen sind einfacher umzusetzen (pro Algorithmus bräuchte es 2 freie Funktionen für ADL und die Kurzvariante ohne State), damit und wenn es keinen Grund für Klassen gibt, dann verwende ich lieber Funktionen.

und im Gegensatz zu Boost.Graph haben sie es dennoch geschafft, ein vernünftiges Interface anzubieten. LEMON ist meiner Meinung nach eine recht schöne C++-Bibliothek.

Zugegeben, ich kenne LEMON nicht und will nicht schlechtreden, was ich nicht kenne.
Aber die Transformation a.f(p) -> f(p,a) ist trivial und liesse prinzipiell sich auch mit LEMON umsetzen.

Ich könnte mir vorstellen, dass die Klassen-Lösung etwas sauberer ist, wenn man den Algorithmus anhalten kann und dann weiter ausführen, es also verschiedene Zwischenstates gibt, die

Nexus

nichttrivialer schrieb:

Aber die Transformation a.f(p) -> f(p,a) ist trivial und liesse prinzipiell sich auch mit LEMON umsetzen.

Das schon, aber brächte es einen Mehrwert? Kapselung wäre für die Entwickler mühsamer umzusetzen (entweder alle haben Zugriff auf Interna oder gezielte friend s werden notwendig), und die Schnittstelle ist für den Benutzer möglicherweise weniger intuitiv. Momentan kann man recht praktisch Zwischenzustände kontrollieren (siehe ersten Link). Wenn die Funktionen direkt zur Klasse gehören und man sie ihnen gewaltsam entreissen müsste, finde ich Memberfunktionen schon sinnvoll.

Ansonsten stimme ich dir aber zu, freie Funktionen können in einigen Szenarien Vorteile bringen.