Den enkleste implementasjonen av dynamisk programmering er kanskje memoisering. Om du klarer å lage en rekursiv løsning for problemet ditt, vil memoisering ofte gi deg en effektiv algoritme. Det kan enten være en fullgod løsning i seg selv, eller første skritt i retning av en bottom-up-løsning. Men hvordan kan man implementere memoisering i Julia?

Som så ofte ellers, kan man finne lure tips på Stack Overflow, for eksempel et par svar av Simon Byrne: Ett enkelt svar som bruker get!, og ett som går litt mer i dybden. Dette grundigere svaret viser også hvordan man kan legge til memoisering i en eksisterende funksjon, noe som gjerne er mer enn hva vi trenger. Her er en kort oppsummering av to enkle fremgangsmåter.

Metode 1: Bruk Memoize.jl

Pakken Memoize.jl tar seg av memoiseringen automatisk, så du bare trenger skrive

@memoize function f(x)
    ...
end

for å få en memoisert utgave av funksjonen f.

Metode 2: Bruk get!

Om du vil ha litt mer kontroll med hva som foregår, kan du bruke get! sammen med en global Dict (som absolutt bør deklareres som const av ytelseshensyn; globale variable i Julia har notorisk dårlig ytelse). For å ta Byrne’s eksempel:

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

Funksjonen get! leter etter fibmem[n], for å returnere denne verdien, men om den ikke finnes, så utføres koden inne i do-blokka, og den resulterende verdien settes inn i fibmem[n] for så å returneres. Funksjonen som kalles her er get!(f, d, n), der ´f´ er en funksjon. Denne funksjonen defineres ved hjelp av do-syntaksen.