3.8.1: Memoization of Object Methods

Our final example from chapter three is the memoization of object methods. Again we can use the same memoizer function of type Memfunc as before, no changes are needed.

type (
 Keyfunc  func(...interface{}) string
 Memfunc  func(...interface{}) interface{}
 Algofunc func(int) int
)

func memoize(f Memfunc, kf Keyfunc) Memfunc {
 if kf == nil {
  kf = func(v ...interface{}) string {
   // Very naive keygen func, simply use string representation
   // of every param
   var buffer bytes.Buffer
   for i := 0; i < len(v); i++ {
    buffer.WriteString(fmt.Sprint(v[0]))
    buffer.WriteString(",")
   }
   return buffer.String()
  }
 }

 cache := make(map[string]interface{})
 return func(v ...interface{}) interface{} {
  cachekey := kf(v)
  if r, ok := cache[cachekey]; ok {
   // Hit, return previous result
   return r
  }
  // Miss, call calculator
  r := f(v...)
  cache[cachekey] = r
  return r
 }
}

Our object is a trivial one, its only purpose to demonstrate the speedup from the memoizing transformation. The method accepts an int argument, waits for one second and then returns the argument.

type Object struct {
}

func (o *Object) Say(p int) int {
 time.Sleep(1 * time.Second)
 return p
}

The main function starts by executing the raw method and timing it:

func main() {
 var obj Object
 duration, res := timeThis(obj.Say, 1)
 fmt.Printf("Object says: %d, takes %s to do it.\n", res, duration)

Our typecasting code structure is simpler this time around because the method is not a recursive one, only typecasting is needed.

 msay := func(f Algofunc) Algofunc {
  memsay := memoize(func(values ...interface{}) interface{} {
   return f(toInt(values[0]))
  }, nil)

  // Return a function that will do the neccessary typecasting
  return func(val int) int {
   return toInt(memsay(val))
  }
 }(obj.Say)

 duration, res = timeThis(msay, 1)
 fmt.Printf("Memoized object says: %d, takes %s to do it.\n", res, duration)
 duration, res = timeThis(msay, 1)
 fmt.Printf("Memoized object says: %d, takes %s to do it.\n", res, duration)
 duration, res = timeThis(msay, 2)
 fmt.Printf("Memoized object says: %d, takes %s to do it.\n", res, duration)
 duration, res = timeThis(msay, 2)
 fmt.Printf("Memoized object says: %d, takes %s to do it.\n", res, duration)
}

The results are predictable, the method takes one second to execute while the memoized version drops down to 15ms after the first execution:

Object says: 1, takes 1.001060856s to do it.
Memoized object says: 1, takes 1.001117812s to do it.
Memoized object says: 1, takes 14.71us to do it.
Memoized object says: 2, takes 1.001044387s to do it.
Memoized object says: 2, takes 14.893us to do it.

Get the source at GitHub.