Thread: string reverse. cannot find the bug in my code.

  1. #16
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by MK27 View Post
    If quzah hadn't beaten me to the punch I would have thought of that too, really :P.
    I think someone was trying to do it for homework here once. I just did it to see if I could. I don't know if I actually posted the result, but I keep it around because I thought it was nifty.


    Quzah.
    Hope is the first step on the road to disappointment.

  2. #17
    Registered User
    Join Date
    Mar 2012
    Posts
    7
    quzah..
    I guess..
    Code:
    if(s[x])
    would do as the base condition.. ain't it ?

  3. #18
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Nifty it *certainly* is, but efficient - no. I'm sure it would do for most string reversal jobs, though.

  4. #19
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by Adak View Post
    Nifty it *certainly* is, but efficient - no.
    How is it not efficient? What's your metric? It makes a single pass through the string. It's fine if you can actually say why it's not efficient, and I'm not claiming it is. But you are claiming it isn't, so you'll need to do more than what you've done to prove your case.


    Quzah.
    Hope is the first step on the road to disappointment.

  5. #20
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by quzah View Post
    How is it not efficient? What's your metric?
    It must use (relatively) excessive stack space, but WRT to speed, I wonder how significant the recursion is?

    Code:
    #include <stdio.h>
    #include <sys/timex.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define LINES 80368
    
    int loadStrings (char *path, char *store[], int len) {
    	char *p;
    	int i = 0;
    	FILE *in = fopen(path, "r");
    	if (!in) return -1;
    	while (fgets(store[i], len, in)) {
    		p = strchr(store[i++], '\n');
    		*p = '\0';
    	}
    	fclose(in);
    	return 0;
    }
    
    void reportDif (struct ntptimeval *a, struct ntptimeval *b) {
    	long mic = b->time.tv_usec - a->time.tv_usec,
    		sec = b->time.tv_sec - a->time.tv_sec;
    
    	if (mic < 0) {
    		sec--;
    		mic *= -1;
    		mic++;
    	}
    
    	printf("Elapsed: %ld microseconds\n", mic + sec * 1000000);
    }
    
    char **allocList (int sz, int len) {
    	char **rv = malloc(sz * sizeof(char*));
    	int i;
    	for (i = 0; i < sz; i++) 
    		rv[i] = malloc(len);
    	return rv;
    }
    
    void freeList (char *list[], int sz) {
    	int i;
    	for (i = 0; i < sz; i++)
    		free(list[i]);
    }
    
    void reverse (char *str) {
    	int i = 0, mid = 0, j = 0;
    	char ch;
    	while (str[++i] != '\0');
    	i--;
    	mid = i/2;
    	while (i > mid) {
    		ch = str[j];
    		str[j++] = str[i];
    		str[i--] = ch;
    	}
    }
    
    size_t rev( char s[], size_t x )
    {
        if( s && s[x] )
        {
            size_t y = rev( s, x+1 );
            if( x < y / 2 )
            {
                char t = s[x];
                s[x] = s[y-1-x];
                s[y-1-x] = t;
            }
            x = y;
        }
        return x;
    }
    
    int main (void) {
    	int i;
    	char **data = allocList(LINES, 32);
    	struct ntptimeval start, end;
    	loadStrings("dictionary.txt", data, 32);
    
    	ntp_gettime(&start);
    	for (i = 0; i < LINES; i++)
    		reverse(data[i]);
    	ntp_gettime(&end);
    	reportDif(&start, &end);
    		
    	ntp_gettime(&start);
    	for (i = 0; i < LINES; i++)
    		rev(data[i], 0);
    	ntp_gettime(&end);
    	reportDif(&start, &end);
    
    	freeList(data, LINES);
    	free(data);
    		
    	return 0;
    }
    Not as big a deal as I would have guessed:

    Elapsed: 4801 microseconds
    Elapsed: 8216 microseconds
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  6. #21
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    My metric for efficiency would be + 10% to 15%. This is + 71%.

    MK did a great job of testing, but his strings were simply single words, I believe. As the strings got longer, the "Nifty" reversing program will begin to flounder much more than the 171% of the better algorithm. Think of the DNA researcher who stated she was working with strings up to 32k in length!! <eek!>

    Also, the "Nifty" program is longer, and easier to goof up. Besides it's nifty-ness, it has nothing to recommend it.

  7. #22
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by Adak View Post
    Also, the "Nifty" program is longer, and easier to goof up. Besides it's nifty-ness, it has nothing to recommend it.
    I assume by "longer and easier to goof up" you mean because it has two arguments instead of one. Ok. Here's a non-recursive, in-place string reversal, that still technically uses a single pass through the string.
    Code:
    void revbubble( char s[] )
    {
        for( int here = 0; s[ here ] != '\0'; here++ )
        {
            for( int there = here -1; there > -1; there-- )
            {
                char c = s[ there + 1 ];
                s[ there + 1 ] = s[ there ];
                s[ there ] = c;
            }
        }
    }
    Isn't it cute??


    Quzah.
    Hope is the first step on the road to disappointment.

  8. #23
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Point is, you can't do an efficient in-place string reversal unless you know where the end of the string is. Ideally, the end of the string would be known to the function doing the reversal.

    All this other stuff is second rate at the job at best, no matter how cute or nifty it might be.

  9. #24
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by Adak View Post
    All this other stuff is second rate at the job at best, no matter how cute or nifty it might be.
    I wasn't trying to be efficient on any of them. I was going for interesting. Actually the first one was constrained by someone's homework assignment guidelines, and the second one was just interesting. I'll leave efficiency for people who specialize in doing boring things.


    Quzah.
    Hope is the first step on the road to disappointment.

  10. #25
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Lol. The second one reminds of this toy made of a chain of flat wooden blocks (proportionate to a domino, but ~4" long), held together end to end with three fabric straps. The straps were attached in such a way that you could cause the blocks to flip in a sequence, and what it looked like was one block cartwheeling along the chain.

    But it is even slower than the recursive one:

    Elapsed: 4798 microseconds
    Elapsed: 8220 microseconds
    Elapsed: 13687 microseconds

    Hmm...found the toy. It's called a "Jacob's ladder":
    http://www.lhup.edu/~dsimanek/TTT-rings/rings.htm
    Last edited by MK27; 03-04-2012 at 11:10 AM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  11. #26
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by MK27 View Post
    But it is even slower than the recursive one:

    Elapsed: 4798 microseconds
    Elapsed: 8220 microseconds
    Elapsed: 13687 microseconds
    Of course it's slower. It's basically a bubble sort. It just pushes the furthest point back along the line until it's at the front. Over and over. Put in some printf statements if you want to watch it work.


    Quzah.
    Last edited by quzah; 03-04-2012 at 11:18 AM.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Exercise reverse array . I can't to find error .
    By ToNy_ in forum C Programming
    Replies: 8
    Last Post: 12-15-2011, 04:02 PM
  2. reverse a string without string.h library
    By antros48 in forum C Programming
    Replies: 6
    Last Post: 09-10-2011, 06:01 PM
  3. Reverse a string (without using any string functions?)
    By geetard in forum C Programming
    Replies: 2
    Last Post: 11-15-2006, 07:42 PM
  4. Problem with my string reverse code
    By learninC in forum C Programming
    Replies: 3
    Last Post: 05-24-2005, 09:22 PM
  5. How to reverse a string C
    By Unregistered in forum C Programming
    Replies: 2
    Last Post: 07-18-2002, 12:26 PM

Tags for this Thread