python - 加速 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 秒的时间内找到一个百万位的回文(而您的代码大约需要 18.5 秒)。