Friday 25 October 2013

Problem Set

Well, the problem wasn't particularly difficult so I'm not planning to post code for this one.  I did learn a few things about the differences:

- remember to use return with Python functions, it doesn't just return the last result if you leave it open
- you have to go back to for i in range(1, h+1) from for i=1:h
- remember that everything starts with 0 in Python not 1
- its xxx.method(c) not method(xx, c)

I'm not sure if working on two languages at once is something I'm capable of or not.  For interest I decided to look at memoizing fib.  This is an interesting exercise in scope and closures.  In Python you can do it with something like this:

But in Julia you run into a couple of problems.  First, redefining a function in the Main() scope is not permitted but that can be overcome by putting fib in a module and importing it (within the same REPL seems fine).  Second, the recursive calls to fib are not updating the cache dictionary so it doesn't speed up.  I've asked for help to understand the error in my thinking.

IJulia Notebook.

The other thing I continued experimenting with was Gadfly.  I didn't know a sine wave could look like this:



And I've created a first draft of a Gadfly Reference Card.

2 comments:

  1. Function names are constants in Julia, so you cannot redefine them (but you can add new methods). If you put it in a module, it is still not going to work: the problem is that you cannot change the "fib" function within the function definition after you have written the function.

    You could, of course, use a global variable "fib" which you assign to a function, and hence is changeable. This works:

    fib_(n) = n <= 1 ? one(n) : fib(n-1) + fib(n-2)
    memoize(f) = let cache = Dict()
    x -> haskey(cache, x) ? cache[x] : (cache[x] = f(x))
    end
    fib = memoize(fib_)

    but this is ugly, and using globals is suboptimal in Julia because it defeats type inference.

    It is more efficient to write memo-ization into the fib function when you write it, e.g:

    const fib_cache_=(Int64=>Int64)[]
    fib_cache(n::Int64) = haskey(fib_cache_, n) ? fib_cache_[n] : (fib_cache_[n] = n > 1 ? fib_cache(n-1)+fib_cache(n-2) : one(n))

    This allows us to specifically declare the key and value types of the fib_cache_ dictionary, so that Julia's type-inference works.

    A more elegant solution is to use something like the Memoize package (https://github.com/simonster/Memoize.jl) to rewrite the function definition to cache its values. This allows you to define functions in the natural way:

    using Memoize
    @memoize fib2(n) = n > 1 ? fib2(n-1)+fib2(n-2) : one(n)

    and Julia's macro facility is powerful enough to allow it to rewrite the function definition into something like the above (but with a bit less type specificity).

    ReplyDelete
  2. Thanks Steven,

    I've just finished the manual on Expressions and Macros so I'll look through your code. My best solution in the end was to generate a new environment for the memoization with let - I wanted a function based solution before moving off to macros:

    let julia_environment = "One that will let us redefine anything"
    ###

    function fmemoize(f)
    mem(x::Int64) = haskey(cache, x) ? cache[x] : (cache[x] = f(x))
    cache = Dict()
    return mem
    end


    fib(n::Int64) = n <= 1 ? 1 : fib(n-1) + fib(n-2)
    fib = fmemoize(fib)

    @time output = fib(1500)
    print(output)

    ###
    end

    This is quick and works well. Interestingly @memoize is more than 3 times as fast as my functional solution.

    ReplyDelete