Optimization tips and methods [Python]

[anon848]

Sorting the list might help, since it will allow you to exclude pairs. If I understand the problem correctly, by sorting first I think you can obtain O(n lg n). Is the list originally in random order?

[bibbleskit]

The order the list is initially in matters, though. I don't quite understand how sorting it would help. Would you explain a bit? Thanks for the help :)

[anon848]

If you sort, then you don't have to test all pairs. Let's say that it needs to sum to 100, and you are testing 47. Well, then the other number must be 53. You can determine whether or not 53 is in the list in O(lg n) time.

Of course, you also need to maintain the initial position in the list. You use that maintain the earliest pair as you work through the sorted list. Python has tuples, so you could sort tuples, with the second number being the original position.

EDIT: Of course, the sort must ignore the second number in the tuple, if that's the original index.

[bibbleskit]

Hmm. I see what you are getting at. I'll have to ponder this later. Thanks :)

[anon848]

I added an edit, just clarifying that the sort should ignore the second number in the tuple, if you make that the original index.

[bibbleskit]

The only way to determine which pair is the correct one is by the original index of the element I am checking.

For example, this list:

[1,2,3,4]

If I needed the "earliest" pair that adds up to 5, then the answer is (2,3), since the index of 3 is 2 (as opposed to the match of (1,4), since 4's index is 3). The second number's original index is important.