加速Python 3.4代码

Question

我有一个问题，我需要找到给定数字后的下一个最大回文，但是我遇到了运行时间超过1秒的问题。有什么办法可以加速这个代码吗？

inp = input() 
if inp == '9' * len(inp): 
    print('1' + ('0' * (len(inp) - 1)) + '1') #ran into a problem where 999 would give 9109 
else: 
num = list(inp) 
oldnum = int(inp) 
if len(num) % 2 == 0: #for even length numbers 
    for i in range(len(num) // 2): 
     num[len(num) // 2 + i] = num[len(num) // 2 - 1 - i] 
    if int("".join(num)) > oldnum: 
     print("".join(num)) 
    else:     
#sometimes the palindrome was smaller eg: 1199 --> 1111 
     num[len(num) // 2 - 1] = str(int(num[len(num) // 2 - 1]) + 1) 
     num[len(num) // 2] = str(int(num[len(num) // 2]) + 1) 
     print("".join(num)) 
else: #basically the same but for odd length numbers 
    for i in range(len(num) // 2): 
     num[len(num) // 2 + 1 + i] = num[len(num) // 2 - 1 - i] 
    if int("".join(num)) > oldnum: 
     print("".join(num)) 
    else: 
     num[len(num) // 2] = str(int(num[len(num) // 2]) + 1) 
     print("".join(num)) 

Answer 1

这是我怎么会打破它，

# simple version, easy to understand and fast enough 
# up to maybe a thousand digits 

def next_palindrome(n): 
    """ 
    Find the first integer p such that p > n and p is palindromic 
    """ 
    # There are two forms of palindrome: 
    # even number of digits,  abccba 
    # odd number of digits,  abcba 
    # Find abc 
    s = str(n) 
    abc = s[:(len(s) + 1) // 2] 

    # There are six possibilites for p: 
    #  
    # abcpq < abcba -> p = abcba 
    # abcpq >= abcba -> p = ab(c + 1)ba  (with carries as needed) 
    # abcpqr == 999999 -> p = 1000001   *(num digits + 1) 
    # 
    # abcpqr < abccba -> p = abccba 
    # abcpqr >= abccba -> p = ab(c+1)(c+1)ba (with carries as needed) 
    # abcpq == 99999 -> p = 100001   *(num digits + 1) 
    # 
    # *Note that the even-number-of-9s case is properly handled by 
    # odd-digits-with-carry, but odd-number-of-9s needs special handling 
    # 
    # Make basis substrings 
    cba = abc[::-1] 
    ba = cba[1:] 
    abc1 = str(int(abc) + 1) 
    cba1 = abc1[::-1] 
    ba1 = cba1[1:] 
    # Assemble candidate values 
    candidates = [ 
     int(abc + ba),  # abcba 
     int(abc1 + ba1),  # ab(c+1)ba 
     int(abc + cba),  # abccba 
     int(abc1 + cba1),  # ab(c+1)(c+1)ba 
     int(abc1[:-1] + ba1) # handles odd-number-of-9s 
    ] 
    # Find the lowest candidate > n 
    return min(c for c in candidates if c > n) 

def main(): 
    while True: 
     n = int(input("\nValue for n (or -1 to quit): ")) 
     if n == -1: 
      break 
     else: 
      print("Next palindrome is {}".format(next_palindrome(n))) 

if __name__ == "__main__": 
    main() 

它运行像

Value for n (or -1 to quit): 12301 
Next palindrome is 12321 

Value for n (or -1 to quit): 12340 
Next palindrome is 12421 

Value for n (or -1 to quit): 99999 
Next palindrome is 100001 

Value for n (or -1 to quit): 123001 
Next palindrome is 123321 

Value for n (or -1 to quit): 123400 
Next palindrome is 124421 

Value for n (or -1 to quit): 999999 
Next palindrome is 1000001 

Value for n (or -1 to quit): -1 

---

编辑：我还以为你在谈论可能100位数字。数以百万计的数字使得它值得花更多的时间减少字符串操作和类型转换的数量，就像这样：

# Super-efficient version 
# for playing with million-digit palindromes 

def str_lt(x, y): 
    """ 
    Take two integer strings, `x` and `y`, 
     return int(`x`) < int(`y`) 
    """ 
    return len(x) < len(y) or x < y 

def str_add_1(n): 
    """ 
    Given an integer string `n`, 
     return str(int(n) + 1) 
    """ 
    # find the first non-9 digit, starting from the right 
    for i in range(len(n) - 1, -1, -1): 
     if n[i] != '9': 
      return n[:i] + str(int(n[i]) + 1) + '0' * (len(n) - i - 1) 
    # string was all 9s - overflow 
    return '1' + '0' * len(n) 

def next_palindrome(n): 
    """ 
    For non-negative integer `n` (as int or str) 
     find the first integer p such that p > n and p is palindromic 
    Return str(p) 

    Note: `n` must be well-formed, ie no leading 0s or non-digit characters 
    """ 
    # Make sure n is a string 
    if not isinstance(n, str): 
     n = str(n) 

    # There are three forms of palindrome: 
    #   single digit,  x (ab == '') 
    # even number of digits, abba (x == '') 
    # odd number of digits, abxba (x is single digit) 
    #  
    if len(n) == 1: 
     # take care of single digit case 
     return '11' if n == '9' else str_add_1(n) 
    else: 
     # There are six possibilites for p: 
     #  
     # (1) abqr < abba -> p = abba 
     # (2) abqr >= abba -> p = a(b+1)(b+1)a (with carries as needed) 
     # (3) abqr == 9999 -> p = 10001   (carry results in overflow) 
     # 
     # (4) abxqr < abxba -> p = abxba 
     # (5) abxqr >= abxba -> p = ab(x + 1)ba (with carries as needed) 
     # (6) abxqr == 99999 -> p = 100001   (carry results in overflow) 
     # 
     # Find ab, x, qr 
     half = len(n) // 2 
     ab = n[  : half] 
     x = n[ half:-half] # a 0- or 1-digit string 
     qr = n[-half:  ] 

     ba = ab[::-1] 
     if str_lt(qr, ba): 
      # solve cases (1) and (4) 
      return "".join([ab, x, ba]) 

     if x == '9': 
      # do manual carry from x 
      ab1 = str_add_1(ab) 
      ba1 = ab1[::-1] 
      if len(ab1) > len(ab): 
       # carry results in overflow - case (6) 
       return ab1 + ba1 
      else: 
       # carry but no overflow - case (5) 
       return "".join([ab1, '0', ba1]) 

     if x: 
      # no carry - case (5) 
      return "".join([ab, str_add_1(x), ba]) 

     # x == '' 
     ab1 = str_add_1(ab) 
     ba1 = ab1[::-1] 
     if len(ab1) > len(ab): 
      # carry results in overflow - case (3) 
      return ab1[:-1] + ba1 
     else: 
      # no overflow - case (2) 
      return ab1 + ba1 

在我的机器，这个发现一百万位数字回文在小于0.002秒（VS约18.5秒你的代码）。

Answer 2

虽然你的代码对我来说不到一秒钟。但为什么这么多的代码只是找到一个plaindrome。为什么不能简单的做

def next_palindrome(num): 
    while True: 
     if str(num) == str(num)[::-1]: 
      break 
     num += 1 
    return num