This post is a lot more theoretical than the things we usually talk about in Shedlandia. The reasoning behind this post is that while I’m talking about code here, “thinking like a cheat” can be applied to many different tasks.
I recently read a story in which Charles Dowding talked about planting lettuce plants without hardening them off, because fleece protects them enough not to need it. This is “cheating” by the conventional rules of gardening, but it works, it saves time, and it saves effort. Another example of this sort of thinking is the recipe for a country style loaf. The loaf uses a much longer proving time, but requires no kneeding. This is slower, but doesn’t require the baker to be doing anything while the bread is proving, so it actually saves quite a bit of time and effort. This is again “cheating” by the standard ideas of bread-making that most people have, but it works, it saves time, and the loaf tastes great.
Optimizing computer code for speed can require a certain amount of mental gymnastics, and you need to develop a unique set of mental skills in order to optimize things successfully. This is what I call “thinking like a cheat”. There is a fairly well known story about the mathematician Carl Gauss, which neatly illustrates the type of thinking you need to develop in order to optimize well.
When Gauss was a child, he was instructed by his teacher to add all of the numbers up to 100 and give him the result. The teacher had barely had time to return to his desk before gauss handed him a slate with the correct answer written on it.
Gauss had used a mathematical shortcut to solve the problem in a fraction of the time that it would take to do the sums conventionally. If you imagine the numbers from 1 to 100 on a number line, like this:
You will see that the sum of the outermost digits on the number line equals 101, and if you move inwards from this point, the next two numbers are also equal to 101. This pattern is true for the entire number line, with the center of the line dividing the numbers into 50 pairs. Gauss realized that the sum 101 * 50 was much faster to calculate than 1+2+3+4+5+…..99+100, and that is how he managed to answer the question so quickly.
The Modern Day Gauss
The previous story shows how Gauss optimized his task by finding an alternative solution to the problem that he had been given. Had python been around when Gauss was at school, then the story might have been a little different.
Suppose Gauss’ teacher had asked the class to use Python to solve the same problem.
The majority of the class would come up with a Python function that looked similar to the code shown below:
tally = 0
for n in range(i+1):
tally = tally + n
The shortcut used by Gauss still offers a much more elegant solution to the problem, by exploiting the number line and returning the answer with only 2 lines of code:
If you are wondering why the gauss_addup function calculates the returned value as a float and then converts it to an integer value, you should consider the consequences when i=1. If Python deals with the numbers directly as integers, then (1+1)*(1/2) = 2*0 = 0, which is incorrect.
This function takes about a 10th of the time of the original code, but can still be improved upon. If you remove the conversion between float and integer, then you can accelerate the function even more:
The speed increase from this method is even greater, taking around half the time of the previous version to get the result. That represents another big increase in performance, but is it the best solution to the problem?
The answer to that question is “no”. The original instruction handed to Gauss’ class was to add the numbers from 1 to 100 and return the answer. In computational terms the statement of the problem could be expressed slightly differently as “What is the sum of all integer numbers between 1 and 100”.
The functions you have seen so far do not exclusively solve this problem. The functions do provide the correct answer to the questions, but they are designed in such a way that they also answer a lot of other questions as well.
Adding the extra functionality into the code is a natural thing to do, but the extra code is not required to solve the problem. If you follow the statement of the problem literally, then you only need to return the sum of all integers between 1 and 100.
The sum of the integers is a constant value, so you can dispense with the calculations altogether and return the result directly. A shorter function would be:
The result of the sum has been pre-calculated, so it’s much faster than any other method described here. You aren’t really cheating, but you are taking a shortcut that most people wouldn’t think of. For many applications, this sort of “cheat” can make life much easier, and that’s particularly true if you’re working with an micro-controller board like the Arduino or Feather, where there isn’t a lot of processor or memory space to play around with.
So next time you’re hacking on a project or even baking a loaf, dare to “think like a cheat” and save yourself a bucket load of time.