优化python-cod

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

我认为这段代码中的大部分时间都花在将字符串转换为整数上。其余的则是在Python解释器中对字符串进行切片和跳跃。这三件事该怎么办？代码中有一些不必要的转换，我们可以删除这些转换。我看不出有什么办法可以避免线切割。为了尽可能减少您在解释器中的时间，您只需编写尽可能少的代码：-），而且将所有代码放入函数中也有帮助。在

程序底部的代码有一两个错误，需要快速猜测以尝试避免调用inc()。我可以这样写这个部分：

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倍。在

为了做得更好，我认为您需要避免完全转换为int。这意味着在不使用普通Python整数加法的情况下递增数字的左半部分。您可以使用array并“手动”执行加法算法：

^{pr2}$

对于需要递增的数字，这又快了9倍左右。在

通过使用while循环而不是for i in range(n - h - 1, -1, -1)可以使这一点变得更快；通过让循环更新数组的两个半部分，而不是只更新左边的一半，然后在末尾反射它，这样可以使速度提高一倍。在

Answer 3

编辑

NVM，看看这个页面：http://thetaoishere.blogspot.com/2009/04/finding-next-palindrome-given-number.html