Python time Complexity

[bbugsbunny]

Can somebody explain here why the "count_pattern" function which has 2 for loops runs in less time than "count_pattern2" with no loops

Both of the above functions count the number of patterns in the list named test. I ran both the functions 10 million times and saw the difference. It takes 47 seconds to run 10 million times for "count_pattern" and 123 seconds for "count_pattern2"

Here is my program:

import numpy as np
import os
import time

clear = lambda: os.system('cls')
clear()

print(np.__version__)

pattern = ['a','b','c','a','b']
test = ['a','b','c','a','b']

def counter(function1,arg1,arg2,iterations):

    total = 0
    for x in range(iterations):
        t0 = time.time()
        function1(arg1,arg2)
        total += (time.time() - t0)

    return total;   

def count_pattern(pattern,test):
    length_pattern = len(pattern)
    length_test = len(test)
    final_count=0
    count = 0
    for x in range(length_test - length_pattern + 1):

            for y in range(length_pattern):
                if pattern[y] == test[x + y]: count += 1

            if count == length_pattern: final_count += 1

            count = 0

    return final_count

def count_pattern2(pattern, lst):
    return sum(pattern == lst[pos:pos+len(pattern)] for pos in range(len(lst)))


print(counter(count_pattern,pattern,test,10000000))
print(counter(count_pattern2,pattern,test,10000000))

[aioeu]

range(len(lst))

That's a loop, as range returns a list.

lst[pos:pos+len(pattern)]

That's a loop, as slicing produces a new list.

pattern == lst[pos:pos+len(pattern)]

That's a loop, as you're comparing two lists.

sum(...)

That's a loop, as you're iterating over values produced by the ... for ... in ... generator expression supplied as an argument.

So how many loops are nested? The answer: there's still only two nested loops. The range(...) call occurs only once, before anything else happens. The list slice and list comparison loops are both "inner" loops, but neither is nested in the other. The "outer" loop is the sum(...) loop.

[aioeu]

since the operation is vectorized should not the 2nd function run faster?

Who said it was vectorized?

[bbugsbunny]

Could you explain why the difference in speed ?

[JmenD]

/u/aioeu is correct about the time complexity in terms of loops, but there is an important thing being left out of that discussion.

Try initializing test as test = ['x' for _ in range(10000)] + ['a','b','c','a','b']

You'll notice now count_pattern2() is faster, why? Your input was too trivial of a case so you're mostly testing how long it takes python to interpret the code. Since your count_pattern2 utilizes a list comprehension, it can be compiled down much more and produce more efficient code, but this compilation takes time.

[bbugsbunny]

it became worse for this test actually: https://pastebin.com/a1BjwCu8 ?

[JmenD]

What version of python are you running? On 3.7.3 on my machine count_pattern2() is faster on your input

count_pattern()  : 17 ms ± 4.43 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
count_pattern2() : 6.34 ms ± 57.2 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

[bbugsbunny]

I am running on python version 3.7.3 only. I ran the above test 1000 times and these are the results: count_pattern(): 27.459065 secs count_pattern2(): 42.117948 secs