leafcloud.com

Let’s begin with an easy question: You have a list of n random floating point numbers, how quickly can you sort them? O(n log(n))? Wrong, you can do better. How about a list of n random strings? O(n log(n))? Actually you’ve probably missed something important there too. How can I say this? Didn’t you learn this in first year computer science? Well, let me explain why I say this.

When the sorting problem is introduced, you typically first look at selection or insertion sort. You soon learn that these algorithms are O(n^2), and very soon you learn that better algorithms, like merge sort and quick sort, can sort in O(n log(n)), but you’ve already glossed over an important assumption. These sorting algorithms are called comparison sorts and they are actually in terms of the running time of a comparison. Now, for numbers like integers and floating point numbers, comparisons are constant time (for a fixed number of bits), but for other data types, like strings, this isn’t the case. So while you can often say that you can sort a list of objects in O(n log(n)), I feel it’s very important to know that this is not always the case.

And this brings me to my other point: You can sort a list of random floating point numbers in better time than O(n log(n)), and it’s very simple: radix sort. Now before you start saying that radix sort only works for integers, you should realise that this just isn’t so. It is actually quite easy to extend the simple radix sort algorithm to floating point numbers. In fact, if you follow a similar process to the linked article, you can sort anything that can be compared in constant time, in O(n) time overall. So while it is true that, because of the large constant factor of radix sort, comparison sort algorithms can give better results in practice (especially if you start parallelising things), radix sort will actually always have a better order complexity for objects that can be compared in constant time.

Now go out into the world and stop making bad assumptions.

Do you have a noisy black-box with a number of parameters that need to be tuned? Then you might just be in luck! The newest paper of the well-known researcher, Rémi Coulom, might be just what you are looking for. In “CLOP: Confident Local Optimization for Noisy Black-Box Parameter Tuning” he describes a new method for optimizing a number of black-box parameters given a noisy output.

To be honest, I have only glanced over the theory behind it, but I have already witnessed some of its power. The reason that is possible is that Rémi has also released software to use. His software is open source and runs on Linux, Mac and Windows. After downloading and building the software, you can run the GUI and be greeted with a simple and intuitive interface. I have included a few screenshots, so you can see what the provided example looks like.

If you think that this is relevant to your work, why not give it a chance? I know I will be making use of it to tune my Computer Go program, Oakfoam. My only complaint is that, in my opinion, the command line interface is slightly lacking; then again, the code is open source, so there is nothing stopping me from improving it…

For more info: http://remi.coulom.free.fr/CLOP/

I just finished the initial round of documenting my open source project, Oakfoam. Initially there were little to no comments, but I decided that this was unacceptable, so over the past couple of weeks, I have been slowly documenting my code. Now, every class and all its public methods have at least a brief line of documentation. I have recently gotten two volunteers for my project, so I think my timing has been rather good.

In order to help the process, I have been making use of Doxygen. It uses the familiar Javadoc “/**” style, whilst helping to compile nice HTML and LaTeX versions of the documentation. I highly recommend having a look at Doxygen for your documentation needs.

I have previously been rather averse to commenting code, believing that code should be understandable without comments. However, after my project has grown to over 10 000 lines of code, I’ve realised the error in my ways. I can now see the use in at least some documentation, especially for an open source project. Why should I expect everyone else to have to wade through my code and figure out what is going on? Hopefully this initial learning curve will be greatly lessened now. After thinking about it, I realise that you can’t expect to attract any contributors without some documentation to guide them. Oakfoam’s documentation is still a long way away from complete, but I do feel like I have reached a milestone.

It’s been a few weeks now since I lasted used gedit as my code editor. I used to only use it, but now I’ve become a converted Vim user.

I was pretty efficient with my setup – my src folder open in the background, gedit to one side and a terminal on the other. However, I have recently had quite a long holiday, so I decided to properly try switch to Vim. I had previously used Vim in small doses when I had to edit a file over an ssh connection, but the time for me to finally jump in the deep end had arrived.

I closed gedit and opened up a nice ol’ terminal where I promptly ran Vim. After some time spent Googling and reading Vim’s excellenct built-in help, I had a nice little vimrc setup. After a few more refinements, before I arrived at my current setup. It looks like this:

Some of the “features” of my setup:

• session plugin – Save and load all my open tabs with F5 and F6.
• molokai theme – Who knew 256 colors could look so good?
• powerline plugin – Works as well as it looks.
• alternate plugin – Quickly switch between my code and header files.
• tagbar plugin – Jump around the current file with ease.
• yankring plugin – Cause everyone uses copy/paste.

If you would like to see exactly how I got it to look like this, have a look at my vimrc. Undoubtedly I will continue to make changes to it, but for the moment, I am rather proud of it.

I got the inspiration to write this post after reading this, so go read that too.

So today I got the degree of BEng (Electronic and Electrical with Computer Science) Cum Laude. It feels good to finish off four years of studies with a ceremonious event. Next year I will be starting with MSc (Computer Science). More on that to come later…

So I was using tumblr for my website (custom domain), but I have decided to switch to WordPress. I’m doing this mostly for more control. I make zero promises of regular blog posts, and I have adjusted my website layout accordingly. My old tumblr posts are available at francoisvn.tumblr.com. If you really want to know what I have to say, you can check back here, but you’re more likely to find out something from my twitter.