Palindrome finder: help find ways to speed up?

[Mike C. Fletcher]

Here's an algorithm that should give you a decent speedup (it's based on 
the suggestions that I _think_ Steven was giving you)...

words = [...]
backwardMap = {...} # last-char to reversed word-list, construct from words

for word in words:
    for back in backwardMap[ word[-1]]:
       subset = min(len(word),len(back))
       if word[:subset] == back[:subset]:
          good_chance_you_have_one_so_explore_further()

For even faster operation, pre-calculate and store the word-lengths in 
the backwardMap so that you don't have to calculate them each time. 

Basically, this should reduce the search space to 1/64th of total (or 
so) for each word with a simple O(1) hash-table lookup, with each check 
considerably faster in exchange for an O(n) setup fee (reversing and 
taking the length of each word, then adding to the dictionary).  Key is 
setting up the correct data-structures so that when you're doing the 
actual run-time searches you can rapidly whittle down the search space 
to a reaidly-processed sub-set.  You see the same thing in fuzzy-text 
searching, BTW.

You can also do neat things such as using the tails beyond subset to 
lookup third/fourth words in the middle (you need a forward map to make 
that work efficiently, of course).  Keep in mind that if you find a 
palindrome set which exactly matches on both sides you get the 
possibility of having an inifinite sequence of those nesting in, so 
you'll want a mechanism to stop that at some point :) .

Enjoy,
Mike


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.
>
>Jonedary 
>
>  
>
>>A smarter search would do better.  One approach would be to build
>>the palindrome from both ends instead of from just one end.  For
>>example, suppose your code understood that a palindrome starting
>>with 'orange' must end with a word 'o', 'ro', 'aro', 'naro',
>>'gnaro', 'egnaro', or a word ending with 'egnaro'.  If there are
>>no such words, it can skip 1/n of the search space, namely all the
>>combinations which start with 'orange'.
>>    
>>
_______________________________________
  Mike C. Fletcher
  Designer, VR Plumber, Coder
  http://members.rogers.com/mcfletch/