Сравнение времени между Python isPalindrome

Я написал в то же время функцию isPalindrome сложности 3 в python. но на удивление их производительность отличается.

def isPalindrome(value):
    i, j = 0, len(value) - 1
    while i < j and value[i] == value[j]:
         i, j = i + 1, j - 1
    return i >= j

def isPalindrome2(value):
    return value == value[::-1]

def isPalindrome3(value):
    res = []
    for c in value:
       res.append(c)
    return value == ''.join(res)

Затем я тестирую его с модулем timeit

import timeit
timeit.timeit(lambda: isPalindrome('abcdefghijklmnopqrstuvzzavutsrqponmlkjihgfedcba'), number=1000000)
timeit.timeit(lambda: isPalindrome2('abcdefghijklmnopqrstuvzzavutsrqponmlkjihgfedcba'), number=1000000)
timeit.timeit(lambda: isPalindrome3('abcdefghijklmnopqrstuvzzavutsrqponmlkjihgfedcba'), number=1000000)

Выход:

  • Для первого: 2.7046061150031164
  • Для второго: 0,2354857140162494
  • Для третьего: 3.201262982998742

Я попытался найти, почему метод 2 занимает так меньше времени, но не смог найти никакого объяснения. Пожалуйста, помогите мне понять, почему, это будет очень полезно.

Второй метод быстрее, потому что большая часть логики выполняется в скомпилированном коде нижнего уровня (C).

trincot 09.04.2022 11:24

Временная сложность не говорит вам, насколько быстр алгоритм, она говорит вам только о том, как изменяется время выполнения в зависимости от размера данных.

Thierry Lathuille 09.04.2022 12:42
Формы c голосовым вводом в React с помощью Speechly
Формы c голосовым вводом в React с помощью Speechly
Пытались ли вы когда-нибудь заполнить веб-форму в области электронной коммерции, которая требует много кликов и выбора? Вас попросят заполнить дату,...
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Будучи разработчиком веб-приложений, легко впасть в заблуждение, считая, что приложение без JavaScript не имеет права на жизнь. Нам становится удобно...
Flatpickr: простой модуль календаря для вашего приложения на React
Flatpickr: простой модуль календаря для вашего приложения на React
Если вы ищете пакет для быстрой интеграции календаря с выбором даты в ваше приложения, то библиотека Flatpickr отлично справится с этой задачей....
В чем разница между Promise и Observable?
В чем разница между Promise и Observable?
Разберитесь в этом вопросе, и вы значительно повысите уровень своей компетенции.
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Клиент для URL-адресов, cURL, позволяет взаимодействовать с множеством различных серверов по множеству различных протоколов с синтаксисом URL.
Четыре эффективных способа центрирования блочных элементов в CSS
Четыре эффективных способа центрирования блочных элементов в CSS
У каждого из нас бывали случаи, когда нам нужно отцентрировать блочный элемент, но мы не знаем, как это сделать. Даже если мы реализуем какой-то...
1
2
32
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Вероятно, во втором случае нарезка выполняется C-кодом, работающим на низком уровне в памяти. В первом случае вам нужно получать элементы один за другим. В третьем вам нужно выполнить итерацию по итератору (созданному синтаксисом for...in), и вам нужно выполнить добавление, которое требует вычислений и проверок, и все это написано в коде Python.

Ответ принят как подходящий

Чтобы узнать, почему определенная функция работает быстрее/медленнее в Python, всегда используйте dis.dis. Функция dis из стандартного модуля dis может дизассемблировать байт-код, в который была скомпилирована функция, поэтому вы можете увидеть, что на самом деле происходит при ее запуске.

Вот разборка трех функций:

import dis
dis.dis(isPalindrome)
  2           0 LOAD_CONST               1 (0)
              2 LOAD_GLOBAL              0 (len)
              4 LOAD_FAST                0 (value)
              6 CALL_FUNCTION            1
              8 LOAD_CONST               2 (1)
             10 BINARY_SUBTRACT
             12 ROT_TWO
             14 STORE_FAST               1 (i)
             16 STORE_FAST               2 (j)

  3          18 LOAD_FAST                1 (i)
             20 LOAD_FAST                2 (j)
             22 COMPARE_OP               0 (<)
             24 POP_JUMP_IF_FALSE       42 (to 84)
             26 LOAD_FAST                0 (value)
             28 LOAD_FAST                1 (i)
             30 BINARY_SUBSCR
             32 LOAD_FAST                0 (value)
             34 LOAD_FAST                2 (j)
             36 BINARY_SUBSCR
             38 COMPARE_OP               2 (==)
             40 POP_JUMP_IF_FALSE       42 (to 84)

  4     >>   42 LOAD_FAST                1 (i)
             44 LOAD_CONST               2 (1)
             46 BINARY_ADD
             48 LOAD_FAST                2 (j)
             50 LOAD_CONST               2 (1)
             52 BINARY_SUBTRACT
             54 ROT_TWO
             56 STORE_FAST               1 (i)
             58 STORE_FAST               2 (j)

  3          60 LOAD_FAST                1 (i)
             62 LOAD_FAST                2 (j)
             64 COMPARE_OP               0 (<)
             66 POP_JUMP_IF_FALSE       42 (to 84)
             68 LOAD_FAST                0 (value)
             70 LOAD_FAST                1 (i)
             72 BINARY_SUBSCR
             74 LOAD_FAST                0 (value)
             76 LOAD_FAST                2 (j)
             78 BINARY_SUBSCR
             80 COMPARE_OP               2 (==)
             82 POP_JUMP_IF_TRUE        21 (to 42)

  5     >>   84 LOAD_FAST                1 (i)
             86 LOAD_FAST                2 (j)
             88 COMPARE_OP               5 (>=)
             90 RETURN_VALUE
dis.dis(isPalindrome2)
  2           0 LOAD_FAST                0 (value)
              2 LOAD_FAST                0 (value)
              4 LOAD_CONST               0 (None)
              6 LOAD_CONST               0 (None)
              8 LOAD_CONST               1 (-1)
             10 BUILD_SLICE              3
             12 BINARY_SUBSCR
             14 COMPARE_OP               2 (==)
             16 RETURN_VALUE
dis.dis(isPalindrome3)
  2           0 BUILD_LIST               0
              2 STORE_FAST               1 (res)

  3           4 LOAD_FAST                0 (value)
              6 GET_ITER
        >>    8 FOR_ITER                 7 (to 24)
             10 STORE_FAST               2 (c)

  4          12 LOAD_FAST                1 (res)
             14 LOAD_METHOD              0 (append)
             16 LOAD_FAST                2 (c)
             18 CALL_METHOD              1
             20 POP_TOP
             22 JUMP_ABSOLUTE            4 (to 8)

  5     >>   24 LOAD_FAST                0 (value)
             26 LOAD_CONST               1 ('')
             28 LOAD_METHOD              1 (join)
             30 LOAD_FAST                1 (res)
             32 CALL_METHOD              1
             34 COMPARE_OP               2 (==)
             36 RETURN_VALUE

Как видите, isPalindrome2 скомпилировал НАМНОГО меньше байт-кода, чем любой из двух других. Это связано с тем, что большинство его операций встроены в Python и, следовательно, написаны на C, а не на Python. Код C, стоящий за каждой из операций в isPalindrome2, вероятно, делает то же самое, что и код Python в одной из других функций (хотя трудно сказать), но он намного быстрее просто потому, что C — очень быстрый язык, а Python очень медленно.

Байты 4-13 байт-кода isPalindrome2 делают по сути то же самое, что и байты 0-33 байт-кода isPalindrome3, но isPalindrome2 использует множество операторов, которые обрабатываются кодом C, тогда как isPalindrome3 вызывает функцию Python (очень медленно), загружает константа/переменная 3 дополнительных раза и использует цикл Python for. Все эти вещи медленнее, чем их эквиваленты C, то есть медленнее. То же самое и с первой функцией. Поэтому вторая функция, которая имеет гораздо меньше байт-кода и в основном использует код C, намного быстрее.

Другие вопросы по теме