10

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?

3
  • 4
    Have you tried the Memoize.jl package?
    – rickhg12hs
    Aug 28, 2018 at 6:06
  • You could use something like get!(memory, x) do; x < 3 ? 1 memfib(x-1) + memfib(x-2) end. But other than that: this question is better suited for Code Review, since you are asking about improvements for working code. Aug 28, 2018 at 7:29
  • 1
    I think the question fits great here. Supplying a worked example just makes it easier to answer. Oct 2, 2018 at 8:05

3 Answers 3

18

As pointed out in the comments, the Memoize.jl package is certainly the easiest option. This requires you to mark the method at definition time.

By far the most powerful approach, however, is to use Cassette.jl, which lets you add memoization to pre-existing functions, e.g.

fib(x) = x < 3 ? 1 : fib(x-2) + fib(x-1)

using Cassette
Cassette.@context MemoizeCtx
function Cassette.overdub(ctx::MemoizeCtx, ::typeof(fib), x)
       get(ctx.metadata, x) do
           result = recurse(ctx, fib, x)
           ctx.metadata[x] = result
           return result
       end
   end

A little bit of a description of what is going on:

  • MemoizeCtx is the Cassette "context" which we are defining
  • overdub is run instead of the original function definition
    • We use this to check if the arg exists in the metadata dictionary.
    • recurse(...) tells Cassette to call the function, but ignore the top level overload.

Now we can run the function with memoization:

Cassette.overdub(MemoizeCtx(metadata=Dict{Int,Int}()), fib, 80)

Now what's even cooler is that we can take an existing function which calls fib, and memoize the call to fib inside that function:

function foo()
    println("calling fib")
    @show fib(80)
    println("done.")
end
Cassette.overdub(MemoizeCtx(metadata=Dict{Int,Int}()), foo)

(Cassette is still pretty hard on the compiler, so this may take a while to run the first time, but will be fast after that).

11

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.

4
1

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.