Monday, December 16, 2013

Moving On

So I could put another post on here about the genetic algorithm, but everything I wanted to say on the subject has been said about that particular algorithm.

Rest assured, I have many more ideas about optimization algorithms. But let me tell you -- it's getting frustrating. A lot of my ideas about new algorithms for optimization include this RankedSet idea... and it doesn't exist in standard libraries.

Michał Marczyk made one for Clojure called avl.clj (great job, Michał!), and AVL tree implementation of what I call the RankedSet, but the genetic algorithm as below described (and other algorithms bouncing around in my head) need faster insertions/deletions and virtually no lookup. That is precisely what red-black trees are better at over AVL trees.  I need a red-black tree based implementation.

So I decided to learn how to make one.

I am currently going through Chris Oksasaki's "Purely Functional Data Structures". (Even just reading the first chapter, you can tell Rich Hickey idolizes the guy, and for good reason.) For those who don't know, this is a seminal work on how to design your own rock-star data structures. A quote from the first chapter:

Rather than attempting to catalog efficient data structures for every purpose (a hopeless task!), we instead concentrate on a handful of general techniques for designing efficient functional data structures...Once you understand the techniques involved, you can easily adapt existing data structures to your particular needs, or even design new data structures from scratch. (p. 4)
I am even learning OCaml so that I can go through it better (most of the examples in his book are in standard ML, which is to OCaml as C is to C++, as far as I can tell).

Hopefully at some point into it I'll be able to make a RankedSet, share the implementation, and keep writing about awesome algorithms.