Memmove v/s Linked list Implementation

[getsanjay.sharma]

Hello there my friends, this is my first attempt at posting in a
newsgroup. Here is my problem statement:

Me and my friend decided to solve a programming problem with our own
styles and then decide which one is the best. The problem being:
"Remove all occurrences of a character (case insensitive) from a given
string"
eg.
i/p: She will be a massless princess
o/p: he will be a male prince (all occurances of 's' removed)

My friend implemented the solution by creating a Linked List of all the
character in which each node holds one character !!! Here is his code:

#include<stdio. h>
# include <iostream>
# include <conio.h>
using namespace std;

typedef struct charNode
{
char ch;
charNode* nxt;
charNode(char ch1 = 0){
nxt = NULL;
ch = ch1;
}
}cn;

int main()
{
cn* head = NULL,* temp, *node;
char ch1 = 'e', ch2;// ch1 is to hold the char that is to be
elimintated and ch2 to temp store the char

cout<< "enter string " ;
head = new cn ();
node = head;

ch2 = cin.get();
while ( ch2 != 10) { // this while loop for creating SLL
temp = new cn(ch2) ;
node->nxt = temp;
node = node->nxt;
ch2 = cin.get();
}

node = head; // for removal of unwanted character ... this
character given by ch1
while (node->nxt != NULL) {
if ( node->nxt->ch == ch1 ) {
temp = node->nxt;
if( temp->nxt == NULL )
node->nxt = NULL;
else
node->nxt = node->nxt->nxt;
delete temp;
}
else
node = node->nxt;
}

node = head; // display the elements !
while ( node -nxt != NULL ) {
cout<<node->ch;
node = node->nxt;
}
cout<<node->ch;
getchar();
return 0;
}

Whereas I implemented the solution using memmove, ie shifting the
entire string when the character to be eliminated is encountered. Here
is my effort:

#include <stdio.h>
#include <string.h>
const char chUpper = 'S' ;
const char chLower = 's' ;

void remove_s( char tmp[] )
{
while( *tmp != '\0' )
{
if( *tmp == chLower || *tmp == chUpper )
{
memmove( tmp, tmp + 1, &tmp[strlen( tmp )] - tmp ) ;
}
else
{
tmp++ ;
}
}
}

int main( )
{
char str[] = " Asser is an asser and nothing but asser, so be
solemsn " ;
printf( "\nThe old string: %s", str ) ;
remove_s( str ) ;
printf( "\nThe new string: %s", str ) ;

getchar( ) ;
return (0);
}

Now the problem is, we can't get to decide which piece of code is more
computationally expensive and would start giving problems as the length
of the string increases.....

Your expert views or any other efficient implementation is appreciated.
Also it would be really nice if you could point out the problem areas
in mine or his code....

Thanks again...

[santosh]

ge************* *@gmail.com wrote:

Hello there my friends, this is my first attempt at posting in a
newsgroup. Here is my problem statement:

Me and my friend decided to solve a programming problem with our own
styles and then decide which one is the best. The problem being:
"Remove all occurrences of a character (case insensitive) from a given
string"
eg.
i/p: She will be a massless princess
o/p: he will be a male prince (all occurances of 's' removed)

My friend implemented the solution by creating a Linked List of all the
character in which each node holds one character !!! Here is his code:

#include<stdio. h>
# include <iostream>
# include <conio.h>
using namespace std;

Please post C++ code to comp.lang.c++. Also read the FAQ for this group
from c-faq.com.

Now the problem is, we can't get to decide which piece of code is more
computationally expensive and would start giving problems as the length
of the string increases.....

Both methods are arguably overkill for the specification as you've
stated above.

[Ben Pfaff]

ge************* *@gmail.com writes:

Hello there my friends, this is my first attempt at posting in a
newsgroup.

You picked the wrong one. Your programs are written in C++, but
you posted to comp.lang.c. Furthermore, you really have an
algorithms question, but comp.lang.c is not about algorithms.

Me and my friend decided to solve a programming problem with our own
styles and then decide which one is the best. The problem being:
"Remove all occurrences of a character (case insensitive) from a given
string"
eg.
i/p: She will be a massless princess
o/p: he will be a male prince (all occurances of 's' removed)

My friend implemented the solution by creating a Linked List of all the
character in which each node holds one character !!! Here is his code:

[...]

Whereas I implemented the solution using memmove, ie shifting the
entire string when the character to be eliminated is encountered. Here
is my effort:

[...]

Now the problem is, we can't get to decide which piece of code is more
computationally expensive and would start giving problems as the length
of the string increases.....

A linked list solution could take O(N) time and space, but moving
the entire rest of the string around for each "s" encountered
takes O(N**2) time and O(N) space.

Here is a better solution (although I haven't tested it):

/* Remove all the "s" characters from STRING, in-place. */
void
remove_s (char *string)
{
char *p = string;
do {
if (*string != 's')
*p++ = *string;
} while (*string++ != '\0');
}
--
"Large amounts of money tend to quench any scruples I might be having."
-- Stephan Wilms

[getsanjay.sharma]

>Santosh wrote:

Please post C++ code to comp.lang.c++. Also read the FAQ for this group
from c-faq.com.

But since my program was in C I thought this would be a better place.
Don't you think that if I posted in the comp.langauge.c ++ group, they
would say the same thing to me since my code in in C and my friends in
C++ ?
Ben Pfaff wrote:

You picked the wrong one. Your programs are written in C++, but
you posted to comp.lang.c. Furthermore, you really have an
algorithms question, but comp.lang.c is not about algorithms.

Is there any algorithms newsgroup ? BTW my code is in C and my friends
in C++.

A linked list solution could take O(N) time and space, but moving
the entire rest of the string around for each "s" encountered
takes O(N**2) time and O(N) space.

So I guess it means that the memmove is after all more expensive than
the Linked List one...But I thought the memmove in C was implemented in
Assembly and moving around chunks of raw data would be as fast as it
got in C ?

[Ben Pfaff]

ge************* *@gmail.com writes:

Ben Pfaff wrote:

>You picked the wrong one. Your programs are written in C++, but
you posted to comp.lang.c. Furthermore, you really have an
algorithms question, but comp.lang.c is not about algorithms.

Is there any algorithms newsgroup ? BTW my code is in C and my friends
in C++.

I'd suggest comp.programmin g.

>A linked list solution could take O(N) time and space, but moving
the entire rest of the string around for each "s" encountered
takes O(N**2) time and O(N) space.

So I guess it means that the memmove is after all more expensive than
the Linked List one...But I thought the memmove in C was implemented in
Assembly and moving around chunks of raw data would be as fast as it
got in C ?

Suppose that the string consists entirely of "s"es. Then your
implementation will copy N + (N-1) + (N-2) + ... + 2 + 1 bytes,
or approximately (N**2)/2 bytes. My implementation will copy 1
byte (the null terminator). Do you still think yours should be
faster?
--
"For those who want to translate C to Pascal, it may be that a lobotomy
serves your needs better." --M. Ambuhl

"Here are the steps to create a C-to-Turbo-Pascal translator..." --H. Schildt

[santosh]

ge************* *@gmail.com wrote:

Santosh wrote:
Please post C++ code to comp.lang.c++. Also read the FAQ for this group
from c-faq.com.

But since my program was in C I thought this would be a better place.
Don't you think that if I posted in the comp.langauge.c ++ group, they
would say the same thing to me since my code in in C and my friends in
C++ ?

Since C, is for practical purposes, a subset of C++, comp.lang.c++
would be a better place than here. The best solution, of course, is to
have both your examples in a single language, or post to a more
algorithm centric group like comp.programmin g.

Ben Pfaff wrote:

You picked the wrong one. Your programs are written in C++, but
you posted to comp.lang.c. Furthermore, you really have an
algorithms question, but comp.lang.c is not about algorithms.

Is there any algorithms newsgroup ? BTW my code is in C and my friends
in C++.

comp.programmin g is one.

A linked list solution could take O(N) time and space, but moving
the entire rest of the string around for each "s" encountered
takes O(N**2) time and O(N) space.

So I guess it means that the memmove is after all more expensive than
the Linked List one...But I thought the memmove in C was implemented in
Assembly and moving around chunks of raw data would be as fast as it
got in C ?

This has nothing to do with the implementation. Even the fastest
assembly code will be of no use to you, if you picked the wrong high
level algorithm to begin with. As I said, for the problem as you state
above, which is very simple, both the solutions are overkill, the
memmove() based one, especially so. Ben Pfaff's solution is a good
alternative.

[getsanjay.sharma]

@ Santosh and Ben
Thanks both of you for the newsgroup name...

@Ben:
Yeah I do realize that in whatever way the memmove be internally
implemented, the way I have used it is really an overkill. If possible
Ben, can you please describe in detail what you said previously about
O(N**2) complexity in time and O(N) complexity in space regarding my
solution... ?

[santosh]

getsanjay.sha.. [e-mail] wrote:

@ Santosh and Ben
Thanks both of you for the newsgroup name...

@Ben:
Yeah I do realize that in whatever way the memmove be internally
implemented, the way I have used it is really an overkill. If possible
Ben, can you please describe in detail what you said previously about
O(N**2) complexity in time and O(N) complexity in space regarding my
solution... ?

In the meanwhile, the following pages should give an introduction for
this notation:

<http://en.wikipedia.or g/wiki/Big_O_notation>
<http://www.eecs.harvar d.edu/~ellard/Q-97/HTML/root/node5.html>

[CBFalconer]

ge************* *@gmail.com wrote:

>

.... snip ...

>
The problem being: "Remove all occurrences of a character (case
insensitive) from a given string"
eg.
i/p: She will be a massless princess
o/p: he will be a male prince (all occurances of 's' removed)

My friend implemented the solution by creating a Linked List of all the
character in which each node holds one character !!! Here is his code:

.... snip 100 lines of ridiculously bloated off-topic C++ code

>
Now the problem is, we can't get to decide which piece of code is more
computationally expensive and would start giving problems as the length
of the string increases.....

Your expert views or any other efficient implementation is appreciated.
Also it would be really nice if you could point out the problem areas
in mine or his code....

#include <stdio.h>

int main(int argc, char **argv) {
int ch;

if (argc < 2) puts("Usage: junk c <input");
else
while (EOF != (ch = getchar()))
if (ch != *argv[1]) putchar(ch);
return 0;
}

c:\c\junk>cc junk.c
c:\c\junk>a s
She will be a massless princess
She will be a male prince

Maybe this will convince you that C++ is not appropriate for many
things.

--
Some informative links:
<http://www.catb.org/~esr/faqs/smart-questions.html>
<http://www.caliburn.nl/topposting.html >
<http://www.netmeister. org/news/learn2quote.htm l>
<http://cfaj.freeshell. org/google/ (taming google)
<http://members.fortune city.com/nnqweb/ (newusers)

[Charlton Wilbur]

>>>>"gs" == getsanjay sharma <ge************ **@gmail.comwri tes:

gsMe and my friend decided to solve a programming problem with
gsour own styles and then decide which one is the best. The
gsproblem being: "Remove all occurrences of a character (case
gsinsensitive) from a given string"

You both wrote some horrendously bad code. This (below) is optimized
for terseness, and has an additional feature that it will remove any
character, not just S.

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

char *remove_char (char *target, char ch)
{
char *src = target;
char *dst = target;

char lch = tolower(ch);
char sch;

while (sch = *src++)
if (tolower(sch) != lch)
*dst++ = sch;

*dst = 0;

return target;
}

int main (void)
{
char in[] = " Asser is an asser and nothing but asser, so be solemsn";
printf("The old string: %s\n", in);
remove_char (in, 's');
printf( "The new string: %s\n", in);

return 0;
}

(Of course, in Perl, I'd just say $str =~ s/s//gi; and call it good.)

Charlton
--
Charlton Wilbur
cw*****@chromat ico.net