My Nested For loops Run "faster" than inline For loop

user_16930381 0
Viewed 118

For a class I'm in we are asked to write out a brute force method for finding 2 elements in lists S1, S2, that add to a specified value x. So far I have it written out as such:

@timing
def brute_force_nested(x, s1 : list, s2 : list) -> bool:
    for a in s2:
        for b in s1:
            if a + b == x:
                return True
    return False

@timing
def brute_force_inline(x, s1 : list, s2 : list) -> bool:
    return bool([ (a,b) for a in s2 for b in s1 if a + b == x ])

But when I run them in the terminal, I get a very large difference in times:

>>> brute_force_nested(5123, S1, S2):

func:brute_force_nested took: 0.007085800170898438 sec and gave: True

>>>func:brute_force_inline(5123, S1, S2)

func:brute_force took: 3.0208868980407715 sec and gave: True

Why is this happening? I was under the impression that the inline syntax was essentialy just syntactical sugar for written out nested loops, but something is obviously different, and I don't know what.

time python loops
2 Answers

The loops are indeed equal, but not the condition to break it. In the first nested loop, the code stops when the first equality is reached. In the second one, all tests are computed until all combinations are exhausted.

The equivalent of the first loop with the comprehension syntax would be to use a generator and any, that will stop when the first truthy value is reached

return any((a+b==x for a in s2 for b in s1))
user_163434640

This is because you are only iterating over the lists in the first fuinction and returning on the first value. The second you are creating a list then evaluating the Truthy value of that list. For them to be comparable you need to use any and a generator comprehension.

def brute_force_inline(x, s1 : list, s2 : list) -> bool:
    return any(a + b == x for a in s2 for b in s1)

P.S Technically both of your approaches are nested loops one is just done using a comprehension.

This can also be done more efficiently using itertools.product:

from itertools import product

def brute_force_inline(x, s1 : list, s2 : list) -> bool:
    return any(sum(ab) == x for ab in product(s2, s1))
user_2250200
Related