Re: string::find complexity.

[Dhruv Matani <dhruvbird at gmx dot net>]

Hi,
	Well, I have implemented a rough version of the KMP algorithm and it's
given in the attached file. You can run it to compare timings between:
1. The traditional n^2 algo. (re-implemented).
2. string::find -> very slow, because it uses traits::compare.
3. KMP -> probably final version.

(3) Is not copy-book KMP, but a modified version, which I have conjured
up to make a speed up.

A few hours ago, when I tested on g++3.4, (3) was giving better timings,
but that tree has become corrupted because of my allocator testing, and
on 3.2, (1) is giving the best timings.

I would like to know the performance on different machines. I've tested
on an AMD Duron-1GHz -> Uni-processor, DDR RAM. x86-Linux.

Currently, string::find is implemented using traits::compare, which does
a 3-way compare, using 2-comparisonsas does memcmp, so that is a
wasteful operation. find could be modified to be like (1) to have a
speedup.

-- 
        -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 <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;
}



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;
}




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);
}