How to do memoization or memoisation in Julia 1.0

Question

I have been trying to do memorisation in Julia for the Fibonacci function. This is what I came up with.

The original unmodified code (for control purposes)

function fib(x)
    if x < 3
        return 1
    else
        return fib(x-2) + fib(x-1)
    end
end

This is my first attempt

memory=Dict()

function memfib(x)
    global memory
    if haskey(memory,x)
        return memory[x]
    else
        if x < 3
            return memory[x] = 1
        else
            return memory[x] = memfib(x-2) + memfib(x-1)
        end
    end
end

My second attempt

memory=Dict()

function membetafib(x)
    global memory
    return haskey(memory,x) ? memory[x] : x < 3 ? memory[x]=1 : memory[x] = membetafib(x-2) + membetafib(x-1)
end

My third attempt

memory=Dict()

function memgammafib!(memory,x)
    return haskey(memory,x) ? memory[x] : x < 3 ? memory[x]=1 : memory[x] = memgammafib!(memory,x-2) + memgammafib!(memory,x-1)
end

Are there other ways of doing so that I am not aware of?

Answer 1

The simplest way to do it is to use get!

const fibmem = Dict{Int,Int}()
function fib(n)
    get!(fibmem, n) do
        n < 3 ? 1 : fib(n-1) + fib(n-2)
    end
end

Note the const specifier outside fibmem. This avoids the need for global, and will make the code faster as it allows the compiler to use type inference within fib.

Answer 2

Since the arguments to the function are integers, you can use a simple array, which will be faster than a Dict (make sure you use BigInts in the cache for large arguments to avoid overflow):

function fib(n, cache=sizehint!(BigInt[0,1],n))
    n < length(cache) && return cache[n+1]
    f = fib(n-1,cache) + fib(n-2,cache)
    push!(cache,f)
    return f
end