Re: Something about sizeof(char)

[Dhruv Matani <dhruvbird at gmx dot net>]

Hi,
	I have attached a test case that compares the performance of the
traditional approach as used in string::find_first_of(), and a different
approach as in the function ffirst_of().

The newer approach uses a temporary stachk array of size 1 <<
__CHAR_BIT__ if __CHAR_BIT__ <= 8, and then performs the operation,
which makes the worst case complexity come down from O(n*m) to O(n+m),
which is an improvement.

I'm not too good at figuring out whether code is portable or not, so I'm
not rally sure that this would be acceptable, so I'd like to hear from
the experts.


On Mon, 2004-06-14 at 21:04, Paolo Carlini wrote:
> Dhruv Matani wrote:
> 
> >Hi,
> >	Is there any way of knowing whether on a platform the sizeof(char)
> >being always one is actually one byte == 8-bits? Or 1 is defined as more
> >than 8-bits.
> >  
> >
> For this there is the predefined macro |__CHAR_BIT__|
> 
> Paolo.
-- 
        -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 <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
ffirst_of(string const& src, string const& f)
{
#if __CHAR_BIT__ <= 8
  char table[1 << __CHAR_BIT__] = { 0 };
  string::size_type sz = f.size();
  string::size_type i;

  for (i = 0; i < sz; ++i)
    table[(unsigned int)f[i]] = 1;

  sz = src.size();

  for (i = 0; i < sz; ++i)
    {
      //Is the entry present?
      if (table[(unsigned int)src[i]] == 1)
	return i;
    }
  return string::npos;
#else
#error Use Traditional Algorithm
#endif
}



void
test_str(string const& src, string const& f)
{
  Timer t;
  const int Max = 200000;
  int sz = 0;

  t.start();
  for (int i = 0; i < Max; ++i)
    sz = src.find_first_of(f);
  t.stop();

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

  t.start();
  for (int i = 0; i < Max; ++i)
    sz = ffirst_of(src, f);
  t.stop();

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


int main()
{
  string src = "some huge string not containing the character after the characher x early on in the "
    "string : x -> d";
  string search_for = "dhruv";

  test_str(src, search_for);

  search_for = "d";
  test_str(src, search_for);

  search_for = "df";
  test_str(src, search_for);

  search_for = "dx";
  test_str(src, search_for);

  search_for = "dxe";
  test_str(src, search_for);

  search_for = "z";
  test_str(src, search_for);
}

Attachment: ffirst_test_output
Description: Text document