Time Comparison between Python isPalindrome-CodePudding

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:

For the first: 2.7046061150031164
For the second: 0.2354857140162494
For the Third: 3.201262982998742

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.

CodePudding user response：

Probably in the second case, the slicing is executed by C code working low level in memory. In the first case, you need to get elements one by one. In the third one you need to iterate over an iterator (created by the for...in syntax) and you need to perform the append that requires computation and checks, all written in python code.

CodePudding user response：

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.