Various Topics on C++

..mbed20..

Hi all,
I asked this question in the C group but no one seems to be interested
in answering it. :-( Basically, I wrote a search and replace function
so I can do:

char[] source = "abcd?1234?x";
char search = '?';
char* replace = "***";

char* result = search_and_replace(source,search,replace);

result will then be "abcd***1234***x". I understand that I can
probably use string instead of char* and there's probably some API in
the C++ standard library that I can use but I want to code it as an
exercise to learn the algorithm. Can someone suggest ways to improve
the performance of my search and replace algorithm? The function lacks
some error checkings but I am more interested in the algorithm.
Thanks!

char* search_and_replace(char* source,char search,char* replace){

char* result;

size_t l = strlen(source), r = strlen(replace), i, k;

int number_of_replaces = 0;

for(i = 0; i < l; i++){
if(source[i] == search)
number_of_replaces++;
}

result = malloc((l - number_of_replaces) +
number_of_replaces * r + 1);
i = 0; k = 0;

while(k < l){
if(source[k] == search){
int j;
for(j = 0; j < r; j++){
result[i++] = replace[j];
}
}else{
result[i++] = source[k];
}
k++;
}

result[i] = 0;
return result;
}

.... ..rris..

"pembed2003" <pembed2003@yahoo.com> wrote in message
news:db593abd.0406192214.72551bc8@posting.google.c om...
> Hi all,
> I asked this question in the C group but no one seems to be interested
> in answering it. :-( Basically, I wrote a search and replace function
> so I can do:
>
> char[] source = "abcd?1234?x";
> char search = '?';
> char* replace = "***";
>
> char* result = search_and_replace(source,search,replace);
>
> result will then be "abcd***1234***x". I understand that I can
> probably use string instead of char* and there's probably some API in
> the C++ standard library that I can use but I want to code it as an
> exercise to learn the algorithm. Can someone suggest ways to improve
> the performance of my search and replace algorithm? The function lacks
> some error checkings but I am more interested in the algorithm.
> Thanks!
>
> char* search_and_replace(char* source,char search,char* replace){
>
> char* result;
>
> size_t l = strlen(source), r = strlen(replace), i, k;
>
> int number_of_replaces = 0;
>
> for(i = 0; i < l; i++){
> if(source[i] == search)
> number_of_replaces++;
> }
>
> result = malloc((l - number_of_replaces) +
> number_of_replaces * r + 1);
> i = 0; k = 0;
>
> while(k < l){
> if(source[k] == search){
> int j;
> for(j = 0; j < r; j++){
> result[i++] = replace[j];
> }
> }else{
> result[i++] = source[k];
> }
> k++;
> }
>
> result[i] = 0;
> return result;
> }

I can't see any obvious way to improve the efficiency, you seem to be doing
all the right things, like preallocating the result buffer. This loop

for(j = 0; j < r; j++){
result[i++] = replace[j];
}

might be a little faster as a memcpy

memcpy(result + i, replace, r);
i += r;

You could also try a pointer version instead of using ints for all your loop
variables. It might be faster but it might not, worth a try though.

john

..em.. ..r..

"pembed2003" <pembed2003@yahoo.com> wrote in message

> char[] source = abcd?1234?x";
> char search = '?';
> char* replace = "***";
>
> char* result = search_and_replace(source,search,replace);
>
> result will then be "abcd***1234***x". I understand that I can

Wait a sec. Did you want four **** before x?

> probably use string instead of char* and there's probably some API in
> the C++ standard library that I can use but I want to code it as an
> exercise to learn the algorithm. Can someone suggest ways to improve
> the performance of my search and replace algorithm? The function lacks
> some error checkings but I am more interested in the algorithm.
> Thanks!
>
> char* search_and_replace(char* source,char search,char* replace){
>
> char* result;
>
> size_t l = strlen(source), r = strlen(replace), i, k;
>
> int number_of_replaces = 0;
>
> for(i = 0; i < l; i++){
> if(source[i] == search)
> number_of_replaces++;
> }
>
> result = malloc((l - number_of_replaces) +
> number_of_replaces * r + 1);
> i = 0; k = 0;
>
> while(k < l){
> if(source[k] == search){
> int j;
> for(j = 0; j < r; j++){
> result[i++] = replace[j];
> }
> }else{
> result[i++] = source[k];
> }
> k++;
> }
>
> result[i] = 0;
> return result;
> }

This looks good. It's efficient. Maybe put in a few comments.

One thing I can think of is that use of standard functions like memcpy
(suitable for your case) and strcpy may use special ***embly instructions
created especially for memcpy, and thus the resulting code would be faster.
But I'm not an expert on what these statements are, what platforms do what,
what compilers support what, and so on.

Another thing I can think of is when you scan the array to find the number
of elements to replace, you put the index of the element into an array, so
for example in "abcd?1234?x" the array will contain 4 and 9 (the index of
the ?). Then in the next loop you can just look up the ?. This approach
may make the algorithm faster if there are few replacements in a long
stream. Also, the resulting code is more complicated, and thus harder to
maintain.

Maybe others can see other problems.

Maybe the next challenge is to do the same in place! Note, this algorithm
is not necessarily better, just different.

..v.. ..rm..

On 19 Jun 2004 23:14:29 -0700 in comp.lang.c++, pembed2003@yahoo.com
(pembed2003) wrote,
>Hi all,
>I asked this question in the C group but no one seems to be interested

Sorry, I am not interested until I see it
use std::string::find() and std::string::replace()