(that time I learnt the lesson: never promise what the next post will be about coz I often not deliver)

Optimization algo need to explore the space of solutions, and this exploration is a major part of the algo! Let’s focus on one simple case: exploring in random order two finite dimensions. For example, let two integer variables, V1 taking value in interval [1, 100] and V2 taking value in interval [1, 20]: how to explore all the possible pairs (v1,v2) in random order?

A simple (almost-)solution is given by the following python code:

[(e1,e2) for e1 in shuffle(range([1,100)), for e2 in shuffle(range(1,20))]

which is in fact the cartesian product of the shuffles of V1 and V2 intervals … but this is ordered by values of the first shuffle and thus not random.

OK, now is the bad news: I have no solution completely space efficient to propose. My best effort is a solution which compute at least two shuffles, one on each dimension (kind of O(n + m) for space) and is even not random … just random enough for most of the cases 😛

So how? the solution is describe in this post http://weblog.raganwald.com/2007/02/haskell-ruby-and-infinity.html and especialy the section about the tabular view of the cartesian product. Did you read it? so the proposed solution is to navigate the cross-product table along its diagonal instead of row by row … simply smart isn’t it? It give “impression” of randomness 😛

Ocaml code for this algo is here: http://github.com/khigia/ocaml-anneal/tree/master/walks.ml (function pair_permutation_random_seq); It uses extensively an ad-hoc stream implementation (Seq module) to perform the walk lazyly. It was a good example to test the stream implementation!

Advertisements

I’ve been using this python implementation of simulated annealing to deduce Singapore bus service from a database of bus stops (see previous posts about Google Map API).

I wanted to play a little bit more with this algo and decided to port it to OCaml: you can find the code on GitHub.

As a first try, I wrote a direct code translation. Only few points differ:

  • The OCaml code use a stream implementation (lazy list) … (mostly equivalent to my previous Erlang implementation).
  • The OCaml code uses array structure where Python uses list.
  • The OCaml implementation of function reversed_section do only one array reverse in all cases.

Result is quite ok. Without any optimization on the algo, the OCaml native code performed quite faster (around 10 times faster), meaning that solving the TSP problem for SG bus services took 40 minutes for OCaml version where the Python code ran for hours (of course we could improve this version too).

The algo itself can be improve (I guestimate the time for SG map problem can be reduce by one more order of magnitude with the same simulated annealing approach).

But in coming post (code is there, need time to clean it), I’ll be looking at other interesting problems I found inside this one, especially on how to walk in solutions space in quasi-random order.

This post is a following to the previous post about drawing SG bus route with google map API.

Status of the system

This is for now only a toy demo, all in a single javascript document that draw the map when loaded (the javascript file is generated from a KML file by a python program that also computes the bus service routes).

Toward drawing all the bus services …

Drawing all the bus services on the same map not only is *very heavy* for the browser (at least for firefox, and its SVG renderer) but also give very little information (it is too much data at one time).

See by yourself:

Even zooming (on Dhoby Ghaut station):

What could be done …

  • To solve the problem of too many services displayed at same time, definitively a good UI could improve usability.
    What I have in mind is a kind of UI which enable to select which services to display … but maybe something better can be done like auto-selection of services to display depending of zoom factor or user itinary?
  • The previous point could also help to not send all the data to the client (in order to save bandwith).
  • Automatic route simplification: on one route, when adjacent stops are “too close” to each other, we could remove one of them on the drawing (which would make it lighter, and also remove some artifact like tiny wigzag caused by stop on the opposite side of the road).
  • Adding some constraints manually (editing few distance between some stops) to correct some wrong path.

More?

As in the previous post conclusions, I think a mashup of existing itinery service to display the itinery on a map could be quite interesting.

Playing with the DB of SG bus stop locations and google map API.

My goal is to try to draw the route of the bus services … but the DB has no info about the order of the stops per service (there is info of which services stop for each bus stop). Following are some experiments, with display about bus service 124.

First try was kind of funny (not unexpected!) as I draw the bus route “as stops are found in DB” … which apparently is from left to right:

So, to get a better idea of the bus route, I’m trying to draw the shortest path … better and even quite enough:

But of course this is inexact map as:

  1. this shortest route uses all bus stops without taking care of which ones are on the way to go or the way to go back (this data is not in my DB);
  2. the length of the path does not depend of the road … those are only straight lines!

But anyway, this give a better view of the bus service than nothing or a guide book of bus stop names …

New example in ocamerl lib of erlocaml project: a tiny map-reduce-like (1) word-count program (word-count is the simple example often used to illustrate map-reduce principle).

First part of this example is an ocaml distributed erlang node [l52]. It is composed of one permanent registered (‘wc’) mbox [l40] which upon request create other mboxes implementing the mappers [l19] (on request, a mapper read a text file [l8] and send it word by word to reducer [l29]).

Second part of this map-reduce example is an erlang module implementing two functionalities. One of them is the reduce part implementation [l34] done by a process which accept messages from mappers and update a dictionary accordingly.
Second responsibility of this module is orchestration of the map-reduce flow [l90], consisting of running all mappers [l66], waiting end of all those executions [l79], and collecting result of all reducers [l95].

Assuming EPMD is running, this script run an ocaml node and an erlang node, and run a simple map-reduce to count words in two test files.

As usual, not sure it’s a useful example, but it was sure fun to write 🙂

(1) this is not a map-reduce lib … there is no failure case taken care of, processes pipe is mostly done through messages over network (while map-reduce is mainly meant to use an efficient filesystem based communication), etc!

Little intro step-by-step to the ocaml-erlang message exchange mechanism offered by ocamerl (a lib of erlocaml).

Subject of the following code is a wonderfull application … named “echo server”!

  1. In the interpretor shell of ocaml, we create a hidden erlang node and an activity to echo all received message (both on console as well as in respond to the caller).
  2. In the erlang interpretor shell, we send few message and compare them to the received ones.

The following assumes code is running on machine “comp1”.

Ocaml shell:

(* getting Ocamerl available in toplevel *)
ocaml> #use "topfind";; (* ocamerl used findlib for install *)
ocaml> #thread;; (* ocamerl is multithreaded app *)
ocaml> #require "ocamerl";;

(* creating/declaring a node, assuming epmd is running *)
ocaml> let o1 = Ocamerl.Enode.run "o1" ~cookie:"cookie";;
val o1 : Ocamerl.Enode.t = <abstr>

(* creating/declaring a mbox, equivalent of erlang process *)
ocaml> let m = Ocamerl.Enode.create_mbox o1;;
val m : Ocamerl.Enode.Mbox.t = <abstr>
ocaml> Ocamerl.Enode.register_mbox o1 m "echoer";; (* give it a name *)
- : unit = ()

ocaml> Ocamerl.Enode.Mbox.create_activity m (fun msg -> match msg with
    | Ocamerl.Eterm.ET_tuple [|pid; any;|] ->
        Printf.eprintf "MSG:%s\n%!" (Ocamerl.Eterm.to_string msg);
        Ocamerl.Enode.send o1 pid any
    | _ ->
        () (* drop unexpected msg *)
);;
- : unit = ()

Erlang shell:

# starting erlang node with same cookie
erl -sname e1 -setcookie cookie

% check connection
erl> pong = net_adm:ping(o1@comp1).
pong

% utility to print whatever is in message queue
erl> F = fun() -> receive W -> io:format("got back: ~w~n", [W]) after 1 -> error end end.
#Fun<erl_eval.20.67289768>

% some tests ... send data, received it back
erl> {echo1, o1@comp1} ! {self(), {1,2,"test"}}.
{<0.37.0>,{1,2,"test"}}
erl> F().
got back: {1,2,[116,101,115,116]}
ok
% in the mean time, ocaml shell also display the data

That’s it! A wonderfull echo server 🙂

Amongst things on the to-do list:

  • Should not have to create a mbox and set its activity separately (need some wrapper)
  • Could have an onode ocaml toplevel which run one node by default and offer direct interface (e.g. “send”).

Yet another useless example for erlocaml, but this time it is not completely silly … it does something 🙂

In fact the project eocarve uses:

Idea is simple: an ocaml node run and provide a API for Erlang node to call the seamcarving library. See eocarve wiki for details/example.

Aim of this project was mainly to demonstrate use of ocamerl lib … however it may be usefull for an Erlang web app which would need seamcarving (heavy weight for CPU!). Had fun to integrate those lib in same app.