Сравнение времени между 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 занимает так меньше времени, но не смог найти никакого объяснения. Пожалуйста, помогите мне понять, почему, это будет очень полезно.
Временная сложность не говорит вам, насколько быстр алгоритм, она говорит вам только о том, как изменяется время выполнения в зависимости от размера данных.
Ответы 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, намного быстрее.
Второй метод быстрее, потому что большая часть логики выполняется в скомпилированном коде нижнего уровня (C).