Komplexer Algorithmus in Klasse?

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.