|
|
 |
|
|
| Community » Perl: Allgemeines Forum |
|
 Geschwindigkeitproblem beim Abgleich mit Regexp
|
Seitenanfang |
| Hallo, ich habe folgendes Problem:
Beim Durchgehen einer Datei wird jede Zeile überprüft ob reguläre Ausdrücke anschlagen; falls nicht wird die Zeile übernommen. Das Ganze sieht derzeit so aus:
$text = "";
while(<DATEI>) {
$text.=$_ unless ( /regexp1/ || /regexp2/ || etc...);
}
print $text;
Da die Anzahl der regulären Ausdrücke nach und nach immer weiter wächst, möchte ich sie jetzt aus einer Datenbank in ein Array einlesen und die Zeilen mit den einzelnen Arrayeinträgen vergleichen. Derzeit versuche ich das folgendermaßen:
@regexps;
$text = "";while(<DATEI>) {
$line = $_;
$acceptline = 1; foreach (@regexps) {
if($line =~ /($_)/) {
$acceptline = 0;
last;
}
} if($acceptline == 1) {
$text.=$line;
}
}
Nicht schön, aber es funktioniert. Das Problem: das Programm ist um den Faktor 10 langsamer als das Alte, weil die Überprüfung in der foreach-Schleife mit "if" viel langsamer als der bisherige Ansatz mit "unless" ist. Ich würde mich sehr darüber freuen, wenn mir jemand einen Denkanstoß geben könnte - warum ist die neue Konstruktion derart deutlich langsamer und wie lässt sich das verbessern? Gibt es vielleicht eine Möglichkeit den Abgleich mit dem Array wieder in "unless" unterzubringen? Viele Grüße
Stevie
Datum: 14.08.2007-22:48
|
re: Geschwindigkeitproblem beim Abgleich mit Regexp
|
Seitenanfang |
| Hallo! Zwischen unless und if sollte es keine Geschwindigkeitsunterschiede geben, da unless schließlich nichts anderes als if(! ) ist. Das Problem ist wohl vielmehr, dass du jetzt eine zusätzliche Schleife durchläufst, und viele "kleine" if-Anweisungen abarbeitest. Abgesehen davon: wieviel tausend RAs müssen denn da auf den Text angewendet werden, damit sich ein bemerkbarer Geschwindigkeitsunterschied ergibt? Vlt. könnte man das Programm durch eine Optimierung der regulären Ausdrücke auch noch beschleunigen. Grüße, Skrilax
Datum: 15.08.2007-10:24
|
re: Geschwindigkeitproblem beim Abgleich mit Regexp
|
Seitenanfang |
Hallo,
es handelt sich gerade mal um 70 RAs die nicht weiter optimiert werden können. Für eine 0,5 MB Datei benötige ich jetzt etwa 2 Sekunden, statt 0.16 bisher.
Für einige tausend Dateien würde das viel zu lange dauern.Hast du eine Idee wie man die 70 RAs aus einer Datenstruktur (muß ja kein array sein) abfragen kann, ohne für jede eine extra if-Schleife zu benutzen? Grüße, Stevie
Datum: 15.08.2007-13:47
|
re: Geschwindigkeitproblem beim Abgleich mit Regexp
|
Seitenanfang |
| Hallo! Hab ne Idee, wie man es optimieren könnte: Eine Möglichkeit wäre, sich aus der Datenbank zuerst einen großen RA zusammenzubauen:
use List::Util 'reduce';
my $regexp = reduce { qr#($a)|($b)# } @regexps;
...
while(<DATEI>) {
$text .= $_ unless /$regexp/;
}
Probiere das mal aus. Ich gebe aber keinerlei Garantie auf Bugfreiheit u.ä. Grüße, Skrilax
Datum: 15.08.2007-18:17
|
re: Geschwindigkeitproblem beim Abgleich mit Regexp
|
Seitenanfang |
| Danke für den Tipp, aber leider braucht das Programm jetzt sogar mehr als 5 Sekunden. Es bleibt mir ein Rätsel warum die Ausführung mit unless (/regexp1/ || /regexp2/ || ...) so deutlich schneller ist. Kann es daran liegen, dass der Ansatz mit reduce
(?-xism:((?-xism:((?-xism:((?-xism:(regexp1)|(regexp2)))|(regexp3)))|(regexp4)))|(regexp5))
als regexp (also einen stark verschachtelten) RA erzeugt? Viele Grüße
Stevie
Datum: 15.08.2007-20:15
|
re: Geschwindigkeitproblem beim Abgleich mit Regexp
|
Seitenanfang |
| Interressant. Ich hab mir ein ähnliches Szenario zum Testen hier schnell hergeleitet, hab ich da wohl doch meilenweit die Realität verfehlt. ;) Vlt. Sollte man den RegExp nicht mit qr erstellen, sondern nur als normalen String:
my $ra = reduce { "$a|$b" } @regexps;
Ob die Klammern auch notwendig sind muss man wohl mal ausprobieren. Ich weiß ja nun nicht, welchen Schlages die RAs sind.
Damit lief es bei mir noch nen tick schneller, aber wie gesagt, mein Beispiel scheint wohl nicht ganz passend zu sein.Erstellst du den RegExp auch nur einmal? Oder vlt. bei jeder Datei neu, ohne das es notwendig wäre? (nur so mal ins Blaue geschossen...) Ansonsten hab ich noch auf zwei verschiedenen Wegen versucht, deine erste Variante (/ra/ || /ra/ ...) per eval herzuleiten, aber das war noch langsamer. (hmm, theoretisch sollte es also bei dir dann schneller sein, als Umkehrschluss *scnr*) Grüße, Skrilax
Datum: 15.08.2007-21:43
|
re: Geschwindigkeitproblem beim Abgleich mit Regexp
|
Seitenanfang |
Nuja, hier ist mal ein kleines Testskript, dass drei Lösungsansätze für dein Problem vergleicht, insofern ich dieses richtig verstanden habe. "Schleife" ist deine Variante, "gr_RA" meine erste Variante, "eval_sub" leitet deine allererste Version mit "unless /ra1/ || /ra2/ || /ra3/" her:
use strict;
use warnings;
use Benchmark 'cmpthese';
use List::Util 'reduce';
$| = 1;
chomp(my @regexp = <DATA>);
no warnings; # er beklagt sich sonst über die nur einmalige Nutzung von $a und $b
my $regexp = reduce { $a . '|' . $b } @regexp;
use warnings;
my $ralist = join ' || ' => map { "/$_/" } @regexp;
my $testsub = eval "sub { local \$_ = shift; $ralist }";
my $progress = 0;
use constant {
SUBCOUNT => 3,
RUN => 10000
};
cmpthese(RUN, {
schleife => sub { schleife(\@regexp) },
gr_RA => sub { gr_RA($regexp) },
eval_sub => sub { eval_sub($testsub) },
}
);
sub schleife {
my $arr = shift;
my $result = '';
open my $fh => 'test.txt';
while(my $line = <$fh>) {
my $accept = 1;
$accept = $line !~ /$_/ or last for @$arr;
$result .= $line if $accept;
}
#print $result, "\n" . '-'x10 . "\n";
printf "%i%% (schleife)\r" => 100 * ++$progress / (RUN * SUBCOUNT);
close $fh;
}
sub gr_RA {
my $regexp = shift;
my $result = '';
open my $fh => 'test.txt';
while(my $line = <$fh>) {
$result .= $line unless $line =~ /$regexp/;
}
#print $result, "\n" . '-'x10 . "\n";
printf "%i%% (gr_RA) \r" => 100 * ++$progress / (RUN * SUBCOUNT);
close $fh;
}
sub eval_sub {
my $sub = shift;
my $result = '';
open my $fh => 'test.txt';
while(my $line = <$fh>) {
$result .= $line unless &$sub($line);
}
#print $result, "\n" . '-'x10 . "\n";
printf "%i%% (eval_sub)\r" => 100 * ++$progress / (RUN * SUBCOUNT);
close $fh;
}
__DATA__
Liste
der
regulären
Ausdrücke
Im DATA-Bereich wie gesagt die Liste der reg. Ausdrücke, eine zu kontrollierende Datei sollte als test.txt im Verzeichnis liegen. Für jede Variante wird diese 10000 mal durchlaufen und anschließend die Ausführungsgeschwindigkeiten vergleichen. "gr_RA" war bei mir wie gesagt am schnellsten, bei "eval_sub" ist dann wohl der zusätzliche Subroutinenaufruf der Grund für die Verlangsamung. Grüße, Skrilax
Datum: 16.08.2007-11:55
|
re: Geschwindigkeitproblem beim Abgleich mit Regexp
|
Seitenanfang |
| Wow, da bin ich ja ganz erschlagen - vielen Dank für die Mühe! Das Weglassen der "qr"s durch
<code>
my $ra = reduce { "$a|$b" } @regexps;
</code>
hat die Geschwindigkeit schon mal deutlich verbessert - leider immer noch deutlich langsamer als der originale Ansatz, aber um etwa 35% besser als alles seitdem. :-) Das Ergebniss deines Skriptes ist bei mir allerdings eindeutig:
Rate schleife gr_RA eval_sub
schleife 51.8/s -- -62% -96%
gr_RA 135/s 160% -- -90%
eval_sub 1416/s 2634% 949% -- Dann muß es wohl doch an meinen RAs liegen. Die meisten sind etwa der Form
"^Die jüngsten Nachrichten aus unserem Nachrichtenticker" (also relativ lange, fast reine Stringvergleiche uä.).
Aber letztendlich werden die doch von allen 3 Ansätzen gleich verarbeitet!?! Ich kenne mich in Perl dann doch nicht ausreichend aus - kannst du mir sagen wie man eval_sub() so umschreibt, dass er die RAs aus einem Array ausliest - die "__DATA__"-Konstruktion ist mir völlig neu. Falls nicht bleibts bei deinem Ansatz, der ist wenigstens übersichtlicher und schneller als mein Machwerk.
Danke nochmal für die Arbeit, die du dir gemacht hast!
Datum: 16.08.2007-20:42
|
re: Geschwindigkeitproblem beim Abgleich mit Regexp
|
Seitenanfang |
Och, er liest es doch schon direkt aus dem Array raus. Du kannst dir DATA wie ein Filehandle auf eine Textdatei vorstellen, die man im __DATA__-Abschnitt notiert. Ich habe zu Beginn des Skriptes diesen Abschnitt zuerst in ein Array geschrieben, welches bei dir aus der Datenbank kommt.
Die Subroutine erstelle ich per:
my $ralist = join ' || ' => map { "/$_/" } @regexp;
my $testsub = eval "sub { local \$_ = shift; $ralist }";
@regexp ist hier das Array, in dem die regulären Ausdrücke stehen, also die gleiche Ausgangssituation wie bei dir. In $testsub steht danach eine Referenz auf eine Subroutine, welche das gleiche macht, wie vorher dein unless-Konstrukt.Ich hoffe, ich habe alle Klarheiten beseitigt ;) Grüße, Skrilax PS: Interressant, dieser Unterschied. Mein Ergebnis sah nämlich so aus: Rate schleife eval_sub gr_RA
schleife 1852/s -- -86% -92%
eval_sub 12821/s 592% -- -45%
gr_RA 23256/s 1156% 81% -- Naja, bin durchaus ein bisschen gespannt, wie es dann im Ernstfall ist :)
Datum: 16.08.2007-22:53
|
re: Geschwindigkeitproblem beim Abgleich mit Regexp
|
Seitenanfang |
> Ich hoffe, ich habe alle Klarheiten beseitigt ;)
Ach was - es wird mich wahrscheinlich nur noch das Wochenende kosten um 100-prozentig zu verstehen was ich da jetzt wirklich mache. ;-)Habs jetzt jedenfalls hinbekommen - und das Ergebnis ist _überwältigend_ - hier mal die Werte als Übersicht (gemittelt über je 5 Durchläufe auf einer "richtigen" Datei 0,5 MB): Orginal: 0.135s (ohne Datenbankzugriff)
mein erster Ansatz(mit Schleife): 2.143s dein erster Ansatz (mit qr): 5.481s
dein erster Ansatz (ohne qr): 1.393s "eval_sub"-Ansatz: 0.250s Da der Datenbankzugriff etwa 0.130s kostet, bin ich jetzt also genauso schnell wie früher - JUHU! :-) Vielen Dank nochmal für deine Hilfe - das hätte ich ohne dich wahrscheinlich in 10 Jahren nicht hinbekommen!
Datum: 17.08.2007-19:05
|
|
|
|
|
|
|
|
|
