I wrote same time complexity 3 isPalindrome function in python. but surprisingly their performance is way different.
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)
Then I test it with timeit module
import timeit
timeit.timeit(lambda: isPalindrome('abcdefghijklmnopqrstuvzzavutsrqponmlkjihgfedcba'), number=1000000)
timeit.timeit(lambda: isPalindrome2('abcdefghijklmnopqrstuvzzavutsrqponmlkjihgfedcba'), number=1000000)
timeit.timeit(lambda: isPalindrome3('abcdefghijklmnopqrstuvzzavutsrqponmlkjihgfedcba'), number=1000000)
Output:
I tried to find why method 2 takes so less time but couldn't find any explanation. Please help me understand why, it will be really helpful.
To find out why a certain function is faster / slower in Python, always use dis.dis. The dis function from the standard dis module can disassemble the bytecode that a function has compiled into, so you can see what really happens when you run it.
Here is the disassembly of the three functions:
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
As you can see, isPalindrome2 has compiled to A LOT less bytecode than either of the other two. This is because most of its operations are builtin in Python, and therefore written in C, not in Python. The C code behind each of the operations in isPalindrome2 probably does a similar thing to the Python code in one of the other functions (although it is hard to tell), but it is much faster simply because C is a very fast language, and Python is very slow.
Bytes 4-13 of the isPalindrome2 bytecode do essentially the same thing as bytes 0-33 of the isPalindrome3 bytecode, but isPalindrome2 uses lots of operators that are handled by C code, whereas isPalindrome3 calls a Python function (very slow to do), loads a constant / variable 3 extra times, and uses a Python for loop. These things are all slower than their C equivalents, meaning it is slower. The same goes for the first function. Therefore, the second function, which has much less bytecode and mainly uses C code, is much faster.