Thread: str_replace && str_find

I'm pretty certain no-one here want's to do your homework....

And if you've already written them yourself, post them up (or links to them if they're too big) so we can try and help optimise them.

Look how many times you're calling strlen()
Call it once for each string and save the result in a local

I know that there are strstr function, but it returns pointer to that string, not it's location.

To determine the position, do this:

Code:

int pos = (strstr(instring, searchstring)-instring);

(That assumes that the string contains what your looking for.)

Code:

char *p;
if(p=strstr(instring, searchstring)) {
    int pos = p-instring;
    printf("String position: %d\n", pos);
}
else {
    /* string not found */
}

A comparison

Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int strfnd1(char *buffer, char *string, unsigned int position)
{
  unsigned int i, ret = 0;

  for (i = position; i < strlen(buffer); i++) {
    if (strncmp(&buffer[i], string, strlen(string)) == 0) {
      ret = i;
      break;
    }
  }
  return ret;
}

/* pre-calculate string lengths */
int strfnd2(char *buffer, char *string, unsigned int position)
{
  unsigned int i, ret = 0;
  unsigned int blen = strlen(buffer);
  unsigned int slen = strlen(string);

  for (i = position; i < blen; i++) {
    if (strncmp(&buffer[i], string, slen) == 0) {
      ret = i;
      break;
    }
  }
  return ret;
}

/* pre-calculate string lengths */
/* only call strncmp if first chars are actually equal (saving function calls) */
int strfnd3(char *buffer, char *string, unsigned int position)
{
  unsigned int i, ret = 0;
  unsigned int blen = strlen(buffer);
  unsigned int slen = strlen(string);

  for (i = position; i < blen; i++) {
    if ( buffer[i] == string[0] &&
         strncmp(&buffer[i], string, slen) == 0) {
      ret = i;
      break;
    }
  }
  return ret;
}

/* using pointer arithmetic */
int strfnd4(char *buffer, char *string, unsigned int position)
{
  unsigned int ret = 0;
  unsigned int blen = strlen(buffer);
  unsigned int slen = strlen(string);
  char *bstart, *bend = buffer + blen;

  for ( bstart = buffer + position; bstart < bend; bstart++ ) {
    if ( *bstart == *string &&
         strncmp(bstart, string, slen) == 0) {
      ret = bstart - buffer;
      break;
    }
  }
  return ret;
}

/* read the processor fast clock */
#define RDTSC(llptr) { \
    __asm__ __volatile__ ( \
    "rdtsc" \
    : "=A" (llptr) ); \
}

int main ( void ) {
  char *haystack = "the quick brown fox jumps over the lazy dog";
  char *needle   = "azy";
  struct {
    unsigned long long t1;
    unsigned long long t2;
    int result;
  } r[20];
  int i, n = 0;

  /* do each test 100 times */
  RDTSC(r[n].t1);
  for(i=0;i<100;i++) r[n].result = strstr(haystack,needle) - haystack;
  RDTSC(r[n].t2);
  n++;

  RDTSC(r[n].t1);
  for(i=0;i<100;i++) r[n].result = strfnd1(haystack,needle,0);
  RDTSC(r[n].t2);
  n++;

  RDTSC(r[n].t1);
  for(i=0;i<100;i++) r[n].result = strfnd2(haystack,needle,0);
  RDTSC(r[n].t2);
  n++;

  RDTSC(r[n].t1);
  for(i=0;i<100;i++) r[n].result = strfnd3(haystack,needle,0);
  RDTSC(r[n].t2);
  n++;

  RDTSC(r[n].t1);
  for(i=0;i<100;i++) r[n].result = strfnd4(haystack,needle,0);
  RDTSC(r[n].t2);
  n++;

  for ( i = 0 ; i < n ; i++ ) {
    unsigned long long elapsed = r[i].t2 - r[i].t1;
    printf( "Result=%d, time=%llu\n", r[i].result, elapsed );
  }

  return 0;
}


$ gcc -W -Wall -ansi -O2 hello.c
$ ./a.out
Result=36, time=21276
Result=36, time=1708840
Result=36, time=263308
Result=36, time=69440
Result=36, time=61664

Tough to beat the library strstr() function.

For those using win32 compilers, the RDTSC needs to be replaced with QueryPerformanceCounter
Those with non pentium (or pentium compatible) processors need another plan.

Somewhere else I was talking about the speed of my home made / Linux hand compiled kernel PC.

To give you an idea, I've just cut & paste the code. Here are my results :

Code:

shake:~/tmp# ./a.out
Result=36, time=63
Result=36, time=102825
Result=36, time=53586
Result=36, time=14202
Result=36, time=14211
shake:~/tmp#

The first result is more than 300 times faster than the result of the C example (21276) . I'm amazed.

So I guess it's a good idea to use strstr() . . . .

By the way, you shouldn't bump threads older than say two weeks. This thread is almost three years old.