linux-l: perl und schnelle Suche

[Steffen Dettmer]

* Ulrich Wiederhold wrote on Sun, Jun 17, 2001 at 23:53 +0200:
> Hallo,
> * Oliver Bandel <oliver at first.in-berlin.de> [010617 21:57]:
> 
> Exakt. Konkretes Beispiel ist:
> Ich habe eine Datei in der alle meine mp3-songs stehen, also z.B.
> Miles_Davis_filenaMe_1
> 
> Wenn jetzt jemand nach Davis oder Miles oder Miles Davis oder
> Miles_DaVis sucht, sollen alle 3 files als Ergebnis ausgegeben werden.

Yep. Das würde mit einem Index gehen.

> Noch besser wäre es, wenn bei "Miles*filename 2" nur Zeile 2 augegeben
> würde.

Sowas kann man nicht mehr effektiv indizieren. Man kann natürlich
über Bestantteile tricksen (also jeweils 5 Buchstabenteilketten
als Indicies verwenden, und den Ausdruck entsprechend teilen),
aber das bringt hier vermutlich gar nichts.

[Array]
> > Ist schneller als ein hash.
> 
> Ich dachte immer, ein hash wäre in dem Fall schneller als ein Array!?

Nein, bei sequentiellem Zugriff ist ein Array i.d.R. schneller
(weil es ja auch eine squentielle Struktur ist). Aber man sollte
in dem Falls eben keinesfalls einen großen Hash sequentiell
durchsuchen. Das kann man höchtes machen, falls man sonst nix
gefunden hat. Machen Datenbanken wohl manchmal auch so. Das
erkennt man daran, daß bestimmte Queries z.B. 1.000 (eintausend)
Mal langsamer sind, als bestimmte andere :)

> Meine beste Lösung war bisher, mittels 'grep -e' direkt in der Datei zu
> suchen, also ohne Perl.

So hab ich mein MP§ Sucher gemacht. 
grep -i -E $wort|less -i -p"$worr"
(Hab dazu aber 36 Zeilen gebraucht :)).

> Problem ist in erster Linie die Performance, die bei >3 Anfragen pro
> Sekunde einfach zu schlecht wird (Suche in > 20000 files sollte möglich
> sein), wenn man in mehreren Channels mit >700 Leuten ist.

Mein P100 (!) braucht 0.5 Sekunden für 4136 Zeilen. Das sind vier
grep Aufrufe (zum Zählen usw. war eben auch so schnell genug).

Perl ist etwa so schnell, wenn ich folgendes mache:

time perl -e 'while(<>) { /xxxworthierxxx/ && print; }' cd_*

Also nur ein "grep", dafür aber 0.1 Sekunden Kompilier-Zeit :)

Wichtig ist zu wissen, wie Deine Suchanfragen i.d.R. aussehen.
Wenn z.B. meistens reguläre Ausdrücke kommen, bringt ein Index
wenig. Wird meistens nach einem Wort gesucht, dann schon mehr. Du
kannst den Index dann geschickt aufbauen, hab sowas mal gemacht,
um Doppelungen zu finden. Nettes Script geworden, kann ich mal
posten, wenn Bedarf. Du mußt in dem Fall die "index_word"
Funktion entsprechend ändern. Denkbar wäre, "ck", "k" usw. immer
als "k" zu indizieren, damit ist beim Suchen dann egal, ob man ck
oder k angibt usw. index_word muß also für gängige Vertipper das
gleiche Resultat produzieren. Der Vorteil daran ist, daß es dann
(beim Suchen) fast egal ist, wie groß Dein Hash ist, ist immer
ziemlich genau gleich schnell.

Wenn Deine Anfragen hingegen kompliziert werden, kannst Du auch
mal über ne Datenbank nachdenken. Vielleicht was von DBI::, da
gibt's übrigens auch Textfiles. Weiß aber nicht, wie schnell das
ist. Hängt eben sehr von den Umständen ab.

oki,

Steffen

-- 
Dieses Schreiben wurde maschinell erstellt,
es trägt daher weder Unterschrift noch Siegel.