Memmove v/s Linked list Implementation

Discussion in 'C Programming' started by getsanjay.sharma@gmail.com, Jan 23, 2007.

  1. Guest

    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...
    , Jan 23, 2007
    #1
    1. Advertising

  2. santosh Guest

    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.
    santosh, Jan 23, 2007
    #2
    1. Advertising

  3. Ben Pfaff Guest

    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
    Ben Pfaff, Jan 23, 2007
    #3
  4. Guest

    >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 ?
    , Jan 23, 2007
    #4
  5. Ben Pfaff Guest

    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
    Ben Pfaff, Jan 23, 2007
    #5
  6. santosh Guest

    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.
    santosh, Jan 23, 2007
    #6
  7. Guest

    @ 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... ?
    , Jan 23, 2007
    #7
  8. santosh Guest

    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>
    santosh, Jan 23, 2007
    #8
  9. CBFalconer Guest

    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)
    CBFalconer, Jan 23, 2007
    #9
  10. >>>>> "gs" == getsanjay sharma <> 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
    Charlton Wilbur, Jan 23, 2007
    #10
  11. Guest

    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
    , Jan 24, 2007
    #11
  12. <> wrote in message
    news:...
    > 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 ()
    http://www.e3ft.com (Consulting Home Page)
    http://www.dtashley.com (Personal Home Page)
    http://gpl.e3ft.com (GPL Publications and Projects)
    David T. Ashley, Jan 24, 2007
    #12
  13. Ben Pfaff Guest

    "David T. Ashley" <> writes:

    > 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[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz.\
    \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\
    );}return 0;}
    Ben Pfaff, Jan 24, 2007
    #13
  14. CBFalconer Guest

    Ben Pfaff wrote:
    > "David T. Ashley" <> writes:
    >
    >> 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
    CBFalconer, Jan 25, 2007
    #14
  15. "santosh" <> wrote in message
    news:...
    > 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
    Stephen Sprunk, Jan 25, 2007
    #15
  16. Jorgen Grahn Guest

    On Tue, 23 Jan 2007 17:12:16 -0500, CBFalconer <> wrote:
    > 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!
    Jorgen Grahn, Feb 1, 2007
    #16
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Dan Pop

    Re: memcopy, memmove Implementation

    Dan Pop, Jun 24, 2003, in forum: C Programming
    Replies:
    0
    Views:
    1,230
    Dan Pop
    Jun 24, 2003
  2. Dan Pop

    Re: memcopy, memmove Implementation

    Dan Pop, Jun 24, 2003, in forum: C Programming
    Replies:
    1
    Views:
    2,513
  3. Micah Cowan

    Re: memcopy, memmove Implementation

    Micah Cowan, Jun 26, 2003, in forum: C Programming
    Replies:
    0
    Views:
    844
    Micah Cowan
    Jun 26, 2003
  4. Trewth Seeker

    Re: memcopy, memmove Implementation

    Trewth Seeker, Jul 14, 2003, in forum: C Programming
    Replies:
    0
    Views:
    524
    Trewth Seeker
    Jul 14, 2003
  5. fool
    Replies:
    14
    Views:
    505
    Barry Schwarz
    Jul 3, 2006
Loading...

Share This Page