Hi Tomer,

If there's a non-recursive alternative, you should never use recursive
function. (easier to maintain, performance reason...)

The following implementation provide non-recursive approach with no hacking
(or "special case handling"), lesser function calls and zero IF statement.

public static string StrRev( string s ) {
char[] charArray;

charArray = s.ToCharArray();
Array.Reverse( charArray );

return ( new string( charArray ) );
}


Compulim @ kasuei


"Tomer" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
Hi,

I've check on the web for a string reverse function and this one on many
places:

public static string StrRev(string s)
{
if (s.Length == 1)
return s;
else
return StrRev( s.Substring(1) ) + s.Substring(0,1);
}
Now, this doesn't work when you put an empty string and produce a
StackOverflowException, so we add a condition at the begining of the
function:
public static string StrRev(string s)
{
if (s.Length == 0)
return s;
if (s.Length == 1)
return s;
else
return StrRev( s.Substring(1) ) + s.Substring(0,1);
}
Hope this helps, Tomer.

Tomer <(E-Mail Removed)> wrote:
> I've check on the web for a string reverse function and this one on many places:
>
> public static string StrRev(string s)
> {
>
> if (s.Length == 1)
>
> return s;
>
> else
>
> return StrRev( s.Substring(1) ) + s.Substring(0,1);
>
> }
>
> Now, this doesn't work when you put an empty string and produce a
> StackOverflowException, so we add a condition at the begining of the
> function:
>
> public static string StrRev(string s)
>
> {
>
> if (s.Length == 0)
>
> return s;
>
> if (s.Length == 1)
>
> return s;
>
> else
>
> return StrRev( s.Substring(1) ) + s.Substring(0,1);
>
> }

Alternatively, you could do something which *won't* throw a
StackOverflowException (or use horrendous amounts of memory for no good
reason):

public static string ReverseString (string s)
{
if (s==null || s.Length < 2)
{
return s;
}

StringBuilder builder = new StringBuilder(s.Length);
for (int i=s.Length-1; i >= 0; i--)
{
builder.Append(s[i]);
}
return builder.ToString();
}

This is slightly more expensive in time but less expensive in memory
than creating a new char array and then a new string from that. Either
way, it's *much* better than the recursive version.

--
Jon Skeet - <(E-Mail Removed)>
http://www.pobox.com/~skeet
If replying to the group, please do not mail me too

There are 10 million ways to reverse a string and all of this has nothing to
do with the CF specifically but what the heck, I'll chip in...

The checks at the beginning of the method are not "special cases", just
verifying the preconditions of the method... While we are talking about
them, both examples given would fail if they were passed a null string...

Faster than both of the methods above is to create StringBuilder and append
to it the characters of the input string (walking backwards)... If
performance was not an issue you could use
Microsoft.VisualBasic.Strings.StrReverse

Cheers
Daniel


"compulim" <123> wrote in message
news:(E-Mail Removed)...
> Hi Tomer,
>
> If there's a non-recursive alternative, you should never use recursive
> function. (easier to maintain, performance reason...)
>
> The following implementation provide non-recursive approach with no
hacking
> (or "special case handling"), lesser function calls and zero IF statement.
>
> public static string StrRev( string s ) {
> char[] charArray;
>
> charArray = s.ToCharArray();
> Array.Reverse( charArray );
>
> return ( new string( charArray ) );
> }
>
>
> Compulim @ kasuei
>
>
> "Tomer" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed)...
> Hi,
>
> I've check on the web for a string reverse function and this one on many
> places:
>
> public static string StrRev(string s)
> {
> if (s.Length == 1)
> return s;
> else
> return StrRev( s.Substring(1) ) + s.Substring(0,1);
> }
> Now, this doesn't work when you put an empty string and produce a
> StackOverflowException, so we add a condition at the begining of the
> function:
> public static string StrRev(string s)
> {
> if (s.Length == 0)
> return s;
> if (s.Length == 1)
> return s;
> else
> return StrRev( s.Substring(1) ) + s.Substring(0,1);
> }
> Hope this helps, Tomer.
>
>

<"compulim" <123>> wrote:
> Hi Tomer,
>
> If there's a non-recursive alternative, you should never use recursive
> function. (easier to maintain, performance reason...)
>
> The following implementation provide non-recursive approach with no hacking
> (or "special case handling"), lesser function calls and zero IF statement.
>
> public static string StrRev( string s ) {
> char[] charArray;
>
> charArray = s.ToCharArray();
> Array.Reverse( charArray );
>
> return ( new string( charArray ) );
> }

I don't see why special-casing empty or single character strings is a
bad idea. (The above still fails with null. If you want it to throw an
exception, ArgumentNullException would be a better one than the
NullReferenceException currently thrown.)

While it's also better with memory than the recursive version, it still
creates a "wasted" character array.

--
Jon Skeet - <(E-Mail Removed)>
http://www.pobox.com/~skeet
If replying to the group, please do not mail me too

The original one also fails with null value. But for performance reason, I
agree adding "null" and "length < 2" condition.

But more method invocation will leads to poor performance. The temporary
charArray in my approach won't take up much memory and able to GC once it
left the method.

What do you think?


Compulim @ kasuei

"Jon Skeet [C# MVP]" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> <"compulim" <123>> wrote:
>> Hi Tomer,
>>
>> If there's a non-recursive alternative, you should never use recursive
>> function. (easier to maintain, performance reason...)
>>
>> The following implementation provide non-recursive approach with no
>> hacking
>> (or "special case handling"), lesser function calls and zero IF
>> statement.
>>
>> public static string StrRev( string s ) {
>> char[] charArray;
>>
>> charArray = s.ToCharArray();
>> Array.Reverse( charArray );
>>
>> return ( new string( charArray ) );
>> }
>
> I don't see why special-casing empty or single character strings is a
> bad idea. (The above still fails with null. If you want it to throw an
> exception, ArgumentNullException would be a better one than the
> NullReferenceException currently thrown.)
>
> While it's also better with memory than the recursive version, it still
> creates a "wasted" character array.
>
> --
> Jon Skeet - <(E-Mail Removed)>
> http://www.pobox.com/~skeet
> If replying to the group, please do not mail me too

Hi,

I've check on the web for a string reverse function and this one on many places:

public static string StrRev(string s)
{

if (s.Length == 1)

return s;

else

return StrRev( s.Substring(1) ) + s.Substring(0,1);

}

Now, this doesn't work when you put an empty string and produce a StackOverflowException, so we add a condition at the begining of the function:

public static string StrRev(string s)

{

if (s.Length == 0)

return s;

if (s.Length == 1)

return s;

else

return StrRev( s.Substring(1) ) + s.Substring(0,1);

}

Hope this helps, Tomer.

<"compulim" <123>> wrote:
> The original one also fails with null value. But for performance reason, I
> agree adding "null" and "length < 2" condition.
>
> But more method invocation will leads to poor performance. The temporary
> charArray in my approach won't take up much memory and able to GC once it
> left the method.
>
> What do you think?

Obviously the recursion is a bad idea, but the version I posted is,
IMO, better than your alternative. The temporary char array will take
up the same amount of space as the original string, which *might* be
very large. Although it will be *eligible* for garbage collection as
soon as the method returns, that doesn't mean it's "free" - you don't
want to stress the GC if you don't have to.

The speed will of my solution partly depends on whether calls to
StringBuilder.Append(char) is inlined or not. One alternative is to
prepopulate the StringBuilder with the requisite number of chars, and
then use the indexer to set the characters - I would imagine the
indexer is more likely to be inlined.

--
Jon Skeet - <(E-Mail Removed)>
http://www.pobox.com/~skeet
If replying to the group, please do not mail me too

Jon Skeet [C# MVP] <(E-Mail Removed)> wrote:
> Obviously the recursion is a bad idea, but the version I posted is,
> IMO, better than your alternative. The temporary char array will take
> up the same amount of space as the original string, which *might* be
> very large. Although it will be *eligible* for garbage collection as
> soon as the method returns, that doesn't mean it's "free" - you don't
> want to stress the GC if you don't have to.
>
> The speed will of my solution partly depends on whether calls to
> StringBuilder.Append(char) is inlined or not. One alternative is to
> prepopulate the StringBuilder with the requisite number of chars, and
> then use the indexer to set the characters - I would imagine the
> indexer is more likely to be inlined.

I decided to run a little benchmark on the desktop framework, and
calling Append repeatedly is a bit faster than using the indexer.

Using Array.Reverse is significantly faster than either of them, which
surprised me.

I'd certainly want to test on the Compact Framework if I thought this
was critical though - as the difference between the two is largely
going to be about garbage collection times and inlining, the difference
in framework could make a significant difference in timing.

--
Jon Skeet - <(E-Mail Removed)>
http://www.pobox.com/~skeet
If replying to the group, please do not mail me too

Jon Skeet [C# MVP] <(E-Mail Removed)> wrote:
> I'd certainly want to test on the Compact Framework if I thought this
> was critical though - as the difference between the two is largely
> going to be about garbage collection times and inlining, the difference
> in framework could make a significant difference in timing.

Just for kicks, I tried it on the Compact Framework, and it turns out
that the situations are reversed:

Desktop:
Array.Reverse: 4.5 seconds
StringBuilder.Append: 13.3 seconds
Indexer in StringBuilder: 16.6 seconds

Compact Framework: (far fewer iterations, of course)
Array.Reverse: 114 seconds
StringBuilder.Append: 25 seconds
Indexer in StringBuilder: 20 seconds


From being about 3 times as fast, Array.Reverse becomes about 5 or 6
times as slow as the other methods!

Just goes to show what a difference it makes being on a different
framework...

--
Jon Skeet - <(E-Mail Removed)>
http://www.pobox.com/~skeet
If replying to the group, please do not mail me too

What about using the Microsoft.VisualBasic.Strings.StrReverse? How fast is
that?

And what is the indexer method you use? I only saw the append method...

Tomer.


"Jon Skeet [C# MVP]" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> Jon Skeet [C# MVP] <(E-Mail Removed)> wrote:
> > I'd certainly want to test on the Compact Framework if I thought this
> > was critical though - as the difference between the two is largely
> > going to be about garbage collection times and inlining, the difference
> > in framework could make a significant difference in timing.
>
> Just for kicks, I tried it on the Compact Framework, and it turns out
> that the situations are reversed:
>
> Desktop:
> Array.Reverse: 4.5 seconds
> StringBuilder.Append: 13.3 seconds
> Indexer in StringBuilder: 16.6 seconds
>
> Compact Framework: (far fewer iterations, of course)
> Array.Reverse: 114 seconds
> StringBuilder.Append: 25 seconds
> Indexer in StringBuilder: 20 seconds
>
>
> From being about 3 times as fast, Array.Reverse becomes about 5 or 6
> times as slow as the other methods!
>
> Just goes to show what a difference it makes being on a different
> framework...
>
> --
> Jon Skeet - <(E-Mail Removed)>
> http://www.pobox.com/~skeet
> If replying to the group, please do not mail me too