python - 检查给定数字是否为回文式的优化方法

Question

我编写了两个函数来检查数字(整数)是否为回文。

第一个函数在不影响数据类型的情况下反转数字
第二个函数将数字转换为字符串，反转字符串，
然后将其转换回整数以比较给定的数字。

方法＃1

def is_palindrome(n):
    """
        This function checks if a number is a Palindrome
        or not.
    """
    result = 0
    temp = n
    while temp > 0:
        result *= 10
        result += temp % 10
        temp //= 10
    return result == n

方法＃2

def is_palindrome_str(n):
    """
        This function checks if a number is a Palindrome
        or not.
    """
    return int(str(n)[::-1]) == n

通过比较执行时间，我发现第一种方法比第二种方法花费的时间更长。

我不明白，为什么进行转换的第二种方法比通过破除每个数字并将它们重新加入temp变量来反转数字的方法更快。

是否可以进一步优化它们？或者是否有更好的方法来检查数字是否为回文？

(由于我是初学者，所以我不了解转换方法在幕后的工作方式，因此我们将不胜感激。

Answer 1

您的第一个版本需要更长的时间，因为Python必须做更多的工作。

使用CPython时(Python实现可从python.org下载或在计算机上找到python或python3可执行文件)，Python代码将编译为字节码，然后core evaluation loop依次执行每个字节码，形成一个大循环。这个大循环用C实现，并编译为适合您特定的OS和CPU架构的机器代码。内置的int和str类型也完全用C代码实现，包括在它们上使用[...]索引或使用运算符时运行的代码。

那么，使一个版本很快而另一个版本变慢的是C代码执行的操作的相对速度与使用大量Python代码(转换为字节码)执行相同操作的相对速度。

dis module可以显示产生了什么字节码(作为人类可读的表示形式)。这是您的第一个功能的字节码:

>>> import dis
>>> dis.dis(is_palindrome)
  6           0 LOAD_CONST               1 (0)
              2 STORE_FAST               1 (result)

  7           4 LOAD_FAST                0 (n)
              6 STORE_FAST               2 (temp)

  8     >>    8 LOAD_FAST                2 (temp)
             10 LOAD_CONST               1 (0)
             12 COMPARE_OP               4 (>)
             14 POP_JUMP_IF_FALSE       46

  9          16 LOAD_FAST                1 (result)
             18 LOAD_CONST               2 (10)
             20 INPLACE_MULTIPLY
             22 STORE_FAST               1 (result)

 10          24 LOAD_FAST                1 (result)
             26 LOAD_FAST                2 (temp)
             28 LOAD_CONST               2 (10)
             30 BINARY_MODULO
             32 INPLACE_ADD
             34 STORE_FAST               1 (result)

 11          36 LOAD_FAST                2 (temp)
             38 LOAD_CONST               2 (10)
             40 INPLACE_FLOOR_DIVIDE
             42 STORE_FAST               2 (temp)
             44 JUMP_ABSOLUTE            8

 12     >>   46 LOAD_FAST                1 (result)
             48 LOAD_FAST                0 (n)
             50 COMPARE_OP               2 (==)
             52 RETURN_VALUE

这是第二个:

>>> dis.dis(is_palindrome_str)
  6           0 LOAD_GLOBAL              0 (int)
              2 LOAD_GLOBAL              1 (str)
              4 LOAD_FAST                0 (n)
              6 CALL_FUNCTION            1
              8 LOAD_CONST               1 (None)
             10 LOAD_CONST               1 (None)
             12 LOAD_CONST               2 (-1)
             14 BUILD_SLICE              3
             16 BINARY_SUBSCR
             18 CALL_FUNCTION            1
             20 LOAD_FAST                0 (n)
             22 COMPARE_OP               2 (==)
             24 RETURN_VALUE

您不必了解每个字节码在这些输出中的作用，但是您可以看到一个 list 更大。

因此， int(str(number)[::-1])也可以完成很多工作，但是它更快，因为工作是在 native 代码中完成的，它比必须处理所有可能的字节码操作的大循环更有效。

对于 非常大的数字，编写一个循环的方式可能会更有效，该循环可以通过从外部进行操作来提前退出(取 math.log10(...) 中数字的大小，将其与1配对，然后朝中间测试返回。当您获得 False结果的那一刻)，但我怀疑即使这样，字符串转换也能胜出。

我可以提供的唯一小改进是您不会转换回 int():

def is_palindrome_str_faster(n):
    return (v := str(n)) == v[::-1]

上面的(ab)使用Python 3 assignment expression syntax。您也可以将其编写为:

def is_palindrome_str_faster(n):
    v = str(n)
    return v == v[::-1]

几乎没有字节码产生或性能上的差异。

使用 timeit module比较方法:

>>> timeit('ip(12345654321)', 'from __main__ import is_palindrome as ip')
1.8687424899544567
>>> timeit('ip(12345654321)', 'from __main__ import is_palindrome_str as ip')
0.5467583388090134
>>> timeit('ip(12345654321)', 'from __main__ import is_palindrome_str_faster as ip')
0.42572025093249977