Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

localize memoization inside a function in Julia

Is there a way I can localize memoization (via Memoize.jl) inside a function? or at least delete the dictionaries created by memoization?

Clarification: suppose I define a define a function f(x, y). I want to start with a fresh table for every new value of y. That is, given y = y0, f( . , y0) iterates on itself for x, x-1, etc but given a new y = y1, I don't need to store the old table for y0, so that memory can be freed up. How can I do that?

Solution:

cachedfib() = begin
    global dict = Dict()
    global dict2 = Dict()
    function _fib(n::Int, a::Int)
        if !haskey(dict2, a)
            dict2[a] = true
            dict = Dict()
        end
        if haskey(dict, (n, a))
            return dict[(n, a)]
        elseif n < 2
            dict[(0, a)] = 0
            dict[(1, a)] = 1
            return dict[(n, a)]
        else
            dict[(n, a)] = a*(_fib(n - 1, a) + _fib(n - 2, a))
            return dict[(n, a)]
        end
    end
end
fib = cachedfib()

fib(10, 1)
fib(10, 2)

now call dict and dict2 and check that the dictionaries are refreshed every time the second argument changes. You can get even better performance when the parameters to store are integers and you use Array instead of Dict

like image 866
amrods Avatar asked Nov 18 '15 07:11

amrods


2 Answers

To use memoization technique you can do it with let or closures. Have a look at my rapid implementation of factorial (with closure).

with_cached_factorial() = begin
    local _cache = [1] #cache factorial(0)=1    
    function _factorial(n)          
        if n < length(_cache) 
            println("pull out from the cache factorial($n)=$(_cache[n+1])")
            _cache[n+1]
        else
            fres =  n * _factorial(n-1)
            push!(_cache, fres)
            println("put factorial($n)=$fres into the cache of the size=$(sizeof(_cache))") #a
            fres            
        end
    end 
end

Now, just use it:

julia> myf = with_cached_factorial()
_factorial (generic function with 1 method)

julia> myf(3)
pull out from the cache factorial(0)=1
put factorial(1)=1 into the cache of the size=16
put factorial(2)=2 into the cache of the size=24
put factorial(3)=6 into the cache of the size=32
6

julia> myf(5)
pull out from the cache factorial(3)=6
put factorial(4)=24 into the cache of the size=40
put factorial(5)=120 into the cache of the size=48
120

julia> myf(10)
pull out from the cache factorial(5)=120
put factorial(6)=720 into the cache of the size=56
put factorial(7)=5040 into the cache of the size=64
put factorial(8)=40320 into the cache of the size=72
put factorial(9)=362880 into the cache of the size=80
put factorial(10)=3628800 into the cache of the size=88
3628800
like image 147
Maciek Leks Avatar answered Nov 15 '22 09:11

Maciek Leks


let Aold = nothing
global foo
function foo(A::AbstractArray)
    if A == Aold
        println("Same as last array")
    else
        Aold = A
    end
    nothing
end
end

Results:

julia> A = rand(2,2)
2x2 Array{Float64,2}:
 0.272936  0.153311
 0.299549  0.703668

julia> B = rand(2,2)
2x2 Array{Float64,2}:
 0.6762    0.377428
 0.493344  0.240194

julia> foo(A)

julia> foo(A)
Same as last array

julia> foo(B)

julia> foo(A)

julia> foo(A)
Same as last array

julia> Aold
ERROR: UndefVarError: Aold not defined
like image 42
tholy Avatar answered Nov 15 '22 07:11

tholy