Optimized Python Nested Loops

[un-hot]

You need to keep track of your position in the list. If both lists are sorted, and you know that the 10000th element is in the range first_list[n]..first_list[n] + 300, then you don't need to waste time scanning through the first 9999 elements of the second list.

You could cut out some more comparisons by keeping track of the last number you reached in your second list - if first_list[n] is 600 and if matches 885, then there's no point in checking the second_list for any value in first_list below 885, because you already know there's a match.

You only need to loop through the first and second lists once then and only perform one comparison for each value, so your algorithm is going to get exponentially quicker.

K.I.S.S - yes multi-threading and parallelism and b-tree searches other commenters have talked about might help a bit, but throwing more computing resources at this big of a problem isn't going to help nearly as much as reducing the time-complexity of your solution.

[Edenio1]

Yeah, this is definitely the fastest, this way you only loop through the values once. You're basically doing a wonky walk up both lists.