RegEx zu langsam

  • C#

Es gibt 11 Antworten in diesem Thema. Der letzte Beitrag () ist von Artentus.

    RegEx zu langsam

    Hallo mal wieder.

    Vielleicht habt ihr mitbekommen, dass ich vor kurzem einen Formelparser für meine MathUtils geschrieben habe. Der Funktioniert auch sehr schön, so wie er soll. Ich habe aber gerade bemerkt, dass die Ausführungsgeschwindigkeit meines Algorithmus' etwa 5 mal langsamer ist, als beim Quadsoft Expressionparser, und 10 mal langsamer, als bei Telcromes MathPro. Ich konnte die Ursache dafür bereits lokalisieren, und zwar ist es RegEx.
    Ich parse den Eingabestring mit RegEx in die einzelnen Tokens, die dann per shunting-yard-Algorithmus in Postfixnotation umgestellt werden und rechne diese dann aus. Laut meinen Messungen benötigt RegEx über die Hälfte der Ausführungszeit. Die genannte Stelle sieht so aus:
    Spoiler anzeigen

    C#-Quellcode

    1. private static List<string> GetInfixTokens(string term)
    2. {
    3. //Leerzeichen entfernen und in Kleinbuchstaben konvertieren
    4. term = term.Replace(" ", string.Empty).ToLowerInvariant();
    6. var tokens = new List<string>();
    8. //mit RegEx alle Zahlen aussortieren
    9. var r = new Regex(@"(?<number>[0-9]+(\" + CultureInfo.CurrentCulture.NumberFormat.NumberDecimalSeparator + @"[0-9]+){0,1}(e[+\-]{0,1}[0-9]+){0,1})"); //(@"(((?<=(\(|^))(?<sign>[+\-]{0,1}))|(?<=.))(?<number>([0-9]+)(\.[0-9]+){0,1})");
    10. var numbers = r.Matches(term);
    11. term = r.Replace(term, "1");
    13. //Term in Tokens teilen
    14. var possibleTokens = new string[] { "+", "-", "*", "/", "^", "%", "sqrt", "root", "sin", "cos", "tan", "asin", "acos", "atan", "sinh", "cosh", "tanh", "ln", "log", "abs", "int", "(", ")", ";", "pi", "e" };
    15. var numberIndex = 0;
    16. while (term.Length > 0)
    17. {
    18. var validToken = false;
    20. //Zahlen prüfen
    21. if (term.StartsWith("1"))
    22. {
    23. tokens.Add(numbers[numberIndex].Groups["number"].Value);
    25. numberIndex++;
    27. if (term.Length > 1)
    28. term = term.Substring(1);
    29. else
    30. term = string.Empty;
    32. validToken = true;
    33. }
    35. //Operatoren, Klammern und Funktionen prüfen
    36. foreach (var token in possibleTokens)
    37. if (term.StartsWith(token))
    38. {
    39. if ((token == "+" || token == "-") && (tokens.Count == 0 || tokens.Last() == "(")) //Vorzeichen
    40. {
    41. if (token == "-")
    42. tokens.Add("!");
    43. }
    44. else if (token == "pi") //PI
    45. tokens.Add(System.Math.PI.ToString());
    46. else if (token == "e") //e
    47. tokens.Add(System.Math.E.ToString());
    48. else
    49. tokens.Add(token);
    51. if (term.Length > token.Length)
    52. term = term.Substring(token.Length);
    53. else
    54. term = string.Empty;
    56. validToken = true;
    57. break;
    58. }
    60. //Token nicht bekannt
    61. if (!validToken)
    62. throw new ArgumentException("Dieser Term enthält einen ungültigen Token.");
    63. }
    65. return tokens;
    66. }

    Wie ihr seht filtere ich mit RegEx alle Zahlen im Term raus und ersetze sie durch ein Zeichen, dass ich dann im Tokenizing-Schritt bequem auslesen kann.

    Meine Frage ist jetzt: kann ich den RegEx-Aufruf durch irgendwas anderes ersetzen bzw. das Tokenizing komplett anders gestalten? Mir ist nichts anderes eingefallen.
    Edit: mir geht es um die Zeilen 9, 10 und 11.

    Erstell nicht immer eine neue Instanz sondern generier und kompilier ein Pattern und check immer mit derselben Instanz. Das sollte schon einiges raushauen.

    Ich probiers mal und melde mich dann wieder.
    Danke schon mal im Voraus.

    Edit:
    Vielen Dank, das hat die Geschwindigkeit von RegEx verzehnfacht. :thumbsup:
    Nur blöd, dass jetzt die erste Ausführung noch langsamer ist. :|

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Artentus“ ()

    Das kann auch an .Net liegen. Der CLI-Code muss auch einmal auf der Maschine kompiliert werden. AFAIK wird der Code erst dann kompiliert, wenn er benötigt wird. Der erste Durchgang dauert dann überall n bisschen, aber beim zweiten Mal wo ein Code genutzt wird ist er schon kompiliert.

    Dann liegt es am Kompilieren vom Regex. Siehe im Link von @Rinecamo:

    MSDN schrieb:

    Compiled: Gibt an, dass der reguläre Ausdruck in eine Assembly kompiliert wird. Dies beschleunigt zwar die Ausführung, verlängert jedoch die Ladezeit. Dieser Wert sollte der Options-Eigenschaft nicht zugewiesen werden, wenn die CompileToAssembly-Methode aufgerufen wird.

    ich hab ma iwo gelesen, dass man regexe nie kompilieren soll, weil das viel Resource belegt, die aus ieinem Grund ühaupt nicht mehr freigegeben werden (muß eiglich ein DesignFehler sein)

    Ansonsten ist doch nicht wichtig, wie schnell ein Expression-Parser parst - deswegen hängt doch keine App.

    @ErfinderDesRades: Es sollte nicht, wenn richtig genutzt ;) Da das aber sicherlich irgendwie verschachtelt sein wird, wenn es hier um ne Infixgenerierung geht, macht es IMO Sinn zu kompilieren. Das fehlende Freigeben ist wirklich eine Designfehler, wenn der Fehler existiert. Sagt mir nichts.

    ich würd jetzt auch nochmal nachfragen, ob Artentus auch den ersten Teil deines Vorschlags umgesetzt hat, also nicht in jedem Aufruf einen neuen Regex erstellen.

    zum Designfehler: der 3. google-treffer von ".net regex compile" - sogar auf msdn: msdn.microsoft.com/de-de/library/8zbs0h2f.aspx


    (cool! - .CompileToAssembly! da kannich auch noch was boosten, ich hab nämlich auch Regex-Performance-Probleme) :thumbsup:

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „ErfinderDesRades“ ()

    @ErfinderDesRades
    Ja, es wird jetzt nur noch eine Instanz erstellt.
    Und CompileToAssembly ist ja nur bedingt von Vorteil, da man dann für jeden Ausdruck eine eigene DLL mitliefern muss, oder? Oder gibts da ne Möglichkeit, den kompilierten Code dann in die eigene Anwendung zu integrieren?

Facebook
Telefonspende