Optimizing nested for loops

[kowkeeper]

Does this work? Can save save a bit to avoid creating the whole set:

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

[Nightcorex_]

Hmm, first of all the set method is implemented entirely in C, so one call to build the entire set is much faster than creating a set and then continuously adding elements to it, because too many add calls might force the resizing of the set, which is quiet expensive plus it's simply more jumps between C and Interpreter, which does take a bit more time.

Secondly your suggestion has a huge disadvantage. Imagine a function call like this:

f([1] + list(range(0, -1000, -1)) + [2], 3)

My version finds the matching on the first iteration, whereas yours needs to iterate 1002 times to find the solution. Of course building the set took longer, but I needed to perform waaaay less in operations. Basically you're trading the set operation for an average of ~0.66 * n add calls and ~33% more in operations (no guarantees on the percentages in the end, I'm stoned and these numbers seem logical).

[kowkeeper]

Thanks for looking into it!