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

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 实现或者会在您的计算机上找到 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

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

所以 int(str(number)[::-1]) 也做了很多工作，但速度更快，因为工作是用本机代码完成的，比必须处理所有可能的字节码操作的大循环更有效。

对于非常大的数字，编写一个从外到内提前退出的循环可能更有效（从[=28=中获取数字的大小） ], 将其与 1 配对并朝着中间测试前进并在获得 False 结果时返回）但我怀疑即使这样字符串转换也会获胜。

我能提供的唯一小改进是您不要转换回int():

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

上面(ab)使用了Python3assignment 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

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]

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

Optimized way for checking if the given number is a Palindrome

python

palindrome

python-3.x

方法 #1

方法 #2