gomemoization

Add a cache to a go function as if it were a static member


Say I have an expensive function

func veryExpensiveFunction(int) int

and this function gets called a lot for the same number.

Is there a good way to allow this function to store previous results to use if the function gets called again that is perhaps even reusable for veryExpensiveFunction2?

Obviously, it would be possible to add an argument

func veryExpensiveFunctionCached(p int, cache map[int]int) int {
    if val, ok := cache[p]; ok {
        return val
    }
    result := veryExpensiveFunction(p)
    cache[p] = result
    return result
}

But now I have to create the cache somewhere, where I don't care about it. I would rather have it as a "static function member" if this were possible.

What is a good way to simulate a static member cache in go?


Solution

  • You can use closures; and let the closure manage the cache.

    func InitExpensiveFuncWithCache() func(p int) int {
        var cache = make(map[int]int)
        return func(p int) int {
            if ret, ok := cache[p]; ok {
                fmt.Println("from cache")
                return ret
            }
            // expensive computation
            time.Sleep(1 * time.Second)
            r := p * 2
            cache[p] = r
            return r
        }
    }
    
    func main() {
        ExpensiveFuncWithCache := InitExpensiveFuncWithCache()
        
        fmt.Println(ExpensiveFuncWithCache(2))
        fmt.Println(ExpensiveFuncWithCache(2))
    }
    
    output:
    4
    from cache
    4
    
    veryExpensiveFunctionCached := InitExpensiveFuncWithCache()
    

    and use the wrapped function with your code. You can try it here.

    If you want it to be reusable, change the signature to InitExpensiveFuncWithCache(func(int) int) so it accept a function as a parameter. Wrap it in the closure, replacing the expensive computation part with it.