lange Listen vergleichen - Performancefrage

Hallo,

ich möchte eine lange Liste von nicht einheitlichen Strings gegen eine
Liste von Mustern prüfen und das Auftreten der einzelnen Muster darun
zählen (Bots und Suchmaschinen aus Browserliste rausfiltern):

($browsers ist ein Arrayref, welches mittels DBI ermittelt wurde)


foreach my $entry ( @{$browsers} ){
(my $datum,my $browser) = @{$entry};
foreach my $bot(keys %botlist){
$result{$datum}{$bot}++ if $browser =~ /$bot/i;
}
}


Das dauert naturgemäss sehr lange bei mehreren 100 bot-Mustern und
mehreren 100000 Einträgen in $browsers.
Wie bekomme ich hier Performance rein?



Jens

Re: lange Listen vergleichen - Performancefrage

Jens Puruckherr wrote:

> ich möchte eine lange Liste von nicht einheitlichen Strings gegen eine
> Liste von Mustern prüfen und das Auftreten der einzelnen Muster darun
> zählen (Bots und Suchmaschinen aus Browserliste rausfiltern):

> ($browsers ist ein Arrayref, welches mittels DBI ermittelt wurde)

Jeder Eintrag in $browsers soll maximal 1-mal gezählt werden?

> foreach my $entry ( @{$browsers} ){
> (my $datum,my $browser) = @{$entry};
> foreach my $bot(keys %botlist){
> $result{$datum}{$bot}++ if $browser =~ /$bot/i;
> }
> }

foreach my $entry ( @{$browsers} ){
(my $datum,my $browser) = @{$entry};
if (exists $botlist{$browser}) { # direkter Zugriff
$result{$datum}{$browser}++;
}
else { # genauer suchen
foreach my $bot(keys %botlist){
$result{$datum}{$bot}++ if $browser =~ /$bot/i;
}
}
}

> Das dauert naturgemäss sehr lange bei mehreren 100 bot-Mustern und
> mehreren 100000 Einträgen in $browsers.
> Wie bekomme ich hier Performance rein?

Möglichst wenig über die Schleife suchen, und Deine Browserstrings so
wählen, dass sie möglichst oft direkt als Key im Hash gefunden werden
können. Ich hab sowas ähnliches mal für mehrere 1000 Muster und mehrere
Mio. Einträge gebastelt, und dafür die Muster strukturiert in einem
HashOfHash abgelegt. Laufzeit unter ca. 20 min. bei 3000 Mustern und 6
Mio. Einträgen (3 GHz CPU).

Helmut Wollmersdorfer

Re: lange Listen vergleichen - Performancefrage

Jens Puruckherr:

> foreach my $entry ( @{$browsers} ){
> (my $datum,my $browser) = @{$entry};
study $browser; # <-- Füge das in dein Skript ein
> foreach my $bot(keys %botlist){
> $result{$datum}{$bot}++ if $browser =~ /$bot/i;

> Das dauert naturgemäss sehr lange bei mehreren 100 bot-Mustern und
> mehreren 100000 Einträgen in $browsers.
> Wie bekomme ich hier Performance rein?

"study" könnte hier helfen. Probier es aus!

LG, Ferry

--
Ing Ferry Bolhar
Magistrat der Stadt Wien - MA 14
A-1010 Wien
E-Mail: bol@adv.magwien.gv.at

Re: lange Listen vergleichen - Performancefrage

Jens Puruckherr schrieb:
> Hallo,
>
> ich möchte eine lange Liste von nicht einheitlichen Strings gegen eine
> Liste von Mustern prüfen und das Auftreten der einzelnen Muster darun
> zählen (Bots und Suchmaschinen aus Browserliste rausfiltern):
>
> ($browsers ist ein Arrayref, welches mittels DBI ermittelt wurde)
>
>
> foreach my $entry ( @{$browsers} ){
> (my $datum,my $browser) = @{$entry};
> foreach my $bot(keys %botlist){
> $result{$datum}{$bot}++ if $browser =~ /$bot/i;
> }
> }

Kann man das nicht ohne Schleife machen?
foreach my $entry ( @{$browsers} ){
(my $datum,my $browser) = @{$entry};
$result{$datum}{$browser}++ if defined $botlist{$browser};
}
(evtl. noch mit lc)

Oder mach ich jetzt einen Denkfehler?


Struppi.

Re: lange Listen vergleichen - Performancefrage

Helmut Wollmersdorfer schrieb:
> Jens Puruckherr wrote:
>
>> ich möchte eine lange Liste von nicht einheitlichen Strings gegen eine
>> Liste von Mustern prüfen und das Auftreten der einzelnen Muster darun
>> zählen (Bots und Suchmaschinen aus Browserliste rausfiltern):
>
>> ($browsers ist ein Arrayref, welches mittels DBI ermittelt wurde)
>
> Jeder Eintrag in $browsers soll maximal 1-mal gezählt werden?

im ergebnis kommt dann sows raus ($result):

$VAR1 = { '10.1.2007' => {
'wisenutbot' => 12,
'mediapartners\\-google' => 23,
'ia_archiver' => 693,
'googlebot' => 29709,
'holmes' => 3,
'msnbot' => 329,
'arks' => 1,
'^voyager\\/' => 5,
'slurp' => 9252,
'nagios' => 645,
'echo' => 22,
'gigabot' => 182,
'zyborg' => 12,
'jeeves' => 7,
'jobo' => 1,
'henrythemiragorobot' => 4,
'msiecrawler' => 1,
'baiduspider' => 2,
'voila' => 1
},



> foreach my $entry ( @{$browsers} ){
> (my $datum,my $browser) = @{$entry};
> if (exists $botlist{$browser}) { # direkter Zugriff
> $result{$datum}{$browser}++;

Das wird nicht funktionieren, $browser ist der komplette Browserstring,
$bot ein Kürzel. Da gibt es keinen Match.

>
> Möglichst wenig über die Schleife suchen, und Deine Browserstrings so
> wählen, dass sie möglichst oft direkt als Key im Hash gefunden werden
> können.

Die Browserstrings gibt das Leben vor :-)



Jens

Re: lange Listen vergleichen - Performancefrage

Jens Puruckherr wrote:
> im ergebnis kommt dann sows raus ($result):
>
> $VAR1 = { '10.1.2007' => { 'wisenutbot' => 12,
> 'mediapartners\\-google' => 23,
> 'ia_archiver' => 693,
> 'googlebot' => 29709,
> ...
> Das wird nicht funktionieren, $browser ist der komplette Browserstring,
> $bot ein Kürzel. Da gibt es keinen Match.
> ...
>
> Die Browserstrings gibt das Leben vor :-)

Aha, ich beginne zu verstehen. Die Ausgangsdaten
sind eine Art logfile, welches in einer db gelandet
ist - und du willst einfach die bot-hits auszählen.

Nun, dann wird es relativ simpel. ich habe zwar keine
db für logfiles, aber dafür richtige logfiles, das
ist dann nur ein Implementationsdetail.

Wenn Du wirklich so viele Datenzeilen hast (mehrere 100000),
solltest Du keinesfalls versuchen, die aus der db gelesenen
daten erst in ein Feld von Feldern zu verpacken - sondern
die db-Zeilen sofort zu verarbeiten. Den rest erledigst Du,
in dem Du die bot-strings in eine Regex verpackst, siehe:

use strict;
use warnings;

my @botlist = qw'
wisenutbot mediapartners-google ia_archiver googlebot
holmes msnbot arks ^voyager/ slurp nagios echo gigabot
zyborg jeeves jobo henrythemiragorobot msiecrawler
baiduspider voila
';

my $botreg = '(' . +(join '|', map quotemeta, @botlist) . ')';
my $browsers = []; # not needed
my $result = {};

# read logfile from db or fs
open my $fh, '<', 'myserver.log' or die "WTF! $!";
while ( <$fh> ) {
my ($t, $b) = /\[(.+?)\].+?\"([^"]*)\"$/; # fuer: Apache2 "CustomLog combined"
$result->{ $1 }++ if $b=~/$botreg/i; # keine Schleife mehr noetig
}
close $fh;

print map "$_ - $result->{$_}\n", keys %$result;


Viele Grüße

Mirco

Re: lange Listen vergleichen - Performancefrage

Ferry Bolhar wrote:
> Jens Puruckherr:
>>
>>foreach my $entry ( @{$browsers} ){
>> (my $datum,my $browser) = @{$entry};
>
> study $browser; # <-- Füge das in dein Skript ein
>
>> foreach my $bot(keys %botlist){
>> $result{$datum}{$bot}++ if $browser =~ /$bot/i;
>
>>Das dauert naturgemäss sehr lange bei mehreren 100 bot-Mustern und
>>mehreren 100000 Einträgen in $browsers.
>>Wie bekomme ich hier Performance rein?
>
> "study" könnte hier helfen. Probier es aus!

Zusätzlich die $bot-Strings mit qr// vorab kompilieren
und diese beim Pattern-Match verwenden. Diese kompilierten
Regexes hältst Du parallel zu den $bot-Strings.

Grüße
Frank
--
Dipl.-Inform. Frank Seitz; http://www.fseitz.de/
Anwendungen für Ihr Internet und Intranet
Tel: 04103/180301; Fax: -02; Industriestr. 31, 22880 Wedel

Re: lange Listen vergleichen - Performancefrage

J. Strübig schrieb:

> Kann man das nicht ohne Schleife machen?
> foreach my $entry ( @{$browsers} ){
> (my $datum,my $browser) = @{$entry};
> $result{$datum}{$browser}++ if defined $botlist{$browser};
> }
> (evtl. noch mit lc)
>
> Oder mach ich jetzt einen Denkfehler?

ähm, ja.
Die Bot-Muster entsprechen nicht der kompletten Browser-Zeile.

Jens

Re: lange Listen vergleichen - Performancefrage

Ferry Bolhar schrieb:


> "study" könnte hier helfen. Probier es aus!

Die Zeiten mit und ohne 'study' unterscheiden sich leider kaum.

Was solls, ich forsche noch etwas weiter.
Da ich annehme, dass ein Browserstring nur auf einen Bot matcht, kann
ich ja einmal gefundene Matches zwischenspeichern und diese direkt zum
hochzählen verwenden. Nur unbekannte Browserstrings werden dem Matching
unterworfen - genau einmal, dann landen Sie in der Liste der bekannten.
oder so..

Jens

Re: lange Listen vergleichen - Performancefrage

Kannst Du nicht direkt in der DB arbeiten lassen? (mit entsprechenden
SELECT-Statements). Das duerfte noch das schnellste sein.

Re: lange Listen vergleichen - Performancefrage

Jens Puruckherr wrote:
> Ferry Bolhar schrieb:
>>
>>"study" könnte hier helfen. Probier es aus!
>
> Die Zeiten mit und ohne 'study' unterscheiden sich leider kaum.
>
> Was solls, ich forsche noch etwas weiter.

Wie gesagt, kompiliere die Pattern vorab mit qr//.
Sowas:

foreach my $bot(keys %botlist)

....sollte man ebenfalls nur einmal vorab machen und nicht 100000 mal.

Ungefährer Code (ungetestet):

@bot = keys %botlist;
@pat = map { qr/$_/i } @bot;
...
for (my $i = 0; $i < @bot; $i++)
{
$result{$datum}{$bot[$i]}++ if $browser =~ /$pat[$i]/;
}

Grüße
Frank
--
Dipl.-Inform. Frank Seitz; http://www.fseitz.de/
Anwendungen für Ihr Internet und Intranet
Tel: 04103/180301; Fax: -02; Industriestr. 31, 22880 Wedel

Re: lange Listen vergleichen - Performancefrage

Frank Seitz schrieb:

> Jens Puruckherr wrote:
> > Ferry Bolhar schrieb:
> >>
> >>"study" könnte hier helfen. Probier es aus!
> >
> > Die Zeiten mit und ohne 'study' unterscheiden sich leider kaum.
> >
> > Was solls, ich forsche noch etwas weiter.
>
> Wie gesagt, kompiliere die Pattern vorab mit qr//.
> Sowas:
>
> foreach my $bot(keys %botlist)
>
> ...sollte man ebenfalls nur einmal vorab machen und nicht 100000 mal.
>
> Ungefährer Code (ungetestet):
>
> @bot =3D keys %botlist;
> @pat =3D map { qr/$_/i } @bot;
> ...
> for (my $i =3D 0; $i < @bot; $i++)
> {
> $result{$datum}{$bot[$i]}++ if $browser =3D~ /$pat[$i]/;
> }
>
> Grüße
> Frank

Ich fände interessant zu erfahren, ob die Kombination der Muster, wie
von Mirco Wahab vorgeschlagen, schneller ist. Mit study und qr,
natürlich.
Also:
$pat =3D join("|", map { quotemeta $_ } @bot);
$pat =3D qr/$pat/i;

Re: lange Listen vergleichen - Performancefrage

Ingo Menger wrote:
>
> Ich fände interessant zu erfahren, ob die Kombination der Muster, wie
> von Mirco Wahab vorgeschlagen, schneller ist. Mit study und qr,
> natürlich.
> Also:
> $pat = join("|", map { quotemeta $_ } @bot);
> $pat = qr/$pat/i;

Aha, das war die eigentliche Idee.
Geht man die Pattern in einer Schleife durch, sollte man
noch einen Abbruch (nach Match) einbauen.

Grüße
Frank
--
Dipl.-Inform. Frank Seitz; http://www.fseitz.de/
Anwendungen für Ihr Internet und Intranet
Tel: 04103/180301; Fax: -02; Industriestr. 31, 22880 Wedel

Re: lange Listen vergleichen - Performancefrage

Jens Puruckherr wrote:

> foreach my $entry ( @{$browsers} ){
> (my $datum,my $browser) = @{$entry};
> foreach my $bot(keys %botlist){
> $result{$datum}{$bot}++ if $browser =~ /$bot/i;
> }
> }
>
>
> Das dauert naturgemäss sehr lange bei mehreren 100 bot-Mustern und
> mehreren 100000 Einträgen in $browsers.
> Wie bekomme ich hier Performance rein?

Mal ganz blöd gefragt: @$browsers ist doch bestimmt nicht unique, oder?
Das heisst, es treten doch sicherlich auch doppelte Einträge auf. Da
würde ich mal etwas wie (ungetestet)

my %cache;
for my $entry (@$browsers) {
my ($datum, $browser) = @$entry;
if (exists $cache{ $browser }) {
$result{ $datum }{ $cache{ $browser } }++;
next;
}
for my $bot (keys %botlist) {
my $bot_rx = $botlist{ $bot };
$result{ $datum }{ $bot }++ if $browser =~ /$bot_rx/i;
}
}

Anm: Ich gehe hier mal davon aus, dass die RX als value in %botlist
liegt, nicht als key.

--
# Robert 'phaylon' Sedlacek
# Perl 5/Catalyst Developer in Hamburg, Germany
{ EMail => ' rs@474.at ', Web => ' http://474.at ' }

Re: lange Listen vergleichen - Performancefrage

Frank Seitz schrieb:


> Ungefährer Code (ungetestet):
>
> @bot = keys %botlist;
> @pat = map { qr/$_/i } @bot;
> ...
> for (my $i = 0; $i < @bot; $i++)
> {
> $result{$datum}{$bot[$i]}++ if $browser =~ /$pat[$i]/;
> }

Das bringts!
Laufzeit von 6min auf 1min gesenkt - damit kann man doch was anfangen!
Danke.

Jens

Re: lange Listen vergleichen - Performancefrage

Frank Seitz schrieb:

> Aha, das war die eigentliche Idee.
> Geht man die Pattern in einer Schleife durch, sollte man
> noch einen Abbruch (nach Match) einbauen.

ähm... ja klar
Das macht aus 1,20 min 36 sek.

Ich sage mal: Ziel erreicht.
Danke und schönes Wochenende!

Jens

Re: lange Listen vergleichen - Performancefrage

ReneeB schrieb:
> Kannst Du nicht direkt in der DB arbeiten lassen? (mit entsprechenden
> SELECT-Statements). Das duerfte noch das schnellste sein.

Die DB ist eine hochfreqnetierte Write-fast-only Datenbank.
Solche aufwendigen Queries füren dann u.U. zu anderen Problemen.


Jens.