Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Memmove v/s Linked list Implementation

Reply
Thread Tools

Memmove v/s Linked list Implementation

 
 
getsanjay.sharma@gmail.com
Guest
Posts: n/a
 
      01-23-2007
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...

 
Reply With Quote
 
 
 
 
santosh
Guest
Posts: n/a
 
      01-23-2007

http://www.velocityreviews.com/forums/(E-Mail Removed) 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.

 
Reply With Quote
 
 
 
 
Ben Pfaff
Guest
Posts: n/a
 
      01-23-2007
(E-Mail Removed) 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
 
Reply With Quote
 
getsanjay.sharma@gmail.com
Guest
Posts: n/a
 
      01-23-2007
>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 ?

 
Reply With Quote
 
Ben Pfaff
Guest
Posts: n/a
 
      01-23-2007
(E-Mail Removed) 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
 
Reply With Quote
 
santosh
Guest
Posts: n/a
 
      01-23-2007
(E-Mail Removed) 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.

 
Reply With Quote
 
getsanjay.sharma@gmail.com
Guest
Posts: n/a
 
      01-23-2007

@ 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... ?

 
Reply With Quote
 
santosh
Guest
Posts: n/a
 
      01-23-2007
(E-Mail Removed) 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>

 
Reply With Quote
 
CBFalconer
Guest
Posts: n/a
 
      01-23-2007
(E-Mail Removed) 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)

 
Reply With Quote
 
Charlton Wilbur
Guest
Posts: n/a
 
      01-23-2007
>>>>> "gs" == getsanjay sharma <(E-Mail Removed)> writes:

gs> Me and my friend decided to solve a programming problem with
gs> our own styles and then decide which one is the best. The
gs> problem being: "Remove all occurrences of a character (case
gs> insensitive) 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
(E-Mail Removed)
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Linked list within a linked list joshd C++ 12 10-02-2006 08:57 AM
Linked list, New try (was:Linked list, no out put,help) fool C Programming 14 07-03-2006 12:29 AM
Re: memcopy, memmove Implementation Micah Cowan C Programming 0 06-26-2003 02:52 AM
Re: memcopy, memmove Implementation Dan Pop C Programming 1 06-24-2003 01:42 PM
Re: memcopy, memmove Implementation Dan Pop C Programming 0 06-24-2003 12:17 PM



Advertisments