string::find complexity.
Paolo Carlini
pcarlini@suse.de
Thu Jun 10 16:26:00 GMT 2004
Ian Lance Taylor wrote:
>How bad is bad, and how much do we care? There are certainly cases
>where KMP loses quite badly. Consider a pattern of length 100 and
>text of length 101. Suppose all the characters in the pattern are
>different. If the pattern does not match at the head, the current
>algorithm does at most one extra compare. With KMP you spend a lot of
>time building an automaton, and you still do one extra compare. I'm
>sure the overall time would be much worse (especially in the micro
>benchmarks you've been using).
>
Thanks. We should really implement both the algorithm and your suggestion
and compare. Still, a linear complexity instead of a quadratic complexity
seems appealing...
About micro benchmarks... I'm reading a tad of irony in your remark...
well I don't think I had to trade so often a coefficient for an exponent,
for instance. If you have interesting larger scale testcases, would by
very welcome of course!
Thansk again,
Paolo.
More information about the Libstdc++
mailing list