优化Python代码

Question

有没有什么建议可以让这个Python代码在寻找下一个回文数时更快呢？

输入的数字可以有1000000位。

已添加评论

#! /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

你不需要去找回文数，其实可以直接生成一个。

把输入的数字分开，然后把它反转过来。如果生成的数字太小了，就把左边的部分加一，然后再反转一次：

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)

Answer 2

编辑

没事了，直接看看这个页面： http://thetaoishere.blogspot.com/2009/04/finding-next-palindrome-given-number.html

Answer 3

我觉得这段代码大部分时间都花在把字符串转换成整数，然后再转换回来。剩下的时间就是在处理字符串和在Python解释器里来回跳转。针对这三件事，我们能做些什么呢？代码里有一些不必要的转换，我们可以把它们去掉。我觉得字符串切片是没法避免的。为了减少在解释器里的时间，你只需要尽量写少一点代码 :-) 把所有代码放在函数里也会有帮助。

你程序底部的代码，试图快速猜测以避免调用 inc()，里面有一两个bug。以下是我可能会这样写那部分代码：

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)

这个简单的改动让你的代码在不需要调用 inc 的情况下快了大约100倍，而在需要调用的情况下快了大约3倍。

想要更快，我觉得你需要完全避免转换成整数。这意味着要在不使用普通Python整数加法的情况下，手动增加数字的左半部分。你可以使用一个 array，然后手动执行加法算法：

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()

对于需要增加的数字，这样做又快了大约9倍。

你可以通过使用 while 循环代替 for i in range(n - h - 1, -1, -1) 来稍微加快速度，再通过让循环同时更新数组的两个半部分，而不仅仅是更新左半部分，然后最后再反射回来，这样又能快大约两倍。