python - 优化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

我认为这段代码中的大部分时间都花在将字符串转换为整数并返回。剩下的就是在 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并“手动”执行加法算法:

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) ，并且通过让循环更新数组的两半而不是仅更新左半部分然后在最后反射(reflect)它，速度再次提高了大约两倍。