Mail Thread Index

[Andreas Schamanek <schamane@fam.tuwien.ac.at>]

Servus allerseits!

On Mon, 21 Jul 2008, at 12:44, Edgar Holleis wrote:

> Am Sonntag, den 20.07.2008, 22:08 +0200 schrieb Andreas Schamanek:
> > Hat jemand eine Idee, wie es kommen kann, dass die Laufzeiten von 
> > _grep -f_ exponentiell mit der Größe des Pattern-Files wachsen?

> * Probiers mal mit "LANG=C grep....". Vielleicht ist das wieder einmal
>   ein Unicode-Problem von grep.

Gute Idee, aber nein. Macht keinen Unterschied.

> * Versuche einmal statt einem Pattern-File eine einzige große Regex
>   mittels (part1)|(part2)|(part3) zusammen zu bauen.

Es ließe sich natürlich machen, aber ich fürchte das würde den Rahmen 
der Befehlszeilenlänge sprengen, bevor wir in Zeiten kommen, wo die 
Messgenauigkeit halbwegs brauchbar ist. Und den langsamen Rechner will 
ich dafür nicht verwenden.

> * Bist du sicher, dass das Wachstum exponentiell ist? Ich denke es ist 
>   quadratisch. Hab mich 2 Minuten mit der Curve-Fitting-Toolbox von 
>   Matlab gespielt ... Also eher quadratisch. 

Vielen Dank für den Hinweis. Ich hätt das natürlich selbst vorher 
überprüfen sollen, bin aber schlicht nicht auf die Idee gekommen, dass 
die Kurven gar nicht exponentiell sind.

> Wo die quadratische Komplexität herkommt, weiß ich allerdings auch 
> nicht.

Ich vermute, dass ein Optimierungscode drinnen ist, der bei kleineren 
Pattern-Files effizienter ist. Wenn ich wissen möchte, ob eine 
Input-Zeile in der Menge der Patterns enthalten ist, tue ich mir 
leichter, wenn ich die Patterns "sortiere". Und das wäre dann auch 
nicht untypisch für quadratische Komplexität.

Der Source-Code ruft :)

Wenn ich mit meiner Vermutung richtig liege, sollte _grep_ einen 
Schalter haben, mit dem sich diese Optimierung abschalten lässt, da ja 
in der derzeitigen Version ab einer gewissen Größe des Pattern-Files 
mehrere Durchläufe mit Teilen des Pattern-Files in Summe schneller 
sind als 1 Durchlauf mit dem ganzen.


Cheerio,

-- 
-- Andreas