Better algorithm found


An animation of the quicksort algorithm sortin...
Image via Wikipedia

Late last night, in a state of some despair, I pleaded for computing power help with my MSc project. Today, having thought about it long and hard I found a better algorithm and speeded the whole thing up by a factor of 50.

Like, I am sure, many people previously in my position, my inspiration was the classic Programming Pearls.

This is a Birkbeck set text but it’s also one that I did not read when I should have last year – or rather I just read a small part of it. Luckily I am systematically going through it now and was yesterday reading about how much of a difference a better algorithm can make – not that I did not know this, but it helped provide the determination to find one.

So what did I do. Firstly I realised that there was a specialist implementation of the Java Map interface that, as the Javadoc file explicitly says, is good for LRU caches (essentially what I am seeking to model): LinkedHashMap.

This sets up a last-accessed order and so means that it is no longer necessary to search through the whole Map to find the out-of-date pages. Using an Iterator and an EntrySet I only need to get to the first page that is not out-of-date and stop.

When I was checking that worked I noticed that temporal locality meant that in many cases the LRU page was still inside the time frame I was seeking to check – in other words literally billions of checks for outdated pages were taking place needlessly. As pages in the cache cannot get “older” (ie there reference time cannot go backwards), at time \tau + \delta the oldest page cannot be any older than it was at \tau – hence if we do not check until we have reached the point here we need to expire pages with time \tau we will not miss any needed evictions.

The result of these two changes is a massive speed up in the code – by a factor of 40 – 50.

Groovydoc issue


LED elevator floor indicator
Image via Wikipedia

I have been working on a coding exercise using the Groovy programming language and struggled for a bit with an issue with Groovydoc, the documentation protocol the language uses (which is meant to be very similar to Javadoc).

Groovydoc documentation is very thin on the ground and it seems to me that the tool is not exactly complete either, so actually working out why things are failing can be a bit of trial and error.

Anyway, I had my code all in the package “elevators” but when I ran this:

groovydoc -d groovydoc -private *.groovy

Inside the source directory it produced garbage files (did not recognise the packages properly, trying to put everything in the DefaultPackage but also generating broken files for elevators package also).

Going one directory level higher and trying this:

groovydoc -d groovydoc -private -sourcepath . elevators

Produced the same result. But this (two directory levels out) seems to work:

groovydoc -d src/groovydoc -private -sourcepath src elevators