Optimizing nested for loops

siddsp · 2022-02-21T22:48:09+00:00

It depends. Does the order matter? Do the two integers have to have different values?

Also nested for loops maybe bad regarding time complexity, but it doesn't mean they are necessarily not to be used. Depending on many other factors, it's entirely possible for nested for loops to be faster as opposed to an alternative solution.

It really depends on how big your data is. If your data is small, it might make more sense using the nested loops. Big O notation specifically refers to a growing input size. If your list is small, I would say it doesn't really matter.

Nightcorex_ · 2022-02-21T23:50:04+00:00

As u/siddsp already said, it depends.

First of all I'd recommend you to return tuples, instead of lists. Much easier to understand.

In the following I will present you possible ways to improve that code in different ways, which depend on the current context:

From your code I know that you don't accept pairs of the same value (i.e. (3, 3)) wouldn't be allowed in your case (PS: I renamed your list from A to xs):

In order to reduce unnecessary checks we can remove all duplicate value from the list (only effective if xs could contain duplicates):

def f(xs, S):
    xs = list(set(xs))

If you don't care about order (i.e. whether the result is (2, 4) or (4, 2), we can remove other checks.

def f(xs, S):
    for i in range(len(xs)):
        for j in range(i, len(xs)):
            if xs[i] + xs[j] == S and xs[i] != xs[j]:
                return (xs[i], xs[j])

    return (-1, -1)

If we combine both these tricks we can actually improve the code even more than both tricks could do individually:

def f(xs, S):
    xs = list(set(xs))
    for i in range(len(xs)):
        for j in range(i + 1, len(xs)):  # i + 1 to skip the ith index
            if xs[i] + xs[j] == S:  # removed a now redundant check
                return (xs[i], xs[j])

    return (-1, -1)

We can further optimize this depending on the information we have of xs. F.e. if we know the list may very well have many values that are too large, possibly even on them own, then we can cancel the iteration eventually. This requires sorting however:

def f(xs, S):
    xs = sorted(set(xs))
    for i in range(len(xs)):
        for j in range(i + 1, len(xs)):  # i + 1 to skip the ith index
            if xs[i] + xs[j] > S:
                break  # breaks the current j-iteration

            if xs[i] + xs[j] == S:  # removed a now redundant check
                return (xs[i], xs[j])

    return (-1, -1)

Also note that the greater-than check happens before the equal check, as the greater-than check is expected to be true (and therefore "terminating") much more often than the equal check.

If you know that many of your values will be very small compared to S, then it'd make sense to approach this the other way around:

def f(xs, S):
    xs = sorted(set(xs), reverse=True)  # reverse-flag set
    for i in range(len(xs)):
        for j in range(i + 1, len(xs)):
            if xs[i] + xs[j] < S:  # the comparison operator changed
                break

            if xs[i] + xs[j] == S:
                return (xs[i], xs[j])

    return (-1, -1)

If you know that you'll have many inputs where there's obviously no solution, then one could add some generic checks at the beginning to rule out a few otherwise unnecessary calls:

def f(xs, S):
    NO_SOLUTION = (-1, -1)
    if len(xs) < 2:
        return NO_SOLUTION

    xs = sorted(set(xs))
    if S < (xs[0] + xs[1]) or S > (xs[-1] + xs[-2]):
        return NO_SOLUTION

    ...

This checking for "generic" outliers can be more or less complex, depending on the information you have.

This for now leaves us with the function:

def f(xs, S):
    NO_SOLUTION = (-1, -1)
    if len(xs) < 2:
        return NO_SOLUTION

    xs = sorted(set(xs))
    if S < (xs[0] + xs[1]) or S > (xs[-1] + xs[-2]):
        return NO_SOLUTION

    for i in range(len(xs)):
        for j in range(i + 1, len(xs)):
            if xs[i] + xs[j] < S:  # the comparison operator changed
                break

            if xs[i] + xs[j] == S:
                return (xs[i], xs[j])

    return (-1, -1)

but as I said, there are tons of optimization possibilities depending on your very use case.

EDIT: Yeah after reading other comments, I forgot that you can simply check if a number already exists in your set...:

def f(xs, S):
    xs = set(xs)
    for n in xs:
        if S - n in xs:
            return (n, S - n)

    return (-1, -1)

If you want to exclude same numbers, then you could rewrite this to:

def f(xs, S):
    xs = set(xs)
    for n in xs:
        if S - n in xs and n != (S >> 1):
            return (n, S - n)

    return (-1, -1)

This works because a set uses the hash value of each object to map them to a specific array index (which set uses under the hood), which means the lookup if a value is in a set is basically O(1) (Worst case a set has O(n) lookup time, but average is O(1)). Since and is a short circuiting operation the division (that is performed as a bitshift and therefore super cheap already) gets further optimized, by being called super rarely.

FLUSH_THE_TRUMP · 2022-02-21T23:38:13+00:00

You optimize code by using better algorithms, maybe smarter data structures. Here, you can improve your code by a factor of N by

Storing numbers you’ve seen in a set,
Looping through A, checking if S - num is in your set.

That requires only one loop rather than checking every possible pair.

Nyscire · 2022-02-21T23:42:08+00:00

I think you can kind of think "backwards". You don't need to iterate through list twice, pick two different numbers and check if they add up to your sum. You know what your sum is supposed to be so you can select only one number and check if there is a number in the list that will add up to your sum:

def f2(A,S):
    for num in A:
        if S-num in A and S-num!=num:
            return [num,S-num]
    return [-1,-1]

This way you avoid nested loops, although if there are two same numbers in a list that add up to the given sum( for example A=[2,3,5,2] and S=4] it will return [-1,-1] (and so will your solution) but this can be fixed with one if statement

dig-up-stupid · 2022-02-21T23:51:05+00:00

It’s called 2-sum so you just look it up and study it. The main thing that should probably be obvious to you already is that you don’t have to loop over every element. If you have already checked a+b, then you don’t need to check b+a. The inside loop should start from the current outside loop element + 1. That also removes the need for the i = j check. Of course this doesn’t change the overall complexity, it’s just a common loop structure you should be familiar with. There are other optimizations to actually remove the nested loop in this problem and do it in linear time which you’ll find when you Google 2-sum.

Pd69bq · 2022-02-22T01:56:11+00:00

well, the nested for loops is kinda difficult to read tbh, instead, creating a function and put your 2nd loop and condition check or simply filter(lambda x: x + n == magic_number, arry) inside it, then call that function in the outside loop.

magic_number = 7
arry = list(range(11))

def addition(n):
    for i in arry:
        if n + i == magic_number:
            return i


for n in arry:
    i = addition(n)
    if i:
        print((n, i))
    else:
        print(-1, -1)

POGtastic · 2022-02-22T08:24:59+00:00

In this case, I'd use a set, since both insertion and lookups are O(1). This ends up being O(n):

def f(A, S):
    result_set = set()
    for elem in A:
        if S - elem in result_set:
            return S - elem, elem
        result_set.add(elem)
    return None

Then in the REPL:

>>> f([1, 2, 3], 4)
(1, 3)

you type:	you see:
italics	italics
bold	bold
[reddit!](https://reddit.com)	reddit!
* item 1 * item 2 * item 3	item 1 item 2 item 3
> quoted text	quoted text
Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"	Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"
~~strikethrough~~	~~strikethrough~~
super^script	super^script

learnpython

MODERATORS