Mark Dilger <[EMAIL PROTECTED]> writes:
> The function
>   static int32 text_position(text *t1, text *t2, int matchnum)
> defined in src/backend/utils/adt/varlena.c uses repeated calls to
> strncmp (or pg_wchar_strncmp) to find the location of the pattern in
> the text.  The worst case runtime for such an approach is O(n*m) where
> n and m are the lengths of the pattern and text.  The best case would
> be O(n), I guess, because it only takes n comparisons to find the
> pattern at the very start of the text.  I'm not sure how to determine
> the average case runtime, because it depends what your data looks like
> on average.

I would think that the worst-case times would be fairly improbable.
I'm disinclined to push something as complicated as Boyer-Moore matching
into this function without considerable evidence that it's a performance
bottleneck for real applications.

The question that comes to mind for me is why we're not using simple
strncmp in all cases in that code.  The conversion to pg_wchar format
looks expensive and unnecessary ...

                        regards, tom lane

---------------------------(end of broadcast)---------------------------
TIP 3: Have you checked our extensive FAQ?

               http://www.postgresql.org/docs/faq

Reply via email to