CODEWITHSUNDEEP
pythonpython-2.7
Divyanshu
Divyanshu

Reputation: 363

Python low-level vs high-level performance (running time analysis of palindrome functions)

I am trying to find the most efficient way to check whether the given string is palindrome or not.
Firstly, I tried brute force which has running time of the order O(N). Then I optimized the code a little bit by making only n/2 comparisons instead of n.

Here is the code: 

def palindrome(a):
    length=len(a)
    iterator=0
    while iterator <= length/2:
        if a[iterator]==a[length-iterator-1]:
            iterator+=1
        else:
            return False

    return True

It takes half time when compared to brute force but it is still order O(N).

Meanwhile, I also thought of a solution which uses slice operator.
Here is the code: 

def palindrome_py(a):
    return a==a[::-1]

Then I did running time analysis of both. Here is the result: Running time

Length of string used is 50
Length multiplier indicates length of new string(50*multiplier)
Running time for 100000 iterations  

For palindrome    For palindrome_py   Length Multiplier
0.6559998989       0.5309998989       1
1.2970001698       0.5939998627       2
3.5149998665       0.7820000648       3
13.4249999523       1.5310001373       4
65.5319998264       5.2660000324       5

The code I used can be accessed here: Running Time Table Generator

Now, I want to know why there is difference between running time of slice operator(palindrome_py) and the palindrome function.Why I am getting this type of running time?
Why is the slice operator so efficient as compared to the palindrome function, what is happening behind the scenes?

My observations-: running time is proportional to multiplier ie. running time when multiplier is 2 can be obtained by multiplying running time of case (n-1) ie. 1st in this case by multiplier (n) ie.2

Generalizing, we get Running Time(n)=Running Time(n-1)* Multiplier

Upvotes: 3

Views: 239

Answers (1)

Eli Korvigo
Eli Korvigo

Reputation: 10513

Your slicing-based solution is still O(n), the constant got smaller (that's your multiplier). It's faster, because less stuff is done in Python and more stuff is done in C. The bytecode shows it all. 

In [1]: import dis

In [2]: %paste
def palindrome(a):
    length=len(a)
    iterator=0
    while iterator <= length/2:
        if a[iterator]==a[length-iterator-1]:
            iterator+=1
        else:
            return False

    return True

## -- End pasted text --

In [3]: dis.dis(palindrome)
  2           0 LOAD_GLOBAL              0 (len)
              3 LOAD_FAST                0 (a)
              6 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
              9 STORE_FAST               1 (length)

  3          12 LOAD_CONST               1 (0)
             15 STORE_FAST               2 (iterator)

  4          18 SETUP_LOOP              65 (to 86)
        >>   21 LOAD_FAST                2 (iterator)
             24 LOAD_FAST                1 (length)
             27 LOAD_CONST               2 (2)
             30 BINARY_TRUE_DIVIDE
             31 COMPARE_OP               1 (<=)
             34 POP_JUMP_IF_FALSE       85

  5          37 LOAD_FAST                0 (a)
             40 LOAD_FAST                2 (iterator)
             43 BINARY_SUBSCR
             44 LOAD_FAST                0 (a)
             47 LOAD_FAST                1 (length)
             50 LOAD_FAST                2 (iterator)
             53 BINARY_SUBTRACT
             54 LOAD_CONST               3 (1)
             57 BINARY_SUBTRACT
             58 BINARY_SUBSCR
             59 COMPARE_OP               2 (==)
             62 POP_JUMP_IF_FALSE       78

  6          65 LOAD_FAST                2 (iterator)
             68 LOAD_CONST               3 (1)
             71 INPLACE_ADD
             72 STORE_FAST               2 (iterator)
             75 JUMP_ABSOLUTE           21

  8     >>   78 LOAD_CONST               4 (False)
             81 RETURN_VALUE
             82 JUMP_ABSOLUTE           21
        >>   85 POP_BLOCK

 10     >>   86 LOAD_CONST               5 (True)
             89 RETURN_VALUE

There is a hell lot of Python virtual-machine level instructions, that are basically function calls, which are very expensive in Python.

Now, what's with the second function. 

In [4]: %paste
def palindrome_py(a):
    return a==a[::-1]

## -- End pasted text --

    In [5]: dis.dis(palindrome_py)
      2           0 LOAD_FAST                0 (a)
                  3 LOAD_FAST                0 (a)
                  6 LOAD_CONST               0 (None)
                  9 LOAD_CONST               0 (None)
                 12 LOAD_CONST               2 (-1)
                 15 BUILD_SLICE              3
                 18 BINARY_SUBSCR
                 19 COMPARE_OP               2 (==)
                 22 RETURN_VALUE

No Python iteration (jumpers) involved here and you only get 3 calls (these instructions call methods): BUILD_SLICE, BINARY_SUBSCR, COMPARE_OP, all done in C, because str is a built-in type with all methods written C. To be fair, we've seen the same instructions in the first function (along with a lot more other instructions), but there they are repeated for each character, multiplying the method-call overhead by n. Here you only pay the Python's function call overhead once, the rest is done in C.

The bottomline. You shouldn't do low-level stuff in Python manually, because it will run slower than a high-level counterpart (unless you have an asymptotically faster alternative that literally requires low-level magic). Python, unlike many other languages, most of the time encourages you to use abstractions and rewards you with higher performance.

Upvotes: 4

Related Questions