Optimizing python code

Question

Any tips on optimizing this python code for finding next palindrome:

Input number can be of 1000000 digits

COMMENTS ADDED

#! /usr/bin/python
    def inc(lst,lng):#this function first extract the left half of the string then
                     #convert it to int then increment it then reconvert it to string
                     #then reverse  it and finally append it to the left half. 
                     #lst is input number and lng is its length
        if(lng%2==0):

            olst=lst[:lng/2]
            l=int(lng/2)
            olst=int(olst)
            olst+=1
            olst=str(olst)
            p=len(olst)
            if l<p:
                olst2=olst[p-2::-1]
            else:
                olst2=olst[::-1]
            lst=olst+olst2
            return lst
        else:
            olst=lst[:lng/2+1]
            l=int(lng/2+1)
            olst=int(olst)
            olst+=1
            olst=str(olst)
            p=len(olst)
            if l<p:
                olst2=olst[p-3::-1]
            else:
                olst2=olst[p-2::-1]
            lst=olst+olst2
            return lst



    t=raw_input()
    t=int(t)

    while True:
        if t>0:
            t-=1
        else:
            break

        num=raw_input()#this is input number
        lng=len(num)
        lst=num[:]

        if(lng%2==0):#this if find next palindrome to num variable
                     #without incrementing the middle digit and store it in lst.

            olst=lst[:lng/2]
            olst2=olst[::-1]
            lst=olst+olst2

        else:
            olst=lst[:lng/2+1]
            olst2=olst[len(olst)-2::-1]
            lst=olst+olst2

        if int(num)>=int(lst):#chk if lst satisfies criteria for next palindrome
            num=inc(num,lng)#otherwise call inc function
            print num
        else:
            print lst

Answer 1

Using strings. n >= 0

from math import floor, ceil, log10


def next_pal(n):
    # returns next palindrome, param is an int
    n10 = str(n)
    m = len(n10) / 2.0
    s, e = int(floor(m - 0.5)), int(ceil(m + 0.5))
    start, middle, end = n10[:s], n10[s:e], n10[e:]
    assert (start, middle[0]) == (end[-1::-1], middle[-1]) #check that n is actually a palindrome
    r = int(start + middle[0]) + 1 #where the actual increment occurs (i.e. add 1)
    r10 = str(r)
    i = 3 - len(middle)
    if len(r10) > len(start) + 1:
        i += 1
    return int(r10 + r10[-i::-1])

Using log, more optized. n > 9

def next_pal2(n):
    k = log10(n + 1)
    l = ceil(k)
    s, e = int(floor(l/2.0 - 0.5)), int(ceil(l/2.0 + 0.5))
    mmod, emod = 10**(e - s), int(10**(l - e))
    start, end = divmod(n, emod)
    start, middle = divmod(start, mmod)
    r1 = 10*start + middle%10 + 1
    i = middle > 9 and 1 or 2
    j = s - i + 2
    if k == l:
        i += 1
    r2 = int(str(r1)[-i::-1])
    return r1*10**j + r2

Answer 2

I think most of the time in this code is spent converting strings to integers and back. The rest is slicing strings and bouncing around in the Python interpreter. What can be done about these three things? There are a few unnecessary conversions in the code, which we can remove. I see no way to avoid the string slicing. To minimize your time in the interpreter you just have to write as little code as possible :-) and it also helps to put all your code inside functions.

The code at the bottom of your program, which takes a quick guess to try and avoid calling inc(), has a bug or two. Here's how I might write that part:

def nextPal(num):
    lng = len(num)
    guess = num[:lng//2] + num[(lng-1)//2::-1]  # works whether lng is even or odd
    if guess > num:  # don't bother converting to int
        return guess
    else:
        return inc(numstr, n)

This simple change makes your code about 100x faster for numbers where inc doesn't need to be called, and about 3x faster for numbers where it does need to be called.

To do better than that, I think you need to avoid converting to int entirely. That means incrementing the left half of the number without using ordinary Python integer addition. You can use an array and carry out the addition algorithm "by hand":

import array

def nextPal(numstr):
    # If we don't need to increment, just reflect the left half and return.
    n = len(numstr)
    h = n//2
    guess = numstr[:n-h] + numstr[h-1::-1]
    if guess > numstr:
        return guess

    # Increment the left half of the number without converting to int.
    a = array.array('b', numstr)
    zero = ord('0')
    ten = ord('9') + 1
    for i in range(n - h - 1, -1, -1):
        d = a[i] + 1
        if d == ten:
            a[i] = zero
        else:
            a[i] = d
            break
    else:
        # The left half was all nines. Carry the 1.
        # Update n and h since the length changed.
        a.insert(0, ord('1'))
        n += 1
        h = n//2

    # Reflect the left half onto the right half.
    a[n-h:] = a[h-1::-1]
    return a.tostring()

This is another 9x faster or so for numbers that require incrementing.

You can make this a touch faster by using a while loop instead of for i in range(n - h - 1, -1, -1), and about twice as fast again by having the loop update both halves of the array rather than just updating the left-hand half and then reflecting it at the end.

Answer 3

EDIT

NVM, just look at this page: http://thetaoishere.blogspot.com/2009/04/finding-next-palindrome-given-number.html

Answer 4

You don't have to find the palindrome, you can just generate it.

Split the input number, and reflect it. If the generated number is too small, then increment the left hand side and reflect it again:

def nextPal(n):
    ns = str(n)
    oddoffset = 0
    if len(ns) % 2 != 0:
        oddoffset = 1

    leftlen = len(ns) / 2 + oddoffset
    lefts = ns[0:leftlen]
    right = lefts[::-1][oddoffset:]
    p = int(lefts + right)
    if p < n:
        ## Need to increment middle digit
        left = int(lefts)
        left += 1
        lefts = str(left)
        right = lefts[::-1][oddoffset:]
        p = int(lefts + right)

    return p

def test(n):
    print n
    p = nextPal(n)
    assert p >= n
    print p

test(1234567890)
test(123456789)
test(999999)
test(999998)
test(888889)
test(8999999)