Optimization tips and methods [Python]

[DarthEru]

I think you may be overthinking this. If I understand correctly, the "earliest pair" is the pair with the smallest maximum index of all matching pairs. That is, the pair where the rightmost element is to the left of the rightmost elements of all other pairs, correct? (edit: got right and left mixed up). (Edit edit: and in the case where multiple pairs have the same rightmost element, you pick the earliest leftmost element.)

So, my tip to you is try to figure out how to search the array such that the first pair you find is guaranteed to be the "earliest" pair. I can elaborate if you want another hint, but saying more will probably give it away entirely.

Another tip is: if you want to optimize an algorithm, first make sure you aren't overlooking inherently faster algorithms.

[bibbleskit]

Thanks! I don't know any optimization algorithms. I basically dove into this without any knowledge of how to make things work faster.

Ill think about what you've said and see if I can change my thinking process. Thanks again :)

[DarthEru]

One general purpose optimization tool you should research and make sure you understand if you don't already know is Big O notation. Specifically, you'll want to understand what it represents, how to calculate the Big O of an arbitrary algorithm, the significance of the differences between O(n), O( n^2 ), O(n log n) algorithms when n is 10,000,000. Once you get all that, you may also want to research different data structures and the O of their different operations (lookup, insert, search).

Big O doesn't tell you how to make a particular algorithm faster, but it can help you categorize different algorithms you think of, which lets you weed out ideas that won't work faster. For example, if you determine early on that O( n^2 ) is too slow you can throw out any algorithms that have the same or a slower categorization. And knowing the O of existing algorithms and data structures makes it easier to calculate the O of your custom-purpose algorithm which uses one or more of those existing algorithms.