3. Designfrage viele aufeinanderfolgende Validierungsfunktionen

Designfrage viele aufeinanderfolgende Validierungsfunktionen

  • P

    Moin,

    ich habe auf Grundlage der hier im Forum erhaltenen Antworten einen ersten dynamischen Parser gebaut, der bislang auch gut läuft und bin jetzt dazu übergegangen auf Grundlage dessen ein C# Programm zu erstellen, dass mir aus einer Syntax automatisch den Tree-Generator für C++ und meine Bibliothek erzeugt.
    Der Tree ist soweit ok, ein Optimizer wäre sicherlich noch sinnvoll aber dazu später.

    Die Frage die sich mir stellt ist jedoch folgende, wenn ich den Code erzeugen lasse, erzeugt jedes Token eine Funktion deren Signatur immer dieselbe ist, deren Inhalt sich aber aus den im Token enthaltenen Subtokens zusammensetzt.

    //ebnf syntax
token = [subtoken];

//pseudo code
function Istoken
  while subtoken
    addNode

    um es mal sehr simpel auszudrücken. Dazu kommt noch eine allgemeine Parsing-Methode, die wiederum solange die Is... Funktionen durchläuft bis der Eingabetext /0 ist oder ein Durchgang erfolglos war und genau hier hardere ich mit der für die Geschwindigkeit optimalen vorgehensweise.

    Eine Idee wäre, dass ich nacheinander alle Funktionen abfrage (diese liefern immer bool zurück) und in jeder Anweisung immer wieder den selben Code hinterlege, also sprich

    while(text) //<- char pointer
{
...
if(Is...()) { /*create node here*/ continue; }
if(Is...()) { /*create node here*/ continue; }
if(Is...()) { /*create node here*/ continue; }
usw...
...}

    das erscheint mir bislang am Sinnvollsten, auch wenn es den Code enorm aufbläßt ist es dennoch ein paar calls weniger als wenn ich nur die ifs abfragen würde und am ende eine einzige create node funktion hätte

    while(text) //<- char pointer
{
...
if(!flag && Is...()) flag = true;
if(!flag && Is...()) flag = true;
if(!flag && Is...()) flag = true;
usw...
if(flag)
  /*create node here*/
...}

    da hier trotzdem weiterhin wenigstens das flag = false abgefragt würde, auch wen ich an Position 0 bereits ein match hatte.

    an ein Array mit Pointern für die entsprechenden Funktionen hatte ich auch gedacht, ist aber komplizierter und warscheinlich nicht so effektiv (schleife, inkrement, pointerarray im speicher etc.) wie meine bisherige Variante mit den continues.

    Hat hier jemand noch eine andere villeicht bessere Idee wie man das für eine feste Anzahl Funktionen statisch effektiver lösen könnte?

    0
  • ?

    Mir würde nur einfallen, dass du die Abfragen so sortierst, dass die Funktionen nach Wahrscheinlichkeit geordnet sind. Also die wahrscheinlichsten Funktionen stehen weiter oben.

    0
  • ?

    Ach, und um den Code zumindest lesbarer zu machen, kannst du dir natürlich auch die Lazy Evaluation zu nutzen machen:

    if (Is...()) || Is...()) || Is...()) || ...)
{
 /*create node here*/
}
    0
  • S

    an ein Array mit Pointern für die entsprechenden Funktionen hatte ich auch gedacht, ist aber komplizierter und warscheinlich nicht so effektiv (schleife, inkrement, pointerarray im speicher etc.) wie meine bisherige Variante mit den continues.

    Ja, erstmal die Version von gkghkghk (natürlich mit der richtigen Syntax). Aber was ist falsch mit den Pointer-Arrays? Dann kannst du auch manuell bequem Funktionen hinzufügen/entfernen, die Reihenfolge ändern, usw.
    Das Argument mit dem Speicher halte ich für Verrückt. Wenn ein Zeiger bspw. Vier Bytes groß ist, dann kommst du möglicherweise bei hunderten Funktionen auf ein, zwei Kilobyte.

    bool (*ptr[])() = { is..., is..., ... };

if( std::any_of( std::begin(ptr), std::end(ptr), [](bool is()){ return is(); } ) )
	/* create node here */
    0
  • P

    gkghkghk schrieb:

    Mir würde nur einfallen, dass du die Abfragen so sortierst, dass die Funktionen nach Wahrscheinlichkeit geordnet sind. Also die wahrscheinlichsten Funktionen stehen weiter oben.

    Klar, das obliegt aber in erster Linie dem Anwender bzw. alleine schon dem Design von EBNF, dass natürlich das komplexeste und somit warscheinlichste Token zuerst definiert wird.

    Sone schrieb:

    Aber was ist falsch mit den Pointer-Arrays? Dann kannst du auch manuell bequem Funktionen hinzufügen/entfernen, die Reihenfolge ändern, usw.
    Das Argument mit dem Speicher halte ich für Verrückt. Wenn ein Zeiger bspw. Vier Bytes groß ist, dann kommst du möglicherweise bei hunderten Funktionen auf ein, zwei Kilobyte.

    Steht ja wohl außer Frage, dass ein if(...), if(...) schneller ist als ein while((ptrBegin++) <= ptrEnd) if(...), da müsste ich mal ein Benchmark machen inwieweit das ins gewicht fällt ... 😕

    Ich guck mal welchen Vorschlag ich verwenden werde.
    Danke erstmal!

    0
  • S

    Pria schrieb:

    Steht ja wohl außer Frage, dass ein if(...), if(...) schneller ist als ein while((ptrBegin++) <= ptrEnd) if(...), da müsste ich mal ein Benchmark machen inwieweit das ins gewicht fällt ... 😕

    Wie auch in einem anderen Thread halte ich das für einen Performance-Wahn + premature optimization. Meine Lösung ist vielleicht langsamer, dafür ist es weniger Code (!), weswegen meine Lösung weniger Arbeitsspeicher verschwendet.

    0
  • ?

    Sone schrieb:

    Pria schrieb:

    Steht ja wohl außer Frage, dass ein if(...), if(...) schneller ist als ein while((ptrBegin++) <= ptrEnd) if(...), da müsste ich mal ein Benchmark machen inwieweit das ins gewicht fällt ... 😕

    Wie auch in einem anderen Thread halte ich das für einen Performance-Wahn + premature optimization. Meine Lösung ist vielleicht langsamer, dafür ist es weniger Code (!), weswegen meine Lösung weniger Arbeitsspeicher verschwendet.

    Das hast du gut aufgeschnappt. Passt hier aber nicht. Das braucht sogar mehr Code als der is()||is()||...-Ansatz

    @Pria: Nimm, was am übersichtlichsten ist. Du unterschätzt den Compiler, der optimiert dir das Flag raus.

    Generell ist es besser, ein switch/case (oder was Äquivalentes dazu) zu verwenden, dadurch können die Abfragen sozusagen parallel bearbeitet werden. Zeig mal deine is-Funktionen, dann können wir dir vieleicht mehr sagen.

    0
  • P

    hominilupus schrieb:

    Nimm, was am übersichtlichsten ist. Du unterschätzt den Compiler, der optimiert dir das Flag raus.

    Welche Variante meinst du?

    hominilupus schrieb:

    Generell ist es besser, ein switch/case (oder was Äquivalentes dazu) zu verwenden, dadurch können die Abfragen sozusagen parallel bearbeitet werden. Zeig mal deine is-Funktionen, dann können wir dir vieleicht mehr sagen.

    Nun im Grunde kann ich nichts zeigen weil sich das wiederum danach richtet, wie ein Token definert ist. Ein einfaches Beispiel könnte unter anderem so aussehen

    Numeric = ["-"] NUMERIC; //NUMERIC <- Macro

    bool ÷CLASS::IsNumeric(const char* term, SyntaxNode* root)
//(const char* term, SyntaxNode* root) <- immer gleich
{
  ...
  if(*term == '-')
  { /* add node to root */ term++; } //optional

  bool found = false;
  while(*term >= '0' && *term <= '9')
  { found = true; term++; }

  if(found)
  { /* add node to root */ return true; }
  else return false;
  ...
}

    ist jetzt natürlich gerade schnell gemacht und weder getestet noch optimiert aber alles in allem sollte die grobe Richtung klar sein.
    ÷CLASS wird durch eine vom Benutzer benannte Klasse ersetzt.

    [Nachtrag]

    Ih habe den Generator geändert, dass die Funktionen jetzt wie folgt generiert werden

    #define CONDITION_MATCH 
          IsA(term,tmp) /
        | IsB(term,tmp) /

    bool %CLASS::Parse(const char* term, SyntaxNode* root)
    {
        ...
        while(*term)
        {
           if(CONDITION_MATCH)
           {
              /* create nodes here */
           }
           else
             return false;
       }

       return true;
    }
    0
Anmelden zum Antworten