A brief study in optimization (Part 4)

Alright y'all, welcome back! Last time we said we were going to look at the algorithm we wrote in a different way.

Why did we even do the exercise last week, then? Are you a sadist?

The approach we took with the merge algorithm, is the way we're going to approach the algorithm as a whole. Rather than loop to generate triangle numbers, then loop to generate square numbers, then, finally, loop to find matching pairs, we're going to loop once and generate the triangle and square numbers as we need them.

That sounds complicated. I don't like complicated.

It's really not that bad, but, if you didn't understand part 3, you may want to go back and look at it again. I'm going to proceed on the assumption that the logic made sense to you.

One basic way to optimize something, as we saw last time, is to eliminate unnecessary loops. We can use the approach we looked at last time for merging, to combine the entire thing into one main loop. In fact, the only difference from part 3 to here, is that we'll be generating the next triangle and square number on demand. With all that said, here's the code:

triangle_square_numbers = []
n = 1
m = 1
current_triangle = 1
current_square = 1
while current_triangle < 10000000 and current_square < 10000000:
  if current_triangle == current_square:
    triangle_square_numbers.append(current_triangle)
    n = n + 1
    m = m + 1
    current_triangle = current_triangle + n
    current_square = m * m
  elif current_triangle < current_square:
    n = n + 1
    current_triangle = current_triangle + n
  else: # current_triangle > current_square
    m = m + 1
    current_square = m * m

But did it make a difference?

Well here's the timing of this approach compared to the original naive approach, and the approach from last week:

Naive Algorithm: 0.439 seconds
Improved Merge: 0.003 seconds
Combined Approach: 0.001 seconds

Which we can see is quite an improvement on the original approach.

That's it for this series. If you liked it, let me know. I may consider doing this again.