Statischer Text mit variablen Anteil



  • Hallo,
    ich habe ein Problem bei dem ich hoffe, dass ihr mir eurer Erfahrung Tipps für die optimale Umsetzung geben könnt.

    Um den Kontext des Problems zu verstehen versuche ich es anhand eines Beispiels zu erklären.
    Es soll ein Programm zum Lösen eines Spiels erstellt werden, in diesem Beispiel Schach.
    Es gibt 3 Hauptkomponenten: Eingabe -> Verarbeitung -> Ausgabe

    Die Eingabe bekommt die aktuelle Zusammenstellung des Spiels, wo welche Figure steht. Die Verarbeitung berechnet für bestimmte Probleme die Lösung. Gibt dann der Ausgabe das aktuelle Feld + den nächsten Lösungsschritt.

    Das wird nun bei jedem neuen Schritt des Spielers wiederholt. Da die Berechnung der Lösung allerdings komplizierter ist, wird dies nur einmal gemacht (die Lösung verändert sich ja nicht).

    Die Lösung besteht aus n Tupel für die n Schritte bis zum Ziel. Das Tupel besteht aus dem nächsten Schritt, welche Figur wohin fahren soll, plus einem zusätzlichen Text, um dem Nutzer das Vorgehen zu erklären.

    So, genau um diesen Text geht es nun.
    Eine Kösung kann aus sehr vielen Schritten bestehen. Wenn bei jedem Zug ein String dabei steht verbraucht das einiges an Speicher, den ich gerne optimieren würde. Dazu kommt noch, dass mehrere Texte gleich sind.

    Meine erste Idee war, alle Texte als const char* TEXT = "der Text" zu deklarieren und nur den Zeiger in das Tupel zu speichern.
    Das hat einen Haken, die Texte haben variable Teile. Zum Beispiel:
    "Der %FARBE% %FIGUR% greift an, damit er den Gegner unter Druck setzt."
    Das kann nun mit "weißer Springer" aber auch mit "schwarzer Läufer" verwendet werden.
    Wenn ich es nun mit Zeiger machen will, müsste ich für jeden Fall den Text angeben, was sehr viel wird, obwohl es nur wenige Grundaufbaue gibt.

    Könnt ihr mir einen Tipp geben, wie ihr das effizient umsetzen würdet?

    Ich hoffe ihr habt das Problem verstanden! Wenn nicht, fragt nach.

    Vielen Dank.


  • Mod

    Idee auf die Schnelle:

    class Text
    {
     public: 
     virtual operator string() const = 0;
    };
    
    class UnterDruckText: public Text
    {
      Farbe farbe;
      Figur figur;
     public:
      UnterDruckText(Farbe farbe, Figur figur): farbe(farbe), figur(figur) {}
      virtual operator string() const override
      {
        return string("Der ") + to_string(farbe) + " " + to_string(figur) 
             + " greift an, damit er den Gegner unter Druck setzt.";
      }
    };
    

    P.S.: Du löst übrigens gerade Probleme, die du höchstwahrscheinlich gar nicht hast. Wie viele Züge sind denn im Programm gespeichert? Dutzende? Hunderte? Das sind ein paar kB Text. Auf einem Rechner, der sicherlich gigabyteweise RAM hat.



  • Joa, das kann man doch so machen. Boost.Format kommt mir da in den Sinn.

    Einen Text könntest du so speichern:

    const int max_param_count = 4;
    
    struct text
    {
      char const* format;
      char const* params[max_param_count];
    };
    

    wobei man das mit den Parametern null-terminiert machen könnte.

    und wenn du die Zeichenkette ausgeben willst, könntest du es so mit Boost.Format machen:

    std::ostream& operator<<(std::ostream& out, text const& t)
    {
      boost::format fmt (t.format);
      for (int i=0; i<max_param_count && t.params[i]; ++i)
        fmt % t.params[i];
      return out << fmt;
    }
    

    Ggf kann man da auch mit Funktionszeigern arbeiten, die einem den Text ausgeben. Die Frage ist dann nur, wie die Parameter gespeichert werden. Statt eines Funktionszeigertypens kann man dann

    typedef std::function<void(std::ostream&)> text_printer;
    

    verwenden. Also speichern und ausgeben so:

    vector<tuple<zug,text_printer>> loesung;
    ...
    for (auto const& tup : loesung)
    {
      ...
      std::get<1>(tup)(std::cout); // std::cout an text_printer geben
      ...
    }
    

    und erzeugen der text_printer so:

    farbe fa1 = ...;
    figur fi1 = ...;
    farbe fa2 = ...;
    figur fi2 = ...;
    text_printer tp = [=](std::ostream& out){
      out << piece2text(fa1,fi1) << " greift " << piece2text(fa2,fi2) << " an";
    };
    

    wobei piece2text dann noch die Enum-Werte nimmt und über << Zeichenketten ausgibt -- oder so ähnlich. Wenn man da der deutschen Grammatik gerecht werden will, müsste man da wohl noch die verschiedenen Fälle und Geschlechter unterscheiden. 😉

    Oder eben so wie SeppJ zeigte, wobei ich dann im Tuple einen unique_ptr<Text> speichern würde.

    Hat alles Vor- und Nachteile. Das erste wird sehr kompakt im Speicher sein. Allerdings bist du da auf eine maximale Anzahl von String-Parameter begrenzt, wobei bei den anderen Varianten die Formatierungs- und Parameterisierungsdetails natürlich schön versteckt sind. Das erfordert aber auch eine zusätzliche Indirektion. Was ich bei std::function noch cool finde, ist, dass eine gute Implementierung wahrscheinlich von der SFO (small function optimization) Gebrauch machen wird. Hast du also nur wenige Parameter, kann es sein, dass man sich damit wenigstens die Freispeichernutzung sparen kann. Farbe und Figur kann man zusammen in ein einziges Byte quetschen, beispielsweise.



  • Hallo ihr beiden,
    vielen lieben Dank für eure Antworten.

    Das mit Boost sieht eigentlich ganz gut aus. Allerdings weiß ich nicht, ob wir in diesem kleinen Projekt Boost hernehmen, muss ich nachfragen.

    Die Idee von SeppJ mit der abgeleiteten Klasse sieht ganz gut aus. Zwar hat man hier den Overhead von Klassen aber im Prinzip finde ich es nicht schlecht.
    @krümelkacker was meinst du genau mit "ich soll unique_ptr<Text>" nutzen? Ich habe noch nie mit einem unique_ptr gearbeitet.

    SeppJ schrieb:

    P.S.: Du löst übrigens gerade Probleme, die du höchstwahrscheinlich gar nicht hast. Wie viele Züge sind denn im Programm gespeichert? Dutzende? Hunderte? Das sind ein paar kB Text. Auf einem Rechner, der sicherlich gigabyteweise RAM hat.

    Ja da hast du auf jeden Fall recht. Habe mir nur gedacht, dass hier Optimierung nicht schaden könnte, da doch mit sehr viel ähnlichen Texten gearbeitet wird, die nicht unbedingt zick Mal im Speicher gehalten werden müssen.
    Ich mag Optimierung, auch wenn ich das Zitat von Donald Knuth kenne:
    "We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil"


  • Mod

    Xenya schrieb:

    Die Idee von SeppJ mit der abgeleiteten Klasse sieht ganz gut aus. Zwar hat man hier den Overhead von Klassen aber im Prinzip finde ich es nicht schlecht.

    😮 Overhead von Klassen?

    Ich habe zwar ein virtual benutzt (welches tatsächlich einen sehr kleinen Overhead erzeugt), aber bei dir klingt die Aussage so, als wäre sie allgemein gemeint. Ich habe da einen bösen Verdacht.

    Ja da hast du auf jeden Fall recht. Habe mir nur gedacht, dass hier Optimierung nicht schaden könnte, da doch mit sehr viel ähnlichen Texten gearbeitet wird, die nicht unbedingt zick Mal im Speicher gehalten werden müssen.
    Ich mag Optimierung, auch wenn ich das Zitat von Donald Knuth kenne:
    "We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil"

    Das bestätigt meinen Verdacht.

    Oje.

    Ich mache dir jetzt mal einen harten Vorwurf:
    Du hast überhaupt keine Ahnung. Trotzdem möchtest du alles optimieren, weil du denkst, es wäre cool. Dabei ignorierst du alle Weisheiten derer, die es besser wissen, denn du hältst dich für klüger.

    Komme ich mit diesem Vorwurf der Wahrheit nahe? Möglicherweise leugnest du es vor dir selber. Woher ich das alles weiß? Weil wohl jeder Anfänger durch so eine Phase geht, in der er so drauf ist. Je früher sie damit aufhören, desto besser für sie. Aber sie ignorieren solche Ratschläge natürlich. Stattdessen wird mit esoterischen Mitteln Code kaputt "optimiert", bis er langsamer läuft als eine einfache Lösung und dabei auch noch unlesbar ist.

    Vielleicht bist du aber einer der wenigen, die auf solche Hinweise reagieren und lernen, worauf es wirklich ankommt.

    P.S.: Dieser konkrete Fall ist sogar ein wunderbares Beispiel für eine Kaputtoptimierung. Du erkaufst Speichereffizienz für Rechenzeit. Gleichzeitig erhöht sich die Codekomplexität. Letzteres ist immer ein Nachteil. Ersteres, der Tausch von Speichereffizienz gegen Recheneffizienz, ist ebenfalls ein Nachteil, solange man nicht in Probleme mit dem Speicher kommt*. Wenn man damit nämlich keine Probleme hat, dann hat man Rechenzeit weggeworfen, ohne etwas gewonnen zu haben. Das heißt von

    dass hier Optimierung nicht schaden könnte

    kann keine Rede sein.

    *: Nicht unbedingt nur "Speicher voll", sondern evtl. auch Cache Misses.


Log in to reply