Re: cvs: php4 / NEWS /ext/standard string.c

At 09:38 PM 7/20/2001 +0200, Sascha Schumann wrote:

On Fri, 20 Jul 2001, Andrei Zmievski wrote: On Fri, 20 Jul 2001, Sascha Schumann wrote:

    There are a lot cases where the old algorithm is faster (and
    there are cases where Boyer is 3x times faster).  Thus it is
    not really practical to remove the current implementation.

How would the user know in which cases to use Boyer-Moore?

    There is a simple rule: The longer the pattern, the more
    efficient the algorithm becomes.  I've experimented with
    some code which automatically determines which algorithm
    to use, but I have not found a convincing way yet.  The old
    naive implementation is faster than I anticipated.

Yes it is difficult to tell because it is not only a function of the length of the pattern but also a function of what characters and sub-strings have a tendency to repeat themselves and what sub-strings you are likely to search for. Actually the latter is what ends up effecting if a long or short pattern is more efficient. Andi