判断给定数字是否是回文的最佳优化方法

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

方法二

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

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

我不明白为什么第二种在进行转换时比第一种更快，第一种方法是通过将每个数字分解并将它们拼接回一个临时变量来实现反转。

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

（由于我是一个初学者，所以我不理解转换方法背后的工作原理，因此额外的帮助将非常感激。）

- Gagan Deep Singh

---

基本上：使用 Python 代码进行工作可能需要更长时间，因为底层的已编译代码支持 str()、[::-1] 和 int() 函数可以被您的 CPU 更快地执行。 - Martijn Pieters

Answer 1

因为Python需要完成更多的工作，所以你的第一个版本需要更长时间来运行。

当使用CPython（从python.org下载或在计算机上找到的python或python3可执行文件）时，你的Python代码被编译成字节码，然后核心评估循环依次执行每个字节码。该大循环是由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

- Martijn Pieters

Answer 2

一行代码，但思路与 @Martijn Pieters 相同

import time
from datetime import timedelta


start_time = time.monotonic()

s = input()

print({True: "Palindrome", False: "Not palindrome"}[s == s[::-1]]) # dictionary based output 
 


end_time = time.monotonic()
print(f'Duration: {timedelta(seconds=end_time - start_time)}')

#nitin
#Palindrome
#Duration: 0:00:02.519435

#[Program finished] 

- Subham