Code optimieren (Allgemeines zu Perl)

[thread]7088[/thread]

Code optimieren

Leser: 1

nes

2005-06-29 18:21

User since
2005-01-24
14 Artikel
BenutzerIn
[default_avatar]

Hallo allseits,

ich muss in einer Subroutine erkennen, ob in einem Langtext div. Reg. Expressions vorkommen, wenn ja, muss ich einen vorgegebenen Kurztext zurückliefern (Siehe Codeschnippsel).

Mein Problem ist, dass die Tabelle mit den Rex.Exp die ich dazu benötige schon recht umfangreich wird ( > 300 Einträge ), und dass die Subroutine auf einen grossen Datenbestand angewandt wird => Das Teil wird schon richtig zäh und läuft im Stundenbereich.

Eh kein Wunder, bei einer Million Aufrufe des Unterprogramms a 300 Regular Expressions mach ich 300 Mio. Match-Operationen. Könnte sich das Codeschnippsel bitte jemand ansehen, und ev. den ein oder anderen Tip abgeben, wie man das beschleunigen könnte? Danke!

Code: (dl )

sub search_klassifizierungkurz {
    my ( $word ) = @_;

    my @rfTab = (
                # KurzString, RegExp
        [ "FWHFF", 'Feuerwehr[ \-.\/]'],
        [ "FWHFF", ' FF[ \-.\/]'],
        [ "FWHFF", 'Feuerw\.'],
        [ "FWHFW", "Wasserwehr"],
# viele weitere Einträge ...
    );

    foreach my $i ( @rfTab ) {
        my $suchstr = lc($i->[1]);
        if ( lc($word) =~ /$suchstr/ ) {
            return ($i->[0]);
        }
    }
    return ("");
}

lg., nes

esskar

2005-06-29 18:40

User since
2003-08-04
7321 Artikel
ModeratorIn

user image

hast du dir mal überlegt, selbst mit index und substr zu arbeiten?
vielleicht verbunden mit nem schnellen pattern-matching algorithmus?

nes

2005-06-29 18:58

User since
2005-01-24
14 Artikel
BenutzerIn
[default_avatar]

Hm, das meiste müsste wohl mit index/substr funktionieren. Nur hab ich auch solche Zeilen in meiner derzeitigen Tabelle:

Code: (dl )

        [ "Offene Handelsgesellschaft", '[ \-\/]O\.H\.G[. ]' ],

Also als RegExp den Ausdruck '[ \-\/]O\.H\.G[. ]'

Das finde ich mit "index" nicht mehr, bzw. muesste ich aus dem etliche Suchbegriffe machen:
' O.H.G.'
' O.H.G '
'-O.H.G.'
'-O.H.G '
'/O.H.G.'
'/O.H.G '
... Da werden aus den 300 Einträgen über 1000 ;)

Und was meinst mit "schnellen pattern-matching algorithmus? So wie ich's dzt. mache, mit =~/<suchausdruck>/ ist es doch eh schnell?

Oder missversteh ich Dich grad völlig?

murphy

2005-06-29 19:11

User since
2004-07-19
1776 Artikel
HausmeisterIn

Vermutlich empfiehlt es sich in so einem Fall ersteinmal, all die regulären Ausdrücke mit qr/../ vorzukompilieren, anstatt das in jedem Schleifendurchlauf ständig neu machen zu lassen.

When C++ is your hammer, every problem looks like your thumb.

Strat

2005-06-29 20:22

User since
2003-08-04
5246 Artikel
ModeratorIn

vielleicht hilft auch

Quote
perldoc -f study

was...

aber die fixen mit index suchen, und die RE's vorcompilieren koennte die sache auch ein wenig beschleunigen...

perl -le "s::*erlco'unaty.'.dk':e,y;*kn:ai;penmic;;print"
http://www.fabiani.net/

Crian

2005-07-01 13:25

User since
2003-08-04
5873 Artikel
ModeratorIn

Pack in Deinen Hash die RE's als qr// und gut ist. Das dürfte einen ziemlich Zeitvorteil bringen.
Erst danach würd ich mit substring, index und solchem Kram anfangen, weiter zu optimieren.

Der Hash sollte dann natürlich nicht mehr in der Funtkion stehen, sonst wird er ja doch immer wieder neu aufgebaut.

Am besten packst Du Funktion und Hash in ein eigenes kleines Modul. Dann sind sie beisammen und trotzdem muss der Hash nur einmal aufgebaut werden.\n\n

s--Pevna-;s.([a-z]).chr((ord($1)-84)%26+97).gee; s^([A-Z])^chr((ord($1)-52)%26+65)^gee;print;

use strict; use warnings; Link zu meiner Perlseite

kabel

2005-07-01 17:35

User since
2003-08-04
704 Artikel
BenutzerIn
[default_avatar]

cat /dev/brain:

mittels //i kannst du auf caseinsensitives matching umschalten, ist evtl bissi besser als lc.

wenn du irgendwie an die relativen häufigkeiten der ausdrücke rankommen würdest, dann könntest du das array so anordnen, dass die häufigen ausdrücke zuerst getestet werden. das wird leider nicht so ohne weiteres gehen.

der letzte satz gilt leider auch für diesen vorschlag: wenn sich die ausdrücke in eine prefix-beziehung setzen lassen, dann könntest du diese so anordnen, dass bei manchen ausdrücken erst gar nicht versucht wird, ein matching durchzuführen. beispiel (bezieht sich auf dein kurzes beispiel oben) wenn im satz ("wort") "Feuer" nicht vorkommt, dann kommt garantiert auch nicht "Feuerwehr" vor etc.

schon mal mit grep probiert?

wenn du mehrere rechner zur verfügung hast, dann auch an eine parallelisierung auf mehrere rechner denken @strat, hier wirds zur abwechslung mal funktionieren ;)

-- stefan

Strat

2005-07-01 17:46

User since
2003-08-04
5246 Artikel
ModeratorIn

[quote=kabel,01.07.2005, 15:35]cat /dev/brain:
mittels //i kannst du auf caseinsensitives matching umschalten, ist evtl bissi besser als lc.
[/quote]
$x =~ /.../i ist so gut wie immer langsamer als lc($x) =~ /.../
bei /i kann perl nicht so gut optimieren

[quote=kabel,01.07.2005, 15:35]
wenn du mehrere rechner zur verfügung hast, dann auch an eine parallelisierung auf mehrere rechner denken @strat, hier wirds zur abwechslung mal funktionieren ;)[/quote]
ich bin nicht generell gegen parallelisierung; hier duerfte es vermutlich auch bei mehreren CPUs was bringen. Ich meinte nur, dass eine Parallelisierung auf einer CPU meistens laufzeit kostet (ausser wenn die cpu auf irgendwas warten muss und waehrenddessen schlaeft, z.B. auf antwort aus dem netz); manchmal gewinnt man jedoch durch eine parallelisierung was, was den laufzeitverlust aufwiegt, z.b. dass ein programm mit GUI schneller auf benutzereingaben reagiert oder so.

Wenn ich z.B. ein programm schreiben muesste, das hunderte von http-Abfragen auf remote hosts macht, dann wuerde ich auch bei einer CPU parallelisieren

perl -le "s::*erlco'unaty.'.dk':e,y;*kn:ai;penmic;;print"
http://www.fabiani.net/

esskar

2005-07-01 18:35

User since
2003-08-04
7321 Artikel
ModeratorIn

user image

was auch ein wenig bringen könnte, ist

Code: (dl )

    my ( $word ) = @_;
    my $wordlc = lc $word;
    my @rfTab = (
               # KurzString, RegExp
        [ "FWHFF", 'feuerwehr[ \-.\/]'],
        [ "FWHFF", ' ff[ \-.\/]'],
        [ "FWHFF", 'feuerw\.'],
        [ "FWHFW", "wasserwehr"],
# viele weitere Einträge ...
    );

    foreach my $i ( @rfTab ) {
        my $suchstr = $i->[1]; # ->[1] sollten alle lowercase sein
        if ( $wordlc =~ /$suchstr/ ) {
            return ($i->[0]);
        }
    }
    return ("");
}

kabel

2005-07-01 23:58

User since
2003-08-04
704 Artikel
BenutzerIn
[default_avatar]

wenn die regulären ausdrücke so einfach sind wie die oben, dann kannste auch mal versuchen, mit einem Trie zu arbeiten.
CPAN:

zufällig gibts da was aufm cpan ;)

du müsstest die regulären ausdrücke in die wortmengen auflösen (da hab ich leider nur eines gefunden, was den umgekehrten weg geht). die wörter dann in den trie einbetten. der trie sorgt dann von sich aus für die prefix-beziehung.

-- stefan

View all threads created 2005-06-29 18:21.