re: More on string reversal!

Mladen — Tue, 18 Jul 2006 06:24:22 GMT

have you tried this one?

public string Reverse(string x)
{
char[] charArray = new char[x.Length];
int len = x.Length - 1;
for (int i = 0; i <= len; i++)
charArray[i] = x[len-i];
return new string(charArray);
}

re: More on string reversal!

Adam Machanic — Tue, 18 Jul 2006 23:20:41 GMT

Mladen:

Just tested it. It falls halfway between methods 2 and 3 (2 being the 2nd fastest, after 5).

re: More on string reversal!

Mladen — Wed, 19 Jul 2006 05:52:03 GMT

hmm... that's interesting...

everytime i try it that one was faster than XOR.

re: More on string reversal!

Adam Machanic — Wed, 19 Jul 2006 14:31:22 GMT

How are you testing, and what are you using to get the timings?

I am simply running every method in a loop 10000 times:

for (int i = 0; i<10000; i++)
{
string s1 = Reverse1("abcdefghijklmnopqrstuvwxyz");
string s2 = Reverse2("abcdefghijklmnopqrstuvwxyz");
string s3 = Reverse3("abcdefghijklmnopqrstuvwxyz");
string s4 = Reverse4("abcdefghijklmnopqrstuvwxyz");
string s5 = Reverse5("abcdefghijklmnopqrstuvwxyz");
string s6 = Reverse6("abcdefghijklmnopqrstuvwxyz");
}

I'm getting the timings using VS's profiler, in instrumentation mode, and looking at the "inclusive of children" column to get the final reported times.

re: More on string reversal!

Mladen — Thu, 20 Jul 2006 11:34:18 GMT

well i simply do it like this:
string testString = "1234567890hguidagnrruiasngilrenglirengilrenglaes";
DateTime dtStart = DateTime.Now;
for (int i = 0; i < 1000000; i++)
{
Reverse1(testString);
}
DateTime dtEnd = DateTime.Now;
TimeSpan ts = dtEnd - dtStart;

dtStart = DateTime.Now;
for (int i = 0; i < 1000000; i++)
{
Reverse2(testString);
}
dtEnd = DateTime.Now;
ts = dtEnd - dtStart;

public string Reverse1(string x)
{
char[] charArray = new char[x.Length];
int len = x.Length - 1;
for (int i = 0; i <= len; i++)
charArray[i] = x[len - i];
return new string(charArray);
}

public string Reverse2(string str)
{
// convert the string to char array
char[] charArray = str.ToCharArray();
int len = str.Length - 1;
for (int i = 0; i < len; i++, len--)
{
charArray[i] ^= charArray[len];
charArray[len] ^= charArray[i];
charArray[i] ^= charArray[len];
}
return new string(charArray);
}

is there something wrong with this way that i'm not familiar with?

An average time i get is around 650 ms for reverse1 and 850 for reverse2.
It doesn't matter how many times i run it.

re: More on string reversal!

Adam Machanic — Thu, 20 Jul 2006 15:55:08 GMT

The problem with that method is that it's "wall clock" time -- during the middle of invocation of one of the methods the GC could kick in, some other unrelated process might require a bunch of time, etc -- that will skew the results. The profiler, AFAIK, shows only time spent actually doing your task, so you don't have all of the other noise and get more accurate results.

That said, I went ahead and tried this method and here are my results (note, I ran each method 2 million times -- I was unable to get consistent results otherwise):

Reverse1: 1892.7216 ms
Reverse2: 660.9504 ms
Reverse3: 1892.7216 ms
Reverse4: 4196.0336 ms
Reverse5: 490.7056 ms
Reverse6: 2042.9376 ms
Reverse7: 510.7344 ms

Note that Reverse5 is your XOR method and Reverse7 is your new method. So at least on my box, XOR still wins.

Here is the code I used to loop:

DateTime theStart = DateTime.Now;
for (int i = 0; i < 1000000; i++)
{
string s1 = Reverse1("abcdefghijklmnopqrstuvwxyz");
s1 = Reverse1(s1);
}
DateTime theEnd = DateTime.Now;
TimeSpan ts = theEnd - theStart;
Console.WriteLine(ts.TotalMilliseconds.ToString());

theStart = DateTime.Now;
for (int i = 0; i < 1000000; i++)
{
string s2 = Reverse2("abcdefghijklmnopqrstuvwxyz");
s2 = Reverse2(s2);
}
theEnd = DateTime.Now;
ts = theEnd - theStart;
Console.WriteLine(ts.TotalMilliseconds.ToString());

... (repeat for each up to Reverse7)

re: More on string reversal!

Mladen — Fri, 21 Jul 2006 06:07:53 GMT

Cool. thanx for explaining that.

In the end though... who needs to reverse a string 2 million times, right? :)))

If you haven't yet go take a look at how Greg Young did it.
It's in the comments:
http://weblogs.sqlteam.com/mladenp/archive/2006/03/19/9350.aspx