Most optimized way to reverse a string?
-
Hi, Can someone write a function that reverses a string in the most optimized manner? meaning it should use as few variables, loops etc as possible.
-
Hi, Can someone write a function that reverses a string in the most optimized manner? meaning it should use as few variables, loops etc as possible.
No temps in reverseString at all, and only one loop which goes halfway along the string. It is an in-place reverse, so it overwrites whats there. If I was feeling really keen I could turn it into a template too :-D
#include <iostream> #include <cstdio> using namespace std; void reverseString(char *str, const int &len) { for(int i=0; i<(len-1)-i; ++i) str[i] ^= str[(len-1)-i] ^= str[i] ^= str[(len-1)-i]; } int main() { char str[] = "String to reverse!"; int len = strlen(str); // in place reverse cout << str << endl; reverseString(str, len); cout << str << endl; return 0; }
-- Ian Darling "The moral of the story is that with a contrived example, you can prove anything." - Joel Spolsky -
Hi, Can someone write a function that reverses a string in the most optimized manner? meaning it should use as few variables, loops etc as possible.
So, what's wrong with
std::reverse
? The compiler's supplied library is usually pretty well optimised for the task in hand. In the general case, forget about trying to eliminate variables, loops etc in your code. The compiler can do that when it optimises - unrolling loops, enregistering variables, removing common terms. Compile your code in release mode for a simple implementation, then see what the compiler did with it. Shortest C++ code is not necessarily shortest or fastest object code. So, the best optimised code is probablyvoid ReverseString( char* sz, size_t len )
{
char ch;for ( size_t idx = 0; idx < len / 2; ++idx )
{
ch = sz[idx];
sz[idx] = sz[len - idx - 1];
sz[len - idx - 1] = ch;
}
}The compiler hoists the division of
len
by 2 out of the loop (and also converts it to a right-shift by 1). It also converts thesz[len - idx - 1]
terms into a pointer and moves it back down from the end. Finally, it uses thedl
register (the least significant byte ofedx
to storech
, which is never stored to main memory. Stick to simple code. -
So, what's wrong with
std::reverse
? The compiler's supplied library is usually pretty well optimised for the task in hand. In the general case, forget about trying to eliminate variables, loops etc in your code. The compiler can do that when it optimises - unrolling loops, enregistering variables, removing common terms. Compile your code in release mode for a simple implementation, then see what the compiler did with it. Shortest C++ code is not necessarily shortest or fastest object code. So, the best optimised code is probablyvoid ReverseString( char* sz, size_t len )
{
char ch;for ( size_t idx = 0; idx < len / 2; ++idx )
{
ch = sz[idx];
sz[idx] = sz[len - idx - 1];
sz[len - idx - 1] = ch;
}
}The compiler hoists the division of
len
by 2 out of the loop (and also converts it to a right-shift by 1). It also converts thesz[len - idx - 1]
terms into a pointer and moves it back down from the end. Finally, it uses thedl
register (the least significant byte ofedx
to storech
, which is never stored to main memory. Stick to simple code.My guess would be this is what the lecturer is looking for too ;P -- The Obliterator
-
So, what's wrong with
std::reverse
? The compiler's supplied library is usually pretty well optimised for the task in hand. In the general case, forget about trying to eliminate variables, loops etc in your code. The compiler can do that when it optimises - unrolling loops, enregistering variables, removing common terms. Compile your code in release mode for a simple implementation, then see what the compiler did with it. Shortest C++ code is not necessarily shortest or fastest object code. So, the best optimised code is probablyvoid ReverseString( char* sz, size_t len )
{
char ch;for ( size_t idx = 0; idx < len / 2; ++idx )
{
ch = sz[idx];
sz[idx] = sz[len - idx - 1];
sz[len - idx - 1] = ch;
}
}The compiler hoists the division of
len
by 2 out of the loop (and also converts it to a right-shift by 1). It also converts thesz[len - idx - 1]
terms into a pointer and moves it back down from the end. Finally, it uses thedl
register (the least significant byte ofedx
to storech
, which is never stored to main memory. Stick to simple code. -
Hi, Can someone write a function that reverses a string in the most optimized manner? meaning it should use as few variables, loops etc as possible.
-
__inline char *StrRev(char *Source, char *Dest) { char *p = strchr(Source, '\0'), *p2 = Dest; while( --p >= Source ) *p2++ = *p; *p2 = '\0'; return Dest; }; Phil
Nice. :) Actually the initial problem required the original string to be reversed (which i forgot to mention). I have used your nice logic to modify my function :-)
void Reverse(char *src) { char *p = strchr(src, '\0') - 1; while (src < p) { *src ^= *p ^= *src ^= *p; src++; p--; } }
-Melwyn