Algorithmus in Tabelle umwandeln



  • Hi,

    angenommen ich habe Scripts der Form

    if A > 10 and B = 5
    x = y
    elseif A < 5 and B = 8
    x = z

    Kann auch etwas komplexer sein, auch mit or und evtl. auch Mehrfachverweisen auf die gleiche Variable:

    if A > 10 and A < 20

    Die Bedingungen können sich überlappen und könnten sogar widersprüchlich sein. Und davon jeweils hunderte.
    Theoretisch kann das ganze beliebig komplex sein ( A > B * C), aber die Fälle würde ich komplett ignorieren.

    Jetzt möchte ich daraus eine Art "decision table" oder Graph aufbauen, bei der ich nur noch die tatsächlichen Variablenwerte einsetzen muss, um möglichst schnell das richtige "then" zu finden.
    Man muss auch beachten, dass die Reihenfolge im Script Priorität hat und man nicht einfach die möglichen Blöcke sortieren kann, damit man schnell suchen kann. Man müsste zumindest noch eine Priorität hinterlegen können.
    Mich interessiert vor allem die Performance beim Suchen, allerdings sollte das Aufbauen auch nicht unendlich lange dauern, sonst rentiert sich das am Ende nicht.

    Gibt es dazu irgendwelche Standardverfahren oder Ansätze oder hat vielleicht jemand eine Idee? Ich hatte zwar schon paar Ideen, aber keine, die alle Möglichkeiten abdeckt und auch noch schnell ist..



  • Also willst Du eine kleine Skriptsprache implementieren, oder was? Weil was Anderes habe ich nicht verstanden. Aber du brauchst wahrsch. einen Lexer -> Parser -> AST -> optimieren -> ...



  • Nein, die Scriptsprache haben wir schon seit Jahrzehnten (und so klein ist die nicht). Es geht darum, diesen häufig vorkommenden Spezialfall zu optimieren.

    Zur Zeit wird das so ausgeführt, wie das hingeschrieben wurde, es wird eine Bedingung nach der anderen geprüft.
    Aber sehr häufig ist das was das Script eigentlich macht, die Beschreibung einer Tabelle. Mehrere Spalten oder Variablen sind vorgegeben, und eine weitere wird daraus berechnet (das ist uninteressant).
    Für diesen Fall möchte ich diese Tabelle quasi reverse-engineeren.

    Ganz einfaches Beispiel:

    if a = 10
    x=y
    elseif a = 11
    x=y
    elseif a = 12
    x=y
    ....

    Usw., paar tausend mal. Jetzt könnte man daraus eine sortierte Liste mit den a-Bedingungen machen und mit einer binären Suche schnell rausfinden, welcher von den Branches zutrifft, anstatt tatsächlich tausende von Vergleichen (mit dem ganzen Overhead der Scriptsprache) auszuführen.

    Es ist aber nicht ganz so einfach, sondern schaut eher so aus, wie ich im ersten Post geschrieben habe. Ich versuch das mal zusammenzufassen:

    • Es sind so gut wie immer mehrere Variablen im Spiel
    • Es wird nicht nur auf konkrete Werte verglichen, sondern auch auf größer/kleiner
    • Die Vergleiche können mit und/oder/nicht verknüpft werden

    Hoffe, das ist jetzt verständlicher...



  • Ich bin vielleicht zu doof das Problem zu verstehen (Du willst eine lookup table für x berechnen in Abhängigkeit von mehreren Variablen und tausenden Bedingungen?), aber spontan würd ich sagen: In C oder C++ umschreiben, kompilieren und gut ist. Das wird schnell genug laufen.

    Ist das generierter Code, oder wie kommt man auf den Wahnsinn tausende if-Abfragen untereinander zu haben?

    Für eine Tabelle musst Du die Logik doch garnicht irgendwie analysieren oder übersetzen. Du kannst doch einfach für alle möglichen Werte schauen was als Ergebnis kommt, und diese abspeichern. Bsp:

    int a = 7; // variabel
    int b = 2; // variabel
    int x; // output
    
    if a < 3 or b > 0
       x = 1
    elseif a == 5
      x = 2
    elseif a > 5 and b < 2
     x = 3
    else
    x = 4
    

    -->

      a  |  b  |  x  |
    --------------------
    7      2     1
    1      1     1
    5     -1     2
    .... usw.
    

    Ansonsten kann ich leider auch nicht weiterhelfen, aber ich würde das einfach in C++ implementieren.



  • @harteware sagte in Algorithmus in Tabelle umwandeln:

    Ich bin vielleicht zu doof das Problem zu verstehen (Du willst eine lookup table für x berechnen in Abhängigkeit von mehreren Variablen und tausenden Bedingungen?)

    Ich bin wohl eher zu doof, das zu erklären. Ich arbeite schon seit Jahren damit und kann wohl schlecht nachvollziehen, welche Informationen andere brauchen. Aber ich denke, das mit der Lookup Tabelle hast du schon richtig verstanden.

    Es geht nicht um ein Script, sondern um hundert tausende 😉 Das ist Teil eines Systems zum Aufbau von parametrischen Modellen. Basiert teilweise auf irgendwelchen alten DIN und VDA Normen. Damit haben Kunden selber ihre Modelle aufgebaut.
    Meist ist das auch nicht schlimm, sondern echt praktisch. Man kann Parameter in Abhängigkeit von anderen Parametern definieren und das ist eben die Sprache, um das zu tun. Vieles lässt sich durch einzeilige Scripte erledigen.
    Nur sind es mit der Zeit immer mehr geworden, die immer komplexere Regeln damit abgebildet haben. z.B. irgendwelche Bestellnummern oder ähnliches. "Wenn Typ A und Größe zwischen 10 und 20, dann... Aber wenn Größe doch größer als 20, dann...".

    Ist ja im Grunde egal. Jedenfalls ist das ein Werkzeug, das schon seit Jahrzehnten im bei vielen Kunden im Einsatz ist und daran wollen und können wir auch nichts ändern. Ist nur die Frage, was wir alles optimieren können.

    Das "Analysieren" ist nicht so das Problem, irgendwelche Analysen über den AST Baum haben wir schon öfter drin. Mir fehlt eher die Idee, in welche Datenstruktur man das ganze verpacken könnte.

    Meine Überlegungen gehen in etwa in diese Richtung:

    struct variableEntry {
      std::pair<variant, variant> valueInterval;
      std::vector<int> branchIndices;
      someEnum conjunction;
    };
    

    Davon könnte man pro Variable eine sortierte Liste anlegen, nach dem kleineren Wert im Interval (z.B. > 5 => 5...max) sortieren und damit schon mal für einen konkreten Wert schnell den richtigen Eintrag finden. Über die branchIndices könnte man das mit anderen Variablenbedingungen verknüpfen.
    Aber wie man die Verknüpfung machen könnte, habe ich noch nicht so wirklich raus. Wie unterscheide ich z.B. und und oder? Oder was mache ich, wenn zweimal die gleiche Variable benutzt wird (a > 5 and a < 10)?


Log in to reply