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

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

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

我不明白为什么发生转换的第二种方法比通过打破每个数字并将它们重新加入临时变量来反转数字的方法快。

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

（由于我是初学者，我不明白转换方法在幕后是如何工作的，因此非常感谢额外的帮助。）

Answer 1

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

当使用 CPython（你可以从 python.org 下载python或者python3在你的计算机上找到的 Python 实现）时，你的 Python 代码被编译成bytecode，然后核心评估循环在一个大循环中依次执行每个字节码。这个大循环是用 C 实现的，并编译为适合您特定操作系统和 CPU 架构的机器代码。内置int和str类型也完全用 C 代码实现，包括[...]在对它们使用索引或使用运算符时运行的代码。

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

该dis模块可以向您展示生成的字节码（作为人类可读的表示）。这是您的第一个函数的字节码：

>>> 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

您不必了解这些输出中每个字节码的影响，但您可以看到一个列表要大得多。

所以，int(str(number)[::-1])做大量的工作太多，但因为工作在本机代码，一个比一个大循环，必须处理所有可能的字节码操作更高效的完成它的速度更快。

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

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

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

以上 (ab) 使用 Python 3赋值表达式语法。你也可以写成：

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

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

使用timeit模块比较方法：

>>> 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