[nylug-workshop] [Reminder] Regular meetings of the Python workshop @ Tue Feb 13 18:00 - 20:00 (2 hrs)

[Peter C. Norton]

On Tue, Feb 13, 2007 at 02:57:28PM -0500, Yusuke Shinyama wrote:
> The biggest problem for now is speed. Because we compare arbitrary
> pairs of strings, it could take O(n^2) times where n is the number of
> log entries to examine. Also, each comparison of two strings takes
> len(s1)*len(s2) computation, so it can be quite slow. Of course
> once regexp patterns are produced, comparing logs with regexps is
> pretty fast. But I'm not sure yet how this is prectically useful.
> Anyway, we will see.

It seems like if a regular expression takes O(n) time to match, you
should compare every string to existing re's first. That could save
you time if you don't do that already and in logs and in web pages it
should make a dent into the O(n^2) behavior by substantially reducing
the length of n. I haven't looked at your code yet, so maybe you're
talking about O(n^2) after this kind of trivial optimization, in which
case... hopefully it's just O(n^2) time and not space, too.

-Peter

-- 
The 5 year plan:
In five years we'll make up another plan.
Or just re-use this one.