Irgendeine Möglichkeit, um instapel zu beschleunigen?

Question

Ich versuche auf einem DIMACS zu verwenden instaparse Datei weniger als 700k in der Größe, mit der folgenden Grammatik

<file>=<comment*> <problem?> clause+ 
comment=#'c.*' 
problem=#'p\s+cnf\s+\d+\s+\d+\s*' 
clause=literal* <'0'> 
<literal>=#'[1-9]\d*'|#'-\d+' 

Aufruf wie so

(def parser 
    (insta/parser (clojure.java.io/resource "dimacs.bnf") :auto-whitespace :standard)) 
... 
(time (parser (slurp filename))) 

und es ist etwa hundert Sekunden dauern. Das ist drei Größenordnungen langsamer als ich mir erhofft hatte. Gibt es eine Möglichkeit, es zu beschleunigen, eine Möglichkeit, die Grammatik zu optimieren oder eine Option, die mir fehlt?

Answer 1

Die Grammatik ist falsch. Es kann nicht zufrieden sein.

• Jede file endet mit einer clause.
• Jede clause endet mit einer '0'.
• Die literal in der clause, die eine greedy reg-exp ist, wird essen die endgültige '0'.

Fazit: No clause wird jemals gefunden werden.

Zum Beispiel ...

=> (parser "60") 
Parse error at line 1, column 3: 
60 
^
Expected one of: 
"0" 
#"\s+" 
#"-\d+" 
#"[1-9]\d*" 

Wir analysieren einen literal

=> (parser "60" :start :literal) 
("60") 

... aber kein clause

=> (parser "60" :start :clause) 
Parse error at line 1, column 3: 
60 
^
Expected one of: 
"0" (followed by end-of-string) 
#"\s+" 
#"-\d+" 
#"[1-9]\d*" 

---

W Ist es so langsam?

Wenn es eine comment:

• es kann die ganze Datei schlucken;
• oder bei jedem 'c' Zeichen in aufeinanderfolgende comment s gebrochen werden;
• oder terminieren an einem beliebigen Punkt nach der ursprünglichen 'c'.

Dies bedeutet, dass jeder Schwanz mit dem Rest der Grammatik präsentiert werden muss, die einen reg-exp für literal enthält, die Instaparse nicht nach innen sehen kann.Daher müssen alle ausprobiert werden, und alles wird letztendlich scheitern. Kein Wunder, dass es langsam ist.

---

Ich vermute, dass diese Datei tatsächlich in Linien unterteilt. Und dass Ihre Probleme entstehen, wenn Sie versuchen, Zeilenumbrüche mit anderen Formen von Leerzeichen zu verbinden.

Darf ich vorsichtig darauf hinweisen, dass das Spielen mit ein paar kleinen Beispielen - das ist alles, was ich getan habe - Ihnen eine Menge Ärger erspart hätte.

Answer 2

Ich denke, dass Ihre umfangreiche Verwendung von * das Problem verursacht. Deine Grammatik ist zu zweideutig/ehrgeizig (denke ich). Ich würde zwei Dinge überprüfen:

;;run it as 
(insta/parses grammar input) 
;; with a small input 

, die Ihnen zeigen, wie viel Unklarheit in Ihrer Grammatik Definition lautet: check „mehrdeutig Grammatik“.

Lesen Sie Engelberg performance notes, es würde helfen, Ihr eigenes Problem zu verstehen und wahrscheinlich herauszufinden, was am besten für Sie passt.