Re: text_position worst case runtime

Ühel kenal päeval, R, 2006-05-19 kell 18:18, kirjutas Tom Lane:
> Hannu Krosing <hannu(at)skype(dot)net> writes:
> > I guess our regex implementation already uses boyer-moore or similar.
> > Why not just expose the match position of substring('text' in 'regex')
> > using some function, called match_position(int searched_text, int
> > regex, int matchnum) ?
>
> If it did that might be a nice solution, but I'm not sure that it does
> use B-M ... I can't find either "Boyer" or "Moore" in its source code.

Ok, maybe it is not optimised for finding longish strings inside even
longers trings.

I had a (false ?) memory that we used some variant of pcre, and that
pcre uses BM. I may be false on both accounts. (I know that python
borrowed its re module from pcre).

> There's no particular reason to suppose offhand that a regex engine
> would be faster than the naive code for fixed patterns.

if naive code is O(n*m), then starting from some values of n and m it is
probably faster if it is based on somewhat optimised regex engine, the
question is, what is the threasold and dataset for fasterness

--
----------------
Hannu Krosing
Database Architect
Skype Technologies OÜ
Akadeemia tee 21 F, Tallinn, 12618, Estonia

Skype me: callto:hkrosing
Get Skype for free: http://www.skype.com