Wednesday, June 1, 2016

Better algorithms (3)



This is the third article of this series {first: Better algorithms, second: Better algorithms (2)}. In the first two I stressed the importance of always try new approaches and the importance of knowing Ruby Core very well.

Today I'm going to talk about another important point to optimize your code: learning about the problem!

The first approach we use to solve a problem is seldom the best one. Common sense is not a good programmer, I tell you.

To give you a good example of what I mean, I'm going to use a simple mathematical problem: Write a method to tell if a number is prime or composite.

We learned at school that a prime number is the one only divided by 1 and by itself. This way, 5 is prime, because neither 2, 3 or 4 may divide 5 with a reminder of 0. But 6 is not prime, is composite, because 2 and 3 divide 6 with a reminder of 0. I keep telling "with a reminder of 0" because we are talking about integer division.

The first approach is almost obvious when you read this description. Given an integer n, we only need to test all numbers between 2 and (n-1). If even a single one of them divides n, then n is composite. It is prime otherwise. Like this:


But if we spend sometime reading a book on Elementary Number Theory like this, we'll find out a theorem stating that the smallest prime divisor of n is not greater than the square root of n. In other words, if p is the smallest prime divisor of n, then p <= Math.sqrt(n). Since we don't need to find all divisors, but only find out if there is one and the smallest is as good as any other, based on this theorem we could make our solution much better by adding a single line:



Why this solution is much better? The answer is time!

Let's do a simple benchmark comparing the to solutions and we'll see.

The first method running on a range from 1000 to 2000

The second method, running on the same range in the same computer

As you may see, we had a dramatic reduction in time. And this would be even easier to see with greater numbers.

So, every problem is worth a small research. You may improve a lot the performance of your programs by doing so.