Although Julia has integrated support for various data structures (arrays, tuples, dictionaries, sets), it doesn’t exhaust the full gamut of ptions. More exotic structures (like queues and deques, stacks, counters, heaps, tries and variations on sets and dictionaries) are implemented in the DataStructures package.
As always we start by loading the required package.
julia> using DataStructures
I won’t attempt to illustrate all structures offered by the package (that would make for an absurdly dull post), but focus instead on queues and counters. The remaining types are self-explanatory and well illustrated in the package documentation.
Queue
Let’s start off with a queue. The data type being queued must be specified at instantiation. We’ll make a queue which can hold items of Any type. Can’t get more general than that.
julia> queue = Queue(Any);
The rules of a queue are such that new items are always added to the back. Adding items is done with enqueue!().
julia> enqueue!(queue, "First in.");
julia> for n in [2:4]; enqueue!(queue, n); end
julia> enqueue!(queue, "Last in.")
Queue{Deque{Any}}(Deque [{"First in.",2,3,4,"Last in."}])
julia> length(queue)
5
The queue now holds five items. We can take a look at the items at the front and back of the queue using front() and back(). Note that indexing does not work on a queue (that would violate the principles of queuing!).
Finally we can remove items from the front of the queue using dequeue!(). The queue implements FIFO (which is completely different from the other form of FIFO, which I only discovered today).
julia> dequeue!(queue)
"First in."
Counter
The counter() function returns an Accumulator object, which is used to assemble item counts.
We can return (and remove) the count for a particular item using pop!().
julia> pop!(cnt, "cat")
4
julia> cnt["cat"] # How many cats do we have now? All gone.
0
And simply accessing the count for an item is done using [] indexing notation.
julia> cnt["mouse"] # But we still have a handful of mice.
5
I’ve just finished reading through the second early access version of Learn Julia by Chris von Csefalvay. In the chapter on Strings the author present a nice example in which he counts the times each character speaks in Shakespeare’s Hamlet. I couldn’t help but think that this would’ve been even more elegant using an Accumulator.
Tomorrow we’ll take a look at an extremely useful data structure: a graph. Until then, feel free to check out the full code for today on github.
Sudoku-as-a-Service is a great illustration of Julia’s integer programming facilities. Julia has several packages which implement various flavours of optimisation: JuMP, JuMPeR, Gurobi, CPLEX, DReal, CoinOptServices and OptimPack. We’re not going to look at anything quite as elaborate as Sudoku today, but focus instead on finding the extrema in some simple (or perhaps not so simple) mathematical functions. At this point you might find it interesting to browse through this catalog of test functions for optimisation.
There are a number of algorithms at our disposal. We’ll start with the Nelder Mead method which only uses the objective function itself. I am very happy with the detailed output provided by the optimize() function and clearly it converges on a result which is very close to what we expected.
julia> optimize(himmelblau, [2.5, 2.5], method = :nelder_mead)
Results of Optimization Algorithm
* Algorithm: Nelder-Mead
* Starting Point: [2.5,2.5]
* Minimum: [3.0000037281643586,2.0000105449945313]
* Value of Function at Minimum: 0.000000
* Iterations: 35
* Convergence: true
* |x - x'| < NaN: false
* |f(x) - f(x')| / |f(x)| < 1.0e-08: true
* |g(x)| < NaN: false
* Exceeded Maximum Number of Iterations: false
* Objective Function Calls: 69
* Gradient Call: 0
Next we’ll look at the limited-memory version of the BFGS algorithm. This can be applied either with or without an explicit gradient function. In this case we’ll provide the gradient function defined above. Again we converge on the right result, but this time with far fewer iterations required.
julia> optimize(himmelblau, himmelblau_gradient!, [2.5, 2.5], method = :l_bfgs)
Results of Optimization Algorithm
* Algorithm: L-BFGS
* Starting Point: [2.5,2.5]
* Minimum: [2.999999999999385,2.0000000000001963]
* Value of Function at Minimum: 0.000000
* Iterations: 6
* Convergence: true
* |x - x'| < 1.0e-32: false
* |f(x) - f(x')| / |f(x)| < 1.0e-08: false
* |g(x)| < 1.0e-08: true
* Exceeded Maximum Number of Iterations: false
* Objective Function Calls: 25
* Gradient Call: 25
Finally we’ll try out Newton’s method, where we’ll provide both gradient and Hessian functions. The result is spot on and we’ve shaved off one iteration. Very nice indeed!
julia> optimize(himmelblau, himmelblau_gradient!, himmelblau_hessian!, [2.5, 2.5],
method = :newton)
Results of Optimization Algorithm
* Algorithm: Newton's Method
* Starting Point: [2.5,2.5]
* Minimum: [3.0,2.0]
* Value of Function at Minimum: 0.000000
* Iterations: 5
* Convergence: true
* |x - x'| < 1.0e-32: false
* |f(x) - f(x')| / |f(x)| < 1.0e-08: true
* |g(x)| < 1.0e-08: true
* Exceeded Maximum Number of Iterations: false
* Objective Function Calls: 19
* Gradient Call: 19
NLopt is an optimisation library with interfaces for a variety of programming languages. NLopt offers a variety of optimisation algorithms. We’ll apply both a gradient-based and a derivative-free technique to maximise the function
subject to the constraints
and
.
Before we load the NLopt package, it’s a good idea to restart your Julia session to flush out any remnants of the Optim package.
julia> using NLopt
We’ll need to write the objective function and a generalised constraint function.
julia> count = 0;
julia> function objective(x::Vector, grad::Vector)
if length(grad) > 0
grad[1] = cos(x[1]) * cos(x[2])
grad[2] = - sin(x[1]) * sin(x[2])
end
global count
count::Int += 1
println("Iteration $count: $x")
sin(x[1]) * cos(x[2])
end
objective (generic function with 1 method)
julia> function constraint(x::Vector, grad::Vector, a, b, c)
if length(grad) > 0
grad[1] = a
grad[2] = b
end
a * x[1] + b * x[2] - c
end
constraint (generic function with 1 method)
The COBYLA (Constrained Optimization BY Linear Approximations) algorithm is a local optimiser which doesn’t use the gradient function.
julia> opt = Opt(:LN_COBYLA, 2); # Algorithm and dimension of problem
julia> ndims(opt)
2
julia> algorithm(opt)
:LN_COBYLA
julia> algorithm_name(opt) # Text description of algorithm
"COBYLA (Constrained Optimization BY Linear Approximations) (local, no-derivative)"
We impose generous upper and lower bounds on the solution space and use two inequality constraints. Either min_objective!() or max_objective!() is used to specify the objective function and whether or not it is a minimisation or maximisation problem. Constraints can be either inequalities using inequality_constraint!() or equalities using equality_constraint!().
I’m rather impressed. Both of these packages provide convenient interfaces and I could solve my test problems without too much effort. Have a look at the videos below for more about optimisation in Julia and check out github for the complete code for today’s examples. We’ll kick off next week with a quick look at some alternative data structures.
Yesterday we had a look at Julia’s support for Calculus. The next logical step is to solve some differential equations. We’ll look at two packages today: Sundials and ODE.
Sundials
The Sundials package is based on a library which implements a number of solvers for differential equations. First off you’ll need to install that library. In Ubuntu this is straightforward using the package manager. Alternatively you can download the source distribution.
sudo apt-get install libsundials-serial-dev
Next install the Julia package and load it.
julia> Pkg.add("Sundials")
julia> using Sundials
To demonstrate we’ll look at a standard “textbook” problem: a damped harmonic oscillator (mass on a spring with friction). This is a second order differential equation with general form
where is the displacement of the oscillator, while and characterise the damping coefficient and spring stiffness respectively. To solve this numerically we need to convert it into a system of first order equations:
We’ll write a function for those relationships and assign specific values to and .
julia> function oscillator(t, y, ydot)
ydot[1] = y[2]
ydot[2] = - 3 * y[1] - y[2] / 10
end
oscillator (generic function with 2 methods)
Next the initial conditions and time steps for the solution.
julia> initial = [1.0, 0.0]; # Initial conditions
julia> t = float([0:0.125:30]); # Time steps
The results for the first few time steps look reasonable: the displacement (left column) is decreasing and the velocity (right column) is becoming progressively more negative. To be sure that the solution has the correct form, have a look at the Gadfly plot below. The displacement (black) and velocity (blue) curves are 90° out of phase, as expected, and both gradually decay with time due to damping. Looks about right to me!
ODE
The ODE package provides a selection of solvers, all of which are implemented with a consistent interface (which differs a bit from Sundials).
julia> using ODE
Again we need to define a function to characterise our differential equations. The form of the function is a little different with the ODE package: rather than passing the derivative vector by reference, it’s simply returned as the result. I’ve consider the same problem as above, but to spice things up I added a sinusoidal driving force.
julia> function oscillator(t, y)
[y[2]; - a * y[1] - y[2] / 10 + sin(t)]
end
oscillator (generic function with 2 methods)
We’ll solve this with ode23(), which is a second order adaptive solver with third order error control. Because it’s adaptive we don’t need to explicitly specify all of the time steps, just the minimum and maximum.
julia> a = 1; # Resonant
julia> T, xv = ode23(oscillator, initial, [0.; 40]);
julia> xv = hcat(xv...).'; # Vector{Vector{Float}} -> Matrix{Float}
The results are plotted below. Driving the oscillator at the resonant frequency causes the amplitude of oscillation to grow with time as energy is transferred to the oscillating mass.
If we move the oscillator away from resonance the behavior becomes rather interesting.
julia> a = 3; # Far from resonance
Now, because the oscillation and the driving force aren’t synchronised (and there’s a non-rational relationship between their frequencies) the displacement and velocity appear to change irregularly with time.
How about a double pendulum (a pendulum with a second pendulum suspended from its end)? This seemingly simple system exhibits a rich range of dynamics. It’s behaviour is sensitive to initial conditions, one of the characteristics of chaotic systems.
First we set up the first order equations of motion. The details of this system are explained in the video below.
Below are two plots which show the results. The first is a time series showing the angular displacement of the first (black) and second (blue) mass. Next is a phase space plot which shows a different view of the same variables. It’s clear to see that there is a regular systematic relationship between them.
Next we’ll look at a different set of initial conditions. This time both masses are initially located above the primary vertex of the pendulum. This represents an initial configuration with much more potential energy.
The same pair of plots now illustrate much more interesting behaviour. Note the larger range of angles, θ2, achieved by the second bob. With these initial conditions the pendulum is sufficiently energetic for it to “flip over”. Look at the video below to get an idea of what this looks like with a real pendulum.
It’s been a while since I’ve played with any Physics problems. That was fun. The full code for today is available at github. Come back tomorrow when I’ll take a look at Optimisation in Julia.
.
.
.
is the displacement of the oscillator, while 
and 
characterise the damping coefficient and spring stiffness respectively. To solve this numerically we need to convert it into a system of first order equations:
