Оптимизированный способ проверки, является ли данный номер палиндромом

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

Сравнивая время выполнения, я обнаружил, что первый подход занимает больше времени, чем второй.

Я не понимаю, почему второй подход, где происходит преобразование, происходит быстрее, чем тот, который обращает число, разбивая каждую ди git и соединение их обратно во временную переменную.

Могут ли они быть дальше оптимизированы или есть ли лучший способ проверить, является ли число палиндромом или нет?

(Поскольку я начинающий, я делаю не понимаю, как конверсионный подход работает за кулисами, поэтому дополнительная помощь будет очень полезна.)

Answer 1

Ваша первая версия занимает больше времени, потому что Python должен выполнять больше работы.

При использовании CPython (реализация Python, которую вы загрузите с python .org или найдет как python или python3 исполняемый на вашем компьютере), ваш код Python компилируется в байт-код , а затем core оценка l oop выполняет каждый байт-код по очереди в большом l oop. Этот большой l oop реализован в C и скомпилирован в машинный код, подходящий для вашей конкретной архитектуры c OS и 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]) также выполняет много работы, но это быстрее, потому что работа выполняется в нативном коде, который более эффективен, чем большой l oop, который должен обрабатывать все возможные операции с байт-кодом.

Для очень больших чисел может быть более эффективно записать все oop, которые рано выходят, работая извне (возьмите величину число от math.log10(...), соедините его с 1 и продвигайтесь к среднему тестированию и возвращению в тот момент, когда вы получите результат False), но я подозреваю, что даже тогда выигрывает преобразование строк.

Единственное улучшение small , которое я могу предложить, заключается в том, что вы не конвертируете обратно в 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