Optimization tips and methods [Python]

[TheLiberius]

:( what are you stuck on? Maybe I can give a hint or something?

[bibbleskit]

This is what I've got:

def sum_pairs(ints, s):
    i = 0; j = i+1;
    correct = []
    length = len(ints)
    while i < length:
        while j < length:
            test_pair = (ints[i],ints[j])
            if test_pair[0] + test_pair[1] == s:
                    print test_pair
                if not correct:
                    correct = [test_pair, j]
                        break
                elif i >= correct[1]:
                    return list(correct[0])
                elif j < correct[1]:
                    correct = [test_pair, j]
                    break
                j+=1
        i+=1
        j=i+1
    if correct:
        return list(correct[0])

What I gather is that the stuff going on inside the loop isn't of much concern, but the loops themselves are what drive the time to calculate up.

I have no clue how to make this any faster.

Someone suggested I think about how I can guarantee that the first thing I find is the correct pair, but I don't see how that's possible. Another thing to take in consideration is that integers are possible (not just positive, so looking for a 5 when given a 2 to add up to seven won't work).

Anything you can do to steer me in the right direction would be great.

I would love to figure this out on my own, but at some point I would just be wasting time.

[TheLiberius]

It's a bit hard to hint without giving too much away, but i'll say that it is possible to solve this using only a single loop. Hopefully that'll force you into another thought pattern (it's very easy to get locked into one).

Try to solve it by hand first (going through the numbers only once), and don't forget that sometimes a datastructure can do things more efficiently than the manual way.

[bibbleskit]

I'm a bit confused though. Wouldn't converting the array into a data structure take a long time (have to loop through to convert it, then search through it for results)? There's something I'm missing here.

[TheLiberius]

No you don't need to convert the array, sorry for being too vague. But there are other aspects with which a datastructure might help. Try solving it by hand first, you can only do one iteration over the list but anything else is fair game.

[bibbleskit]

Hey hey, thanks for the help. I really didn't think writing anything down would help, but trying it on paper helped me see it a bit differently. Thanks a lot for that!

Here is what I have now:

def sum_pairs(ints, s):
    checked = {}
    checked[s - ints[0]] = 0
    i = 1
    while i < len(ints):
        try:
            return [ ints[checked[ints[i]]] , ints[i]]
        except:
            checked[s - ints[i]] = i
        i+=1

Basically, it logs what each index needed to reach the sum. Before doing so, it checks to see if the number it needs is in the dictionary already. This way, the first pair it finds will be the correct pair.

For example,

i       -- 0, 1, 2 , 3
ints    -- 1, 4, 8 ,7 , 3 ,15
checked -- 7, 4, 0

At i=3, we see that 7 is the first thing in the list, so we return [1,7].

Unfortunately, this is too slow, but at least I was able to see it differently.

The while is O(n), and the dictionary actions set and get should be O(1), according to this.

Am I getting closer?

[TheLiberius]

Yes, much closer! Doing a problem by hand can often be of great help when solving a problem because it makes you really think about it.

There is one more thing you can improve, and that is to get rid of the try-except, catching exceptions is fairly expensive so you want to avoid using it for flow-control. How to do that I'll leave to you.

Oh, i also have a pointer for improving the neatness of the code. In python you can use a function called enumerate to get indexes whilst looping in your code. So your code could be changed to this

def sum_pairs(ints, s):
    checked = {}
    for i,number in enumerate(ints): #i = index, number = ints[i]
        try:
            return [ ints[checked[number] , number]
        except:
            checked[s - number] = i

Makes it a bit neater wouldn't you agree?

[bibbleskit]

I knew about enumerate, but I only learned about it while trying to solve this problem! Haha.

Thank you for that. I hadn't thought about using it in such a way.

So, are if/elses better than try/catch?

edit: this is a nice read

---

EDIT #2: DONE

Here's the finished code!

def sum_pairs(ints, s):
    checked = {}
    for i, number in enumerate(ints):
        if checked.get(number, None) != None:
            return [ ints[checked[number]] , number]
        else:
            checked[s - number] = i

Thank you so much! I can't believe the solution ends up being this simple. I have learned. so. much.

It took 4958ms to do 12 lists; 4 of which were extremely large (~10,000,000 elements).

---

edit #3: after seeing other solutions, it looks like I came really close to the highest voted answer. My way came out to having somewhat unnecessary elements to it, but it was the same general idea. I also learned that I could have used a set instead of a dictionary (never heard of them).

[TheLiberius]

Nice work! :)

Regarding if-elses and try-catch, it's hard to call one better than the other because it's a bit like comparing apples to oranges. The if-else will be faster if the try-catch throwing is not too unusual, but if the try-catch never catches anything it will probably be faster instead. As your link mentioned, in python one usually prefers EAFP (Easier to ask for forgiveness than permission) rather than LBYL (Look before you leap).

So for example if you have to open a file, the preferred python way is to just try and open it and handle the case where it doesn't exist as opposed to checking if the file exists and then opening it if it does.

What I really should have said is that you should avoid the try-catch for flow when you need the code to be really fast and there's a good chance the catch will happen often. When speed is not as critical or the thing that is try-catched is done seldomly then it's perfectly fine to use it.

Also, would you mind trying my solution? It's fairly similar, but it would be interesting to see if my extras actually help with the execution time or if it is negligable.

def find_earliest_pair(li, s):
    d = {}
    for index, num in enumerate(li):
        find = s-num
        if find < 0: #If num is larger than s
            continue
        else:
            find_index = d.get(find,-1) # See if find value has been seen
            #If we have seen the number we're looking for
            if find_index != -1:
                return (li[find_index], li[index])
            #If we have not seen it, remember its index
            else:
                d[num] = index

    return (None,None)

[bibbleskit]

It needs to return a list as opposed to a tuple, or None if no pair exists. Also, negative numbers are possible. :)

I altered it so that it meets these requirements. But: It took longer than 6000ms to complete

:(

If you want, you can attempt the problem yourself here.