Main Content

How to avoid too many recalculations within an object

Archive - Originally posted on "The Horse's Mouth" - 2014-12-21 16:38:26 - Graham Ellis

Object Orientation is a wonderful way of segmenting your code - hiding algorithms within objects (encapsulating) so that the user of your code need now realise about / understand the algorithms. But this can mean that the user, unknowingly, runs potentially slow and complex code many times over when it's unnecessary to do so.

Let's take an example - I have an object type "game" of which I've created three and I call for the length of each game (let's pretend it's a complex algorithm) many times over - that's quite a realistic proposition if I were to be sorting by game length, or doing something else like that. The program that shows this initial example is at [here] - I've added a global counter to what would be a regular class and property to illustrate the number of getminute calculations made ... and it turn out to be 30.

With only three objects, you may think I could simply calculate the number of minutes at the time the object is constructed - however, there many be applications where huge numbers of gaes are constructed and the length of the game is only required for a very few of them - net result being a lot of calculations made for no purpose at all. This "calculate at construct" approach also has problems if you provide and use a facility to change the input values to your object later on after it's been built - you need to code carefully to recalculate the output values at appropriate times so you always have it available. If I were to modify my control class to calculate on construction, there would be 13 calculations made.

An excellent solution to the "calculate on construct" v "calculate on use" dilemma is to set a flag on construct to say that the calculation has not been made, to calculate on first use, and at that point to store the result for subsequent requests and set the flag to indicate that a stored result is available ... with that stored result returned in preference to a re-calculate. This is termed "caching the results". If there's a facility to change the input values within your object later, all you need do is set the stored ("cached") flag to false, thus forcing a recalculate and re-store if and when the calculation result is subsequently rerequested. This cuts the number of calculations in my example tojust 4.

Sample code - [here]

Code amendments between my examples?

I have added
  this.cached = 0
in the contructor

I have replaced
  results = (this.time + 10) * this.players
  return results
by
  if not this.cached:
    this.results = (this.time + 10) * this.players
    this.cached = 1
  return this.results
in the routine that calculates and returns the results

And I have replaced
  this.time = time
by
  if time != this.time:
    this.cached = 0
    this.time = time
in the routine which sets a new value for one of the inputs

For a class with lots of calculated values for each object, you'll need to decide which to store and which not to store, and whether to have a single "cached" variable that flags them all as stored as a "job lot" or whether to cache / store / flag individually. The decision will be 'data driven' in that it will depend on the relationship between the various values and how close it is.

This example is coded in Python, but the same principle should be applied across the other OO languages we teach - Perl, PHP, Ruby, Java (private courses only) and C++, and it can be applied to C structs and Lua tables too.