Palindrome finder: help find ways to speed up?

dromedary camel at oasis.com
Tue Apr 8 18:30:50 CEST 2003


I've written a palidrome finder two ways (see below), both of which
work, but verrrrrry slooooooooooowly. Would anybody out there care to
look over the code and offer an idea or two about how to speed it up?

The first example uses recursion (handy for combining any number of
words); the second example uses for loops (not fast but faster, though
clunkier).

But‹if you suggest a C/C++ wrapper or extension, please please give me
guidance on how to implement it. I've never translated a Python widget
into C/C++.

___________________________________________________

CODE 1 (uses recursion to combine words, then looks for palindromes)

##### Combine 'em
def combinations(alist, numb, blist=[]):
   if not numb: 
      return rPal(''.join(blist))
   for i in range(len(alist)):
      blist.append(alist.pop(i))
      combinations(alist, numb-1, blist)
      alist.insert(i, blist.pop())

##### Look for symmetry
def rPal(w):
   x=0
   y=1
   L=len(w)
   h=L/2
   if L % 2 > 0:
      while x < h:
         if w[h-y]==w[h+y]:
            x=x+1
            y=y+1
            if x == h:
               print w
               break
         else:
            break          
   else:
      while x < h:
         if w[h-y]==w[h+x]:
            x=x+1
            y=y+1
            if x == h:
               print w
               break 
         else:
            break

##### Get a word list
words = open(SOME_WORD_FILE).read().splitlines()

##### Set number of words to combine
n=SOME_NUMBER_OF_WORDS

########################################
##### Call the recursive function to print the palindromes
if __name__ == '__main__': 
   
   combinations(words, n)


^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

CODE 2 (for loops; the example uses three loops, but you can see how
complex it can get for each additional iteration)

##### Get a word list
words = open(SOME_WORD_FILE).read().splitlines()

##### Combine pairs of words into keys and values
for i in words:
   for j in words:
      for k in words:
         if i != j and i != k and j !=k:
            w=i+j+k
            x=0
            y=1
            L=len(w)
            h=L/2
            if L % 2 > 0:
               while x < h:
                  if w[h-y]==w[h+y]:
                     x=x+1
                     y=y+1
                     if x == h:
                        print w
                        break
                  else:
                     break
                     
            else:
               while x < h:
                  if w[h-y]==w[h+x]:
                     x=x+1
                     y=y+1
                     if x == h:
                        print w
                        break 
                  else:
                     break




More information about the Python-list mailing list