Palindrome finder: help find ways to speed up?

[Steven Taschuk]

Quoth I:
  [...]
> My suggestion is that, if the word list is, say,
> 	abandon
> 	major
> 	wombat
> 	articulate
> 	orange
> 	royal
> then the program could start with 'abandon', notice that no word
> in the word list ends with 'a', and immediately, er, abandon
> trying to find palindromes starting with this word, and move on to
> finding palindromes starting with 'major'.  [...]

Having too much time on my hands today, I went ahead and
implemented this idea.  The results are encouraging; times in
seconds to find all n-word palindromic phrases using a list of
(allegedly) the thousand most common English words:
    n      original     pruning
    1        < 1            2
    2        140            3
    3     > 1000           15
    4          ?           45
    5          ?          500
(I gave up on running the original for n >= 3.)

I think this shows that, in this case, changing the algorithm is a
better first step than changing languages.

(Caveat: The two programs are strictly speaking not comparable.
For example, the original implementation requires all words in the
palindrome to be distinct, while mine does not.  But this
introduces a bias against my version, which searches a larger
space.)

I'm a bit reluctant to post my pruning search module, since it's
475 lines long.  I'll email it to interested posters on request.
(I'll probably submit it to Useless Python shortly too, but no
doubt it'll take a while to appear on the site.)

-- 
Steven Taschuk                 Go draw a war dog.
staschuk at telusplanet.net       Won't safe be fast now?