[Update] I've been told that my solution isn't really “fair“ as it uses char[] data as parameters...a fair function call for this algorithm should accept merely a string as a parameter, i.e. “static bool isPalindrome(string s)” since most of us don't make a habit of passing char[] data around classes/dll's, plus the method should do all of the work (blackbox theory...aka encapsulation) itself. I somewhat agree with the first argument, agree less with the second argument (in this case at least)...but love a good challenge; thus I've started on a standalone C# class with said method signature/constraints that should give comparable performance. Stay tuned (even though it might not be pretty ;-) ) [/Update]
I'm bored. Yup, really really bored. Not a whole lot going on down here as will be demonstrated by this post. I decided to take another look at my palindrome code and tighten it up a bit...running my initial code at one million iterations was leading to some pretty horendous performance (~14891 milliseconds on a 2 ghz p4/512k cache (I believe it is called Northwood?)) compared to the other algorithms on the channel9 post...yes, I tested all of the C# solutions in the comments; see “bored” above. Then I realized why my solution was choking: I didn't write it to stand up to iterative testing, it was a one shot algorithm for formatting the string and checking to see if it was a palindrome...everything was done in the same loop. Moving the formatting/splitting code out of the loop gives an incredible boost as this only needs to be done once for the string, then the iterations can begin on the new string. I knew I was on to something by using char[] data when I initially wrote the algorithm a while back, I knew it _could_ be wicked fast as it's pretty well known that char's are quicker than strings. Lo and behold I was indeed correct. The fastest managed solution I found in the comments was by ezu on page 3; I consistently received results in the ~280 millisecond range for a million iterations with his code using the palindrome “A man, a plan, a canal...Panama!“:
static bool isPalindrome(string t)
{
if(t == null || t.Length == 0)
return false;
bool r = true;
for(int i = 0, n = t.Length -1; i < n && r; i++, n--)
r = t[i] == t[n];
return r;
}
Note that this solution doesn't handle whitespace nor punctuation (actually, almost none of the solutions on channel9 do surprisingly..including the folks who won). So, I moved those routines out of my initial code and into their own methods to clean up the string first (full code here), then passed it to the above algorithm. 280 milliseconds for a million iterations is _fast_. My code == faster :-) And I didn't even change my core algorithm. Here's my take:
Algorithm to strip spaces/punctuation from the string:
static private string formatString(string stringToFormat)
{
char[] stringChars = stringToFormat.ToCharArray();
foreach (char character in stringToFormat)
{
if (!char.IsLetterOrDigit(character))
{
stringToFormat = stringToFormat.Replace(character.ToString(), "").ToLower();
}
}
return stringToFormat;
}
Routine to check for palinindromeness:
static private bool isPalindrome (char[] firstHalf, char[] secondHalf)
{
bool flag = true;
int half = firstHalf.Length;
for (int i=0;i < half; i++)
{
if (firstHalf[i] != secondHalf[i])
{
flag = false;
}
}
return flag;
}
Rroutine that builds the two char[] parameters for the above routine:
static private void buildArrays(ref string testString, ref char[] firstHalf, ref char[] secondHalf)
{
int half = (testString.Length/2);
firstHalf = testString.Substring(0, half).ToCharArray();
secondHalf = testString.Substring(half).ToCharArray();
Array.Reverse(secondHalf);
}
Running the same palindrome at a million iteration yields a result of ~80 milliseconds (about 3.5 times faster than ezu's), and I've seen it go as low as 60...but also as high as 100. It'll do ten million iterations in just under a second. Char data is almost always faster than the equivalent string walking/looping construct, and when doing most types of string manipulation I usually break it down into a char[] first. I'm guessing regex's would be on an order of magnitude worse in performance than even direct string manipulation, but I didn't see a managed regex solution and didn't roll one myself for testing (come on...I wasn't that bored!). Full code for my solution is posted here (it's a console application). The counter starts immediately after checking the string for palindromeness and after specifying the number of iterations. Code commentary is welcome, as are alternate solutions...can anyone get it below 50 milliseconds/million iterations? I'm sure it could be done in C/C++. Bring it on!
Posted
Oct 13 2004, 05:40 PM
by
Jayson Knight