Palindrome finder: help find ways to speed up?

[Dave Brueck]

On Tue, 8 Apr 2003, Jon Brown wrote:

> Steven,
>
> Actually the program does exactly what you describe, except from the inside
> out because it starts in the middle, and it cuts out of the loop if the
> characters don't match.
>
> To look for pals it spins off big, big numbers of combinations, true enough.
> That's what behind the need for speed. Since Python is inherently on the
> pokey side, I expected the slowness but wonder if I'm missing a cool way to
> pick up the pace. But I suspect the solution will involve C++, and I've
> never linked C/C++ with Python.

I wouldn't jump to C/C++ yet - a good algorithm in a slow language often
beats a lesser algorithm in a fast language. Reducing the number of
combinations is very important, as was already pointed out, but you should
also optimize your palindrome checker. For example, rather than testing
character by character you can test if a string is a palindrome by doing
something like (untested):

def IsPal(s):
  r = list(s)
  r.reverse()
  r = ''.join(r)
  c = len(s)/2
  return s[:c] == r[:c]

In Python 2.3 you could even do:

def IsPal(s):
  c = len(s)/2
  return s[:c] == s[::-1][:c]

Also, you should probably call lower() on your input and use strings'
translate method to elminate punctuation and whitespace because

"And E.T. saw waste DNA"

is typically considered a palindrome.

-Dave