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.programming.

>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.programming.

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.programming 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]

[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.org/wiki/Big_O_notation>
<http://www.eecs.harvard.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.html>
<http://cfaj.freeshell.org/google/ (taming google)
<http://members.fortunecity.com/nnqweb/ (newusers)

[Charlton Wilbur]

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

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*****@chromatico.net

[getsanjay.sharma]

Thanks a lot all your guys for your valuable time and comments...

Charlton Wilbur wrote:

You both wrote some horrendously bad code.

Yes I know, I have already been clubbed by almost all the members
because of this... ;-)

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

Wish C was as forgiving as Perl...

Thanks again all of you. When I have a C doubt, I know where to turn
to.... :-D

[David T. Ashley]

<ge**************@gmail.comwrote in message
news:11**********************@h3g2000cwc.googlegro ups.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.....

Assuming uniform distribution of the characters to be removed, the memmove()
method is O(N**2). This comes about because each of the later characters in
the string may need to be moved many times.

Both methods you proposed suck from an efficiency point of view.

O(N**2) sucks very badly when O(N) is available.

The most efficient method--and it is O(N)--would be to maintain two pointers
within the string, one being the "put" point and the other being the "get"
point. Just skip the "get" pointer over the characters you don't want. For
all others, write them to the "put" pointer and advance it by one. The code
is so trivial I won't write it for a newsgroup post.

--
David T. Ashley (dt*@e3ft.com)
http://www.e3ft.com (Consulting Home Page)
http://www.dtashley.com (Personal Home Page)
http://gpl.e3ft.com (GPL Publications and Projects)

[Ben Pfaff]

"David T. Ashley" <dt*@e3ft.comwrites:

The most efficient method--and it is O(N)--would be to maintain two pointers
within the string, one being the "put" point and the other being the "get"
point. Just skip the "get" pointer over the characters you don't want. For
all others, write them to the "put" pointer and advance it by one. The code
is so trivial I won't write it for a newsgroup post.

For what it's worth, I already put code for this somewhere else
in the thread.
--
int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv wxyz.\
\n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\
);}return 0;}

[Stephen Sprunk]

"santosh" <sa*********@gmail.comwrote in message
news:11*********************@13g2000cwe.googlegrou ps.com...

[e-mail] wrote:

>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.org/wiki/Big_O_notation>
<http://www.eecs.harvard.edu/~ellard/Q-97/HTML/root/node5.html>

Both good introductions, but one thing that both mostly neglect is that
they compare algorithms for _large_ values of N. Big-O notation drops
all the constants and non-dominant terms, and thus is not necessarily
helpful for small values of N. For instance, it isn't difficult to find
examples where an O(N^2) algorithm outperforms an O(N) one due to large
constants on the latter.

The end result is that the best solution for a string of 10 characters
may not be the best solution for a string of 10,000 characters and vice
versa.

S

--
Stephen Sprunk "God does not play dice." --Albert Einstein
CCIE #3723 "God is an inveterate gambler, and He throws the
K5SSS dice at every possible opportunity." --Stephen Hawking
--
Posted via a free Usenet account from http://www.teranews.com

[CBFalconer]

Ben Pfaff wrote:

"David T. Ashley" <dt*@e3ft.comwrites:

>The most efficient method--and it is O(N)--would be to maintain
two pointers within the string, one being the "put" point and the
other being the "get" point. Just skip the "get" pointer over
the characters you don't want. For all others, write them to the
"put" pointer and advance it by one. The code is so trivial
I won't write it for a newsgroup post.

For what it's worth, I already put code for this somewhere else
in the thread.

As did I, except I used i/o streams.

--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>

"A man who is right every time is not likely to do very much."
-- Francis Crick, co-discover of DNA
"There is nothing more amazing than stupidity in action."
-- Thomas Matthews

[Jorgen Grahn]

On Tue, 23 Jan 2007 17:12:16 -0500, CBFalconer <cb********@yahoo.comwrote:

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

....

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

Nitpick: you need a tolower() somewhere here to meet the requirements.

return 0;
}

....

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

This is offtopic here, but the quoted (and thankfully, snipped) C++ code
was (again, thankfully) non-representative. The original poster's friend
needs to get a modern book on the subject. Badly. Hints: std::list,
std::string, std::copy_if.

/Jorgen

--
// Jorgen Grahn <grahn@ Ph'nglui mglw'nafh Cthulhu
\X/ snipabacken.dyndns.org R'lyeh wgah'nagl fhtagn!