As an ArgoUML contributor I'm going to blog my activities here, so that they may draw interest by other developers or help other developers when doing tasks similar to what I've done. AND(!) the grand vision that makes an Argonaut what he is, TO THRIVE IN THE BIG DANGEROUS WORLD, TAKING THE Argo TO A GOOD SHORE ;-))

Friday, October 06, 2006

On Algorithms

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:

NSolTime (ms)
44391
96593
62360
91422
10013843
90125672
16161297
25251766
36303156
42353625

And after the "improvements":

NSolTime (ms)
44265
96438
62281
91297
10012656
90127047
16161610
25253859
36306594
42358625

Reader Shared items

Followers