Re: string::find complexity.

[Dhruv Matani <dhruvbird at gmx dot net>]

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

#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <time.h>

using namespace std;

struct Timer {
  clock_t begin, end;
  void start() { begin = clock(); }
  void stop() { end = clock(); }
  double operator()() { return static_cast<double>
			  (end-begin)/CLOCKS_PER_SEC; }
};

string::size_type
s_find(const string& data, const string& src)
{
  string::size_type max = src.size();
  string::size_type inner_max = data.size();
  for (string::size_type i = 0; i < max; ++i)
    {
      string::size_type j;
      for (j = 0; j < inner_max; ++j)
	{
	  if (src[i + j] != data[j])
	    break;
	}
      if (j == inner_max)
	return i;
    }
  return string::npos;
}

string::size_type
s_search(const string& data, const string& src)
{
  string::const_iterator i = 
    std::search(src.begin(), src.end(), 
		data.begin(), data.end());
  return (i - src.begin());
}



template <class _Str>
typename _Str::size_type str_find (const _Str& search_for, const _Str& src)
{
  typename _Str::size_type src_size = src.size();
  typename _Str::size_type data_size = search_for.size();
  typename _Str::size_type next_start = 0;
  register typename _Str::size_type i = 0;

  while (i < src_size)
    {
      register typename _Str::size_type j;
      for (j = 0; j < data_size; ++j)
	{
	  if (src[i] != search_for[j])
	    {
	      if (next_start)
		{
		  i = next_start;
		  next_start = 0;
		}
	      else
		if (search_for[0] != src[i])
		  ++i;
	      break;
	    }
	  else
	    {
	      if (j != 0 && next_start == 0 && src[i] == search_for[0])
		next_start = i;
	      ++i;
	    }
	}
      if (j == data_size)
	return (i - data_size);
    }
  return _Str::npos;
}

void
test_pair(string s, string f)
{
  cout<<"Searching for: "<<f<<"*** in: "<<s<<endl;
  Timer t;
  string::size_type sz = 0;

  t.start ();
  for (int i = 0; i < 1000000; ++i)
    sz = s_find(f, s);
  t.stop ();

  cout<<"Time taken: "<<t()<<" seconds."<<endl;
  cout<<sz<<endl;

  t.start ();
  for (int i = 0; i < 1000000; ++i)
    sz = s.find (f);
  t.stop ();

  cout<<"Time taken: "<<t()<<" seconds."<<endl;
  cout<<sz<<endl;

  t.start ();
  for (int i = 0; i < 1000000; ++i)
    sz = str_find(f, s);
  t.stop ();

  cout<<"Time taken: "<<t()<<" seconds."<<endl;
  cout<<sz<<endl;

  t.start ();
  for (int i = 0; i < 1000000; ++i)
    sz = s_search(f, s);
  t.stop ();

  cout<<"Time taken: "<<t()<<" seconds."<<endl;
  cout<<sz<<endl;
}




int main ()
{
  string s, f;

  s = "aabbaabbaaxd adbffdadgaxaabbbddhatyaaaabbbaabbaabbcsy";
  f = "aabbaabbc";
  test_pair(s, f);

  f = "aabbb";
  test_pair(s, f);

  f = "xd";
  test_pair(s, f);

  s = "dhruv is a very very good boy ;-)";
  f = "very";
  test_pair(s, f);

  f = "bad";
  test_pair(s, f);

  f = "extra irritating";
  test_pair(s, f);

  s = "this is a very this is a very this is a verty this is a very this is a very long sentence";
  f = "this is a very long sentence";
  test_pair(s, f);
}

Attachment: str_find_output.txt
Description: Text document