Ich habe einen Textkörper, den ich einscannen muss und jede Zeile enthält mindestens zwei und manchmal vier Teile Information. Das Problem ist, dass jede Zeile 1 von 15-20 verschiedenen Aktionen sein kann.
in Ruby sieht der aktuelle Code etwa so aus:
%Vor%Das ist offensichtlich "DAS PROBLEM". Ich habe es geschafft, es schneller zu machen (in C ++ um 50%), indem ich alle Regexen zu einem zusammenfasse, aber das ist immer noch nicht die Geschwindigkeit, die ich benötige - ich muss Tausende dieser Dateien SCHNELL analysieren!
Im Moment passe ich sie an Regexes an - aber das ist unerträglich langsam. Ich begann mit Ruby und wechselte zu C ++, in der Hoffnung, dass ich einen Geschwindigkeitsschub bekommen würde und es einfach nicht passiert.
Ich habe beiläufig PEGs und grammatikbasiertes Parsen gelesen, aber es sieht etwas schwierig aus, es zu implementieren. Ist das die Richtung, in die ich gehen sollte oder gibt es unterschiedliche Routen?
Im Grunde analysiere ich die Handhistorien von Poker und jede Zeile der Handhistorie enthält normalerweise 2-3 Bits an Informationen, die ich sammeln muss: wer der Spieler war, wie viel Geld oder welche Karten die Aktion beinhaltete .. etc ..
Beispieltext, der analysiert werden muss:
%Vor%Nachdem ich diese Informationen gesammelt habe, wird jede Aktion in einen xml-Knoten umgewandelt.
Im Moment ist meine Ruby-Implementierung viel schneller als meine C ++, aber das ist wahrscheinlich. Nur weil ich nicht mehr als 4-5 Jahre in c-Code geschrieben habe
UPDATE: Ich möchte hier nicht den gesamten Code posten, aber bis jetzt sehen meine Hände / Sekunde wie folgt aus:
%Vor%Ich teste gerade antlr, um zu sehen, ob wir weiter gehen können, aber im Moment bin ich sehr sehr glücklich mit den Ergebnissen von spirit.
Verwandte Frage: Effiziente Abfrage einer Zeichenfolge gegen mehrere Regexes.
Ich würde vorschlagen
Viel Glück
Boost.Spirit ist eine fantastische Bibliothek, mit der Sie detaillierte Parseranalysen durchführen können, und da der Parser direkt generiert und kompiliert wird Ihr Code sollte viel schneller sein als eine dynamisch berechnete Lösung. Die Syntax wird hauptsächlich mit Expression-Templates (ein Begriff für viele überladene Operatoren) gemacht, was bedeutet, dass Sie sie direkt in Ihren Code schreiben.
Hier ist eine Möglichkeit, dies zu tun, wenn Sie Perl verwenden.
kopiert von perldoc perlfaq6
Für jede Zeile versucht die PARSER -Schleife zuerst, eine Reihe von Ziffern gefolgt von einer Wortgrenze zu finden. Dieses Match muss an der Stelle beginnen, an der das letzte Match abgebrochen wurde (oder am Anfang des Strings beim ersten Match). Da m/ \G( \d+\b )/gcx das Flag c verwendet, wenn der String nicht mit diesem regulären Ausdruck übereinstimmt, setzt Perl pos() nicht zurück und die nächste Übereinstimmung beginnt an der gleichen Position, um ein anderes Muster auszuprobieren.
Siehe Die Anpassung regulärer Ausdrücke kann einfach und schnell sein (aber ist langsam in Java, Perl, PHP, Python, Ruby, ...) . Je nachdem, wie umfangreich Ihre Daten sind und wie komplex Ihre Regex ist, ist es vielleicht einfacher, Ihre eigene Analyse-Logik zu schreiben.
Ich habe beiläufig PEGs und grammatikbasiertes Parsen gelesen, aber es sieht etwas schwierig aus, es zu implementieren. Ist das die Richtung, in die ich gehen sollte oder gibt es unterschiedliche Routen?
Ich persönlich habe PEGs geliebt. Es wird vielleicht ein bisschen dauern, um mit ihnen zufrieden zu sein, aber ich denke, dass sie so viel aufrechterhaltbar sind, dass es ein klarer Gewinn ist. Ich finde, dass Parsing-Code die Quelle vieler unerwarteter Fehler ist, wenn Sie neue Kantenfälle in Eingaben finden. Deklarative Grammatiken mit Nichtterminalen sind für mich leichter zu aktualisieren, wenn dies im Vergleich zu Loop- und Condition-Heavy-Regex-Code geschieht. Die Benennung ist mächtig.
In Ruby gibt es Treetop , welches ein Parser-Generator ist, der PEGs verwendet. Ich fand es kürzlich ziemlich angenehm, einen regex-schweren, handgeschriebenen Parser durch eine kurze Grammatik zu ersetzen.
Überschneiden sich die regulären Ausdrücke immer? Das heißt, wenn zwei oder mehr Regexes mit derselben Zeile übereinstimmen, stimmen sie immer mit verschiedenen Teilen der Zeile überein (keine Überlappung)?
Wenn sich die Übereinstimmungen niemals überschneiden, führen Sie Ihre Suche mit einem regulären Ausdruck durch, der die 15 Regexes, die Sie jetzt haben, kombiniert:
%Vor%Verwenden Sie Erfassungsgruppen, wenn Sie in der Lage sein müssen, zu bestimmen, welche der 15 Regexes übereinstimmt.
Wenn Sie Ihre Daten einmal für einen langen Regex suchen, ist das schneller als 15 mal zu suchen. Wie viel schneller ist abhängig von der Regex-Engine, die Sie verwenden, und der Komplexität Ihrer regulären Ausdrücke.
Versuchen Sie einen einfachen Test in Perl. Lesen Sie über die Funktion "Studieren". Was ich versuchen könnte ist:
Ich habe es nicht versucht, aber es könnte interessant sein.
Eine andere Idee, wenn Sie einen pfiffigen Quad- oder Oct-Core-Server dafür haben.
Erstellen Sie eine Verarbeitungspipeline, die die Arbeit trennt. Stage One könnte Dateien in jeweils ein Spiel oder Hand schneiden und dann jedes in eines der acht Stage Two-Pipes schreiben, die die Daten lesen, verarbeiten und irgendwie produzieren, wahrscheinlich in eine Datenbank auf einem anderen Rechner.
Nach meiner Erfahrung sind diese röhrenbasierten Multiprozess-Designs fast so schnell und viel einfacher zu debuggen als Multi-Threading-Designs. Es wäre auch einfach, einen Cluster von Computern einzurichten, die Netzwerk-Sockets anstelle von Pipes verwenden.
OK, das macht die Dinge klarer (Poker Hand Histories). Ich nehme an, dass Sie ein Statistik-Tool erstellen (Aggressionsfaktor, ging zum Showdown, freiwillig $ in den Pot etc.). Ich bin nicht sicher, warum Sie dafür überhöhte Geschwindigkeiten benötigen; Selbst wenn Sie mit 16 Tischen Multitabling betreiben, sollten die Hände nur mäßig kitzeln.
Ich kenne Ruby nicht, aber in Perl würde ich eine kleine switch-Anweisung machen und gleichzeitig die wichtigen Teile in $ 1, $ 2 usw. bringen. Meiner Erfahrung nach ist das nicht langsamer als das Vergleichen von Strings und dann die Linie mit anderen Mitteln teilen.
%Vor% Ich glaube nicht, dass Sie es wirklich schneller machen können. Setzen Sie die Checks für die Zeilen, die am häufigsten vorkommen, an einer ersten Position (wahrscheinlich die falten-Anweisungen) und diejenigen, die nur spärlich auftreten (neue Hand beginnen, "*** NEXT PHASE ***" ).
Wenn Sie feststellen, dass das tatsächliche Lesen von Dateien ein Flaschenhals ist, können Sie sich vielleicht ansehen, welche Module Sie verwenden können, um große Dateien zu adressieren; für Perl kommt Tie::File in den Sinn.
Stelle sicher, dass du jede Hand nur einmal liest. Lesen Sie nicht alle Daten nach jeder Hand erneut, sondern behalten Sie z.B. eine Hash-Tabelle der Hand-IDs, die bereits analysiert wurden.
Für ein Problem wie dieses würde ich nur meine Augen schließen und einen Lexer + Parser Generator benutzen. Sie können das mit Hand-Optimierung wahrscheinlich schlagen, aber es ist viel einfacher, einen Generator zu verwenden. Außerdem ist es viel flexibler, wenn sich die Eingabe plötzlich ändert.
Tags und Links ruby parsing regex performance peg