I don’t remind myself starting to code, even a single tiny function, without illustrating it on paper. Do I write code on paper? Yes, I also do that. I adore coding on whiteboards where many people can come together on a coffee break and discuss. Most of the young developers ignore that single rule in software development. To write decent code, you have to spend more time on thinking, criticising, brainstorming – determining what the problem is before getting into the solution. Defining the constraints, getting aware of the exceptions, and so on.
Early Starting or Deep Thinking?
I wish the first idea comes to mind was the perfect one. But usually, it is not even close enough to be a good solution – it is often greedy and very straight-forward. The more you learn about the problem and its characteristics, the better and more efficient solution will pop up. If you start coding in the first hour, you will probably never ever finish the task. I’d like to share a case study from Jon Bentley’s amazing book, Programming Pearls.
The story is about Andrew Appel and his experience on reducing the run time of a system from one year to one day. They had to simulate the motions of N objects in 3D space, given their masses and initial positions and velocities. They basically were interested to predict the positions of planets, stars, galaxies 10 years, 100 years, 1000 years later. In a 2D space the input may look like the image on the left: a large set of vectors.
The regular simulation programs divide time into small steps and computes the progress of each object at each step. Due to the existing of gravitational field and mass attractions, the computational cost were proportional to N2. Appel estimated that 1000 time steps of such a system with N=10000 objects would require more than one year on a VAX-11/780 or a day on a Cray-1. Andrew had to develop a system far more efficient than a one-year-running turtle. After several speedup improvements, he reduced the runtime to less than a day on VAX-11/780 — almost 400 times faster than the initial setup. Continue reading
