Almost after 4 months of silence its time to get back at taking notes about ArgoUML and my adventures in software development. I'll do a retrospective on what I've been doing another time. Currently I want to document one very interesting thing that is common knowledge, but, that have reveal to me again today. Don't optimize without having measurements before. Or stated in its full glory: Premature optimization is the root of all evil.
I was working in solving one of the Google Code Jam 2006 excercises. –If you are curious I was very unsuccessful in my attempt to solve this in the one hour they give you to solve. – It is the SquareCounting problem and I tried to solve it in Java, in a Test Driven Development way. After my failure to provide anything near a solution to the problem, I kept trying to solve it and I think that now I have a solution and I was making some simple efficiency measures to check what was the performance of my solution according to the Big O notation.
After having this setup and with 10 different measures, I started making a very simple change that I thought would bring immediate improvements. Alas, it made it worst by a factor of 3 for some cases! I'm very happy to have started measuring before any changes. So, now have a personal experience backing the idea that premature optimization is evil.
My solution doesn't use any linear algebra ideas, but, I think it should. The thing is, now I have the possibility to decide on the best based on actual measurements and detailed test cases. This kind of problem solving is proving to be fun.
Oh, forgot to show you the measurements. N is the number of elements in the square. Sol is the number of squares and the time in miliseconds for executing the tests 100.000 times. The results before the change:
N | Sol | Time (ms) |
---|---|---|
4 | 4 | 391 |
9 | 6 | 593 |
6 | 2 | 360 |
9 | 1 | 422 |
100 | 1 | 3843 |
90 | 12 | 5672 |
16 | 16 | 1297 |
25 | 25 | 1766 |
36 | 30 | 3156 |
42 | 35 | 3625 |
And after the "improvements":
N | Sol | Time (ms) |
---|---|---|
4 | 4 | 265 |
9 | 6 | 438 |
6 | 2 | 281 |
9 | 1 | 297 |
100 | 1 | 2656 |
90 | 12 | 7047 |
16 | 16 | 1610 |
25 | 25 | 3859 |
36 | 30 | 6594 |
42 | 35 | 8625 |