ACHTUNG. Das ist ein Archiv des alten forum.ruby-portal.de. Die aktuelle Mailingliste gibt es auf lists.ruby-lang.org/pipermail/ruby-de.

NOTICE. This is a ready-only copy of the old forum.ruby-portal.de. You can find the current mailing list at lists.ruby-lang.org/pipermail/ruby-de.

Die Programmiersprache Ruby

Blog|

Forum|

Wiki  


Alle Zeiten sind UTC + 1 Stunde [ Sommerzeit ]

Ein neues Thema erstellen Auf das Thema antworten  [ 11 Beiträge ] 
Autor Nachricht
 Betreff des Beitrags: Oniguruma/Regexp performance
BeitragVerfasst: 16 Dez 2007, 23:24 
Offline
Nuby

Registriert: 16 Dez 2007, 22:53
Beiträge: 4
HI,

evtl. toben sich hier Oniguruma Experten rum deshalb die Frage:
Ich habe mal einige Tests mit dem externen Oniguruma lib gemacht unter (ruby 1.8) (wobei das auch auf die alte Regexp engine zutrifft):
Ich verknüpfe viele (ca. 50000) Wörter mit "|", will also ein Matching auf viele Wörter haben. Danach mache ich ein regexp.scan(text).

Ich dachte bisher, dass die Größe des Regexp keine Rolle spielen sollte (Der Automat wird zwar komplexer aber die Geschwindigkeit sollte nicht groß einbrechen).
Wenn ich aber die Anzahl der Wörter erhöhe steigt die Zeit für den Match. Hier mal ein paar Zahlen:
Words: 1000
Textsize: 23000
Matchingtime: Regexp:0.397622 Oniguruma: 0.234323

Words: 2000
Textsize: 23000
Matchingtime: Regexp:0.79058 Oniguruma: 0.48075

Words: 10000
Textsize: 23000
Matchingtime: Regexp:error Oniguruma: 2.249399

Words: 50000
Textsize: 23000
Matchingtime: Regexp:error Oniguruma: 95.113469 !!!!!

mal ein kürzerer Test:
Words: 50000
Textsize: 4600
Matchingtime: Regexp:error Oniguruma: 21.225318

es ist nicht ganz linear....

Schönen Gruß
P

(ich weiß es gibt schönere Strukturen um so was zu machen aber Regexps sind recht flexibel)


Nach oben
 Profil  
 
 Betreff des Beitrags: Re: Oniguruma/Regexp performance
BeitragVerfasst: 16 Dez 2007, 23:37 
Offline
Interpreter

Registriert: 15 Mär 2005, 19:26
Beiträge: 6142
Wohnort: Karlsruhe
popel hat geschrieben:
Ich dachte bisher, dass die Größe des Regexp keine Rolle spielen sollte (Der Automat wird zwar komplexer aber die Geschwindigkeit sollte nicht groß einbrechen).

Die regulären Ausdrücke werden nicht in einen Automaten übersetzt, sondern per Backtracking ausgeführt.

Die Übersetzung in einen Automaten, wie beispielsweise beim Lex, geht nur bei echten regulären Ausdrücken, aber davon sind die in Oniguruma zulässigen Ausdrücke weit entfernt.

Daher gibt es Ausdrücke, die in einen Automaten übersetzt und dann ausgeführt, sehr schnell gehen, die jedoch interpretiert länger dauern können, als das Universum alt ist.

_________________
WoNáDo.set_state!(:retired)


Nach oben
 Profil  
 
 Betreff des Beitrags: Re: Oniguruma/Regexp performance
BeitragVerfasst: 17 Dez 2007, 00:20 
Offline
Interpreter
Benutzeravatar

Registriert: 03 Jul 2006, 14:53
Beiträge: 4872
Wohnort: RLP
popel hat geschrieben:
Wenn ich aber die Anzahl der Wörter erhöhe steigt die Zeit für den Match. Hier mal ein paar Zahlen:
Words: 1000
Textsize: 23000
Matchingtime: Regexp:0.397622 Oniguruma: 0.234323

Words: 2000
Textsize: 23000
Matchingtime: Regexp:0.79058 Oniguruma: 0.48075

Words: 10000
Textsize: 23000
Matchingtime: Regexp:error Oniguruma: 2.249399


Ich finde das ziemlich linear.

Ich habs jetzt nicht mehr genau im Kopf, aber wenn ich mich recht entsinne, war die Auswertungsreihenfolge von | ja von links nach rechts. (Also, weiter links gewinnt, wenn beide Alternativen "passen".

Illustration:



1
2
3
4
5
6
7
8
9
10
11
12
13
14
>> regex = /(\w{3})|(\w{1,3})/
=> /(\w{3})|(\w{1,3})/
>> regex.match("foo")
=> #<MatchData:0x584cb0>
>> $1
=> "foo"
>> $2
=> nil
>> regex.match("fo")
=> #<MatchData:0x57cac4>
>> $1
=> nil
>> $2
=> "fo"


Das gibt natürlich eine Auswertungsreihenfolge vor. Somit ist zu erwarten, dass bei einem relativ gleichverteilten Satz von Wörtern im Text der Aufwand fürs Matchen pro Wort linear mit der Anzahl der Wörter in der Alternative steigt (da ich von links nach rechts alle Alternativen probiere). Das passt da oben doch:

10 mal soviele Wörter in der Alternative benötigen eine zehnfache Laufzeit.

Auch in einem Automaten übersetzt sich das nämlich meines Wissens (korrigiert mich, wenn ich falsch liege) nicht in:



1
2
3
4
5
6

\w{3}
S -------------- Alternative 1
|
| \w{1,3}
------------- Alternative 2


sondern in:



1
2
3
4
5
6
7

\w{3}
S ------------------- Alternative 1
|
|
| !\w{3} \w{1,3}
---------- N -------------- Alternative 2


Das müsste dann auch dem klassischen Backtracking-Verhalten entsprechen.

Gruß
Skade

P.S.:


1
2
3
4
5
6
7
8
Words: 50000
Textsize: 23000
Matchingtime: Regexp:error Oniguruma: 95.113469 !!!!!

mal ein k��rzerer Test:
Words: 50000
Textsize: 4600
Matchingtime: Regexp:error Oniguruma: 21.225318


Das ist auch nicht soo weit weg von Linearität. Spannenderweise wird Oniguruma offenbar sogar schneller. (5 mal soviele Wörter, 4,5-fache Laufzeit). Kann auch am Testdatensatz liegen.


Nach oben
 Profil  
 
 Betreff des Beitrags: Re: Oniguruma/Regexp performance
BeitragVerfasst: 17 Dez 2007, 02:07 
Offline
Interpreter

Registriert: 15 Mär 2005, 19:26
Beiträge: 6142
Wohnort: Karlsruhe
Skade hat geschrieben:
Ich habs jetzt nicht mehr genau im Kopf, aber wenn ich mich recht entsinne, war die Auswertungsreihenfolge von | ja von links nach rechts. (Also, weiter links gewinnt, wenn beide Alternativen "passen").

Genauer gesagt, sobald eine passt, ist das Thema erledigt, ausser wenn später noch ein Backtracking passiert.

Aber, das sollte man nicht vergessen, dass bei...

1
2
s = 'a'*10000
s.match(/^a{10000}x$|^a{10000}$/)
...die Mascine sehr wohl erst einmal 10000 a-s liest ehe sie beim Versuch ein s zu lesen scheitert. Für die zweite Alternative muss sie vollständig zurückgehen. Das fällt nur bei kurzen Texten (<ein paar MB) nicht so auf.

Skade hat geschrieben:
in ... Automaten übersetzt

Es wird daraus ein Automat erstellt, der für jedes gelesene Zeichen in einen neuen Zustand übergeht, und zwar eindeutig (DFA). Daher ist das Verhalten einer derartig aufgebauten Maschine immer linear, maximal quadratisch, falls es, wie beim Lex, look-ahead gibt.

Allerdings lassen sich bei einem Automaten keine Gruppierungen getrennt erkennen. Man kann zwar klammern, nur hat das nichts mit einer Zuweisung des Teilausdrucks an eine Variable zu tun.

Falls jemand von Euch das Drachenbuch zur Hand hat - da sind sehr schön und verständlich die zugehörenden Algorithmen beschrieben.

Einen Nachteil hat eine Übersetzung in einen Automaten allerdings auch - der kann seeeeeehr gross werden.

_________________
WoNáDo.set_state!(:retired)


Nach oben
 Profil  
 
 Betreff des Beitrags:
BeitragVerfasst: 17 Dez 2007, 02:11 
Offline
Nuby

Registriert: 16 Dez 2007, 22:53
Beiträge: 4
Naja, die Annahme war, dass wenn sie einen richtigen Automaten bauen, was anscheinend nicht der Fall ist, dann wäre die Suchzeit zwar linear zum durchsuchten Text aber nicht linear zur "Größe" des Automaten. Im Idealfall wäre der Automat eine Art Trie (und ich kann auch sagen damit geht es recht schnell).
Schade das versaut mir das Frühstück (obwohl das erst in einigen Stunden ist).

Danke für die Hilfe
P


Zuletzt geändert von popel am 17 Dez 2007, 02:14, insgesamt 1-mal geändert.

Nach oben
 Profil  
 
 Betreff des Beitrags: Re: Oniguruma/Regexp performance
BeitragVerfasst: 17 Dez 2007, 02:13 
Offline
Interpreter
Benutzeravatar

Registriert: 03 Jul 2006, 14:53
Beiträge: 4872
Wohnort: RLP
WoNáDo hat geschrieben:
Falls jemand von Euch das Drachenbuch zur Hand hat - da sind sehr schön und verständlich die zugehörenden Algorithmen beschrieben.


Ich hab den Abschnitt mal gelesen, hatte das Buch aber von der Agentur ausgeliehen, bei der ich zu der Zeit gearbeitet habe. Ich hätts ja gerne mitgenommen, gelesen hats da ja eh keiner :/. Die haben weiter lustig probiert, HTML-Parser mit RegEx aufzubauen.

Aber Backtracking ist mir bekannt, ich muss mich momentan mit dieser hässlichen Sprache Prolog auseinander setzen :/.

Gruß
Skade


Nach oben
 Profil  
 
 Betreff des Beitrags:
BeitragVerfasst: 17 Dez 2007, 02:16 
Offline
Nuby

Registriert: 16 Dez 2007, 22:53
Beiträge: 4
Offtopic:
Prolog ist nicht häßlich nur .... anders (Ich benutze es derzeit für NLP um Syntaxbäume von Sprache zu erstellen und dann mit lustigen Lambdaausdrücken die Semantik zu errechnen).


Nach oben
 Profil  
 
 Betreff des Beitrags:
BeitragVerfasst: 17 Dez 2007, 02:24 
Offline
Interpreter
Benutzeravatar

Registriert: 03 Jul 2006, 14:53
Beiträge: 4872
Wohnort: RLP
popel hat geschrieben:
Offtopic:
Prolog ist nicht häßlich nur .... anders (Ich benutze es derzeit für NLP um Syntaxbäume von Sprache zu erstellen und dann mit lustigen Lambdaausdrücken die Semantik zu errechnen).


Ich finds einen Horror beim debugging und bei den meisten Problemen den Aufwand nicht wert. Aber lass uns das in ein anderes Topic verschieben ;). Ich habe auch durchaus meinen Spass an den CLP-Fähigkeiten von GProlog, was nichts daran ändert, dass die Sprache einfach schon extrem alt ist und man ihr das an mehr als einer Stelle anmerkt. Vielleicht liegts auch einfach nur daran, dass ich eine Implementierung verwende, die nicht so herrlich ist? (ich kann das nicht bewerten, gibts besseres als GProlog?)


Nach oben
 Profil  
 
 Betreff des Beitrags:
BeitragVerfasst: 17 Dez 2007, 10:35 
Offline
Interpreter

Registriert: 15 Mär 2005, 19:26
Beiträge: 6142
Wohnort: Karlsruhe
popel hat geschrieben:
Naja, die Annahme war, dass wenn sie einen richtigen Automaten bauen, was anscheinend nicht der Fall ist...

Das geht bei Oniguruma (wie auch bei Perl) überhaupt nicht, weil das ja im eigentlichen Sinn nichts mehr mit regulären Ausdrücken zu tun hat. Schau doch mal in die Oniguruma-Beschreibung rein, da gibt es Konstruktionen, die Rekursion erlauben.

Ich habe mal in Beispielen (Reguläre Ausdrücke, Teil 5: Benannte Gruppen, Palindrome, Taschenrechner und Klammergebirge.) Oniguruma dafür benutzt die bal-Funktion von Snobol4 zu implementieren...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
module Matchelements
def bal(lpar='(', rpar=')')
raise RegexpError,
"wrong length of left bracket '#{lpar}' in bal" unless lpar.length == 1
raise RegexpError,
"wrong length of right bracket '#{rpar}' in bal" unless rpar.length == 1
raise RegexpError,
"identical left and right bracket '#{lpar}' in bal" if lpar.eql?(rpar)
lclass, rclass = lpar, rpar
lclass = '\\' + lclass if lclass.match(/[\-\[\]]/)
rclass = '\\' + rclass if rclass.match(/[\-\[\]]/)
return "(?<bal>" +
"[^#{lclass}#{rclass}]*?" +
"(?:\\#{lpar}\\g<bal>\\#{rpar}" +
"[^#{lclass}#{rclass}]*?" +
")*?" +
")"
end
end
...und eine Eingabe für einen Taschenrechner zu analysieren...

1
2
3
4
5
6
7
8
pattern = / (?<e>\g<t>\+\g<e>|\g<t>-\g<e>|\g<t>){0}
(?<t>|
\g<f>\*\g<t>|\g<f>\/\g<t>|\g<f>){0}
(?<f>[-+]?
\g<id>|\(\g<e>\)){0}
(?<id>
\g<n>|\g<v>){0}
(?<n>[a-zA-Z_]
\w*){0}
(?<v>
\d+(\.\d+)?){0}
^((?<var>
\g<n>)=)?(?<expr>\g<e>)$
/x
...Das ist deutlich Chomsky-2.

Was ich aber nicht weiss ist, inwieweit Oniguruma optimiert, wenn sich die Möglichkeit bietet. Die Quellen sind nicht sonderlich umfangreich dokumentiert, jedenfalls nicht auf Englisch (Japanische Doku gibt es wahrscheinlich schon - nur - die hilft mir nichts).

_________________
WoNáDo.set_state!(:retired)


Zuletzt geändert von WoNáDo am 17 Dez 2007, 11:15, insgesamt 1-mal geändert.

Nach oben
 Profil  
 
 Betreff des Beitrags: Re: Oniguruma/Regexp performance
BeitragVerfasst: 17 Dez 2007, 10:59 
Offline
Interpreter

Registriert: 15 Mär 2005, 19:26
Beiträge: 6142
Wohnort: Karlsruhe
Skade hat geschrieben:
WoNáDo hat geschrieben:
...das Drachenbuch...

Ich hab den Abschnitt mal gelesen, hatte das Buch aber von der Agentur ausgeliehen, bei der ich zu der Zeit gearbeitet habe. Ich hätts ja gerne mitgenommen, gelesen hats da ja eh keiner :/. Die haben weiter lustig probiert, HTML-Parser mit RegEx aufzubauen.

Seltsam - das ist oft das Schicksal dieser Bücher. Auch die Knuth-Bände stehen an sehr vielen Stellen rum, ohne dass die Leute sie wirklich benutzen. Die müssen wohl oft gegenüber Dritten die Funktion "seht ihr, wie professionell wir hier arbeiten?!" erfüllen.

Dabei ist das Drachenbuch wirklich nützlich. Im damaligen Samos-Projekt (1978-80 - Software Adaption and Maintenance Organisation System) wurden bei uns anhand des ersten Drachenbuchs (nicht so umfangreicher Vorläufer) in BCPL die Tools namens Slex und Syacc gebaut ("S" für Samos, der Rest der Bezeichnung dürfte klar sein). Das Buch kann also nachgewiesenermassen hilfreich eingesetzt werden.

Skade hat geschrieben:
Aber Backtracking ist mir bekannt, ich muss mich momentan mit dieser hässlichen Sprache Prolog auseinander setzen :/.

Ich wusste garnicht, dass Prolog noch immer benutzt wird. Falls Du an regelbasiertem Arbeiten in Ruby interessiert bist - Christian Neukirchen hat vor über einem Jahr diesbezüglich was gemacht. Es handelt sich um solve, welches im Vortrag ab Seite 24 behandelt wird.

_________________
WoNáDo.set_state!(:retired)


Nach oben
 Profil  
 
 Betreff des Beitrags:
BeitragVerfasst: 19 Dez 2007, 17:26 
Offline
Interpreter

Registriert: 15 Mär 2005, 19:26
Beiträge: 6142
Wohnort: Karlsruhe
<Back to Original Topic />
Schau doch mal auf RubyForge nach, ob es irgendein Interface zum Lex oder ein anderes Werkzeug zur lexikalischen Analyse gibt.

Das sollte dann jedes Performance-Problem lösen.

_________________
WoNáDo.set_state!(:retired)


Nach oben
 Profil  
 
Beiträge der letzten Zeit anzeigen:  Sortiere nach  
Ein neues Thema erstellen Auf das Thema antworten  [ 11 Beiträge ] 

Alle Zeiten sind UTC + 1 Stunde [ Sommerzeit ]


Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 2 Gäste


Du darfst keine neuen Themen in diesem Forum erstellen.
Du darfst keine Antworten zu Themen in diesem Forum erstellen.
Du darfst deine Beiträge in diesem Forum nicht ändern.
Du darfst deine Beiträge in diesem Forum nicht löschen.
Du darfst keine Dateianhänge in diesem Forum erstellen.

Suche nach: