quzah..
I guess..
would do as the base condition.. ain't it ?Code:if(s[x])
Nifty it *certainly* is, but efficient - no. I'm sure it would do for most string reversal jobs, though.
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.
It must use (relatively) excessive stack space, but WRT to speed, I wonder how significant the recursion is?
Not as big a deal as I would have guessed: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; }
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
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.
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.
Isn't it cute??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; } } }
Quzah.
Hope is the first step on the road to disappointment.
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.
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.
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
Last edited by quzah; 03-04-2012 at 11:18 AM.
Hope is the first step on the road to disappointment.