优化Python代码

关于优化此 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

我认为这段代码的大部分时间都花在将字符串与整数相互转换上。剩下的就是对字符串进行切片并在 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)

这个简单的更改使您的代码对于数字的速度提高了约 100 倍，其中inc不需要调用，对于需要调用的号码，速度大约快 3 倍。

为了做得更好，我认为你需要完全避免转换为 int 。这意味着不使用普通的 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)，并且通过让循环更新数组的两半而不是只更新左半部分然后在最后反映它，速度大约提高了一倍。