string::find complexity.

[Dhruv Matani]

Here are the results for the tests on my system:

The format is as follows:
<what string is being searched for in which string>
Time taken for:
1. n^2 algo. re-implemented.
2. string::find.
3. modified KMP.
4. find in terms of std::search -> as suggested by Matt Austern.

The numbers for (1) and (4) are the best in most cases. However, (1)
does not come out a winner in all cases, whereas (4) seems to be the
best for the general case.

Run on AMD-Duron 1GHZ, DDR RAM, x86-Linux, gcc-3.4.1.

On Thu, 2004-06-10 at 23:10, Matt Austern wrote:
> On Jun 9, 2004, at 11:05 PM, Dhruv Matani wrote:
> 
> > Hello,
> > 	I wanted to know why the string::find(string pos, n) function is
> > implemented as O(n^2), instead of the KMP algorithm which is much
> > faster?
> 
> There are really two questions here.
>   (1) Why is string::find implemented from scratch, instead of just
>          implemented as a thin wrapper around std::search()?
>   (2) Why doesn't either of them use KMP?
> 
> The answer to the first question: no good reason that I can think
> of.  std::string::find and std::search both do substring matches.
> It shouldn't be implemented twice.  Doing it once means that
> whatever bug fixes and performance tweaks you make apply
> in more places.


> The answer to the second question: Alex Stepanov deliberately
> decided to use a worst-case-quadratic algorithm for std::search,
> instead of KMP, because he believed that the quadratic case
> was rare in practice and that in typical cases the worst-case-
> quadratic algorithm was faster.  The last time anyone tried to
> measure this (this was work by Dave Musser and John
> Wilkinson, maybe five years ago), they found that Alex was right.
> But they also found that there were some clever performance
> improvements that would make substring matching even faster.
> Those improvements are there in std::search but not in the
> simple hand-written std::string::find.
> 
> So my advice: rewrite std::string::find so that it uses search.
> You'll have to use the version that takes a function object,
> of course, because of the traits template parameter.  Don't
> rewrite std::search in terms of KMP unless you have numbers
> to prove that it's always an improvement---and I think you won't
> find that.  If you want to implement KMP then implement it as
> a separate algorithm that people can use when they care more
> about worst-case complexity than about complexity in the
> common case.

Yes, I guess you are right! The numbers do agree with you, and
string::find is the slowest of all the algorithms tested.

-- 
        -Dhruv Matani.
http://www.geocities.com/dhruvbird/

Proud to be a Vegetarian.
http://www.vegetarianstarterkit.com/
http://www.vegkids.com/vegkids/index.html

-------------- next part --------------
A non-text attachment was scrubbed...
Name: str_find.cpp
Type: text/x-c++
Size: 2973 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20040611/8c6ef85e/attachment.bin>
-------------- next part --------------
[dhruv@localhost test]$ compile str_find.cpp v4 -O3
The Compiler command passed is: g++34 -Wall -O3 -o str_find str_find.cpp
[dhruv@localhost test]$ ./str_find 
Searching for: aabbaabbc*** in: aabbaabbaaxd adbffdadgaxaabbbddhatyaaaabbbaabbaabbcsy
Time taken: 1.03 seconds.
42
Time taken: 1.47 seconds.
42
Time taken: 1.13 seconds.
42
Time taken: 1.06 seconds.
42
Searching for: aabbb*** in: aabbaabbaaxd adbffdadgaxaabbbddhatyaaaabbbaabbaabbcsy
Time taken: 0.57 seconds.
24
Time taken: 0.86 seconds.
24
Time taken: 0.54 seconds.
24
Time taken: 0.5 seconds.
24
Searching for: xd*** in: aabbaabbaaxd adbffdadgaxaabbbddhatyaaaabbbaabbaabbcsy
Time taken: 0.12 seconds.
10
Time taken: 0.39 seconds.
10
Time taken: 0.16 seconds.
10
Time taken: 0.09 seconds.
10
Searching for: very*** in: dhruv is a very very good boy ;-)
Time taken: 0.21 seconds.
11
Time taken: 0.42 seconds.
11
Time taken: 0.17 seconds.
11
Time taken: 0.14 seconds.
11
Searching for: bad*** in: dhruv is a very very good boy ;-)
Time taken: 0.26 seconds.
4294967295
Time taken: 1.02 seconds.
4294967295
Time taken: 0.37 seconds.
4294967295
Time taken: 0.17 seconds.
33
Searching for: extra irritating*** in: dhruv is a very very good boy ;-)
Time taken: 0.29 seconds.
4294967295
Time taken: 0.61 seconds.
4294967295
Time taken: 0.42 seconds.
4294967295
Time taken: 0.2 seconds.
33
Searching for: this is a very long sentence*** in: this is a very this is a very this is a verty this is a very this is a very long sentence
Time taken: 1.06 seconds.
61
Time taken: 2.16 seconds.
61
Time taken: 0.98 seconds.
61
Time taken: 0.88 seconds.
61