When I finished the post about my exploration of the algorithm to map from a distance to Hilbert coordinates and back, one of the things that still bothered me was that I had not yet implemented some of the optimizations that I could see were possible. For example, the unnecessary creation of additional HilbertCurveSegment class instances and the mapping through a set of basis vectors for what amounted to a simple bit rotation.

So, this afternoon I sat down and created an updated version (which I’ve added to the HilbertCurveExample repository) that implements these ideas. I haven’t bothered to benchmark it against the original but I’m sure it is a considerable improvement if only in terms of its memory footprint.

I had an additional motivation to finish this update. Midway through my work to get to the root of this algorithm, I ran a search (in a moment of frustration) that surfaced a stackoverflow posting whose answer offered what purported to be an actual implementation of the algorithm that I was looking for. Rather than read and implement it (like most normal people might), I simply scanned the code briefly to get a sense of the size and then set aside a link to it. Just seeing that an implementation was available in the event that I truly got stuck gave me enough motivation to press forward.

All the same, I wanted to have a look at this code and the paper associated with it – but not until I’d finished my work. I considered it a challenge to see how close my final solution would be (I still haven’t read it yet but I plan to do so once I finish this post).

The implementation that I completed today discards the HilbertCurveSegment class (which I had implemented in order to help frame the concept that a distance expressed an address related to the vertices of a set of nested N-cubes) and instead computed coordinate vectors, reflections, and basis vector transformations directly. I also discarded the idea of basis vectors since the only key principal that I needed to preserve was the rotation of the basis, which could be implemented more efficiently as a bit rotation. Finally, I attempted to express the concept of bit vector (and its relationship to an ordered sequence of vertices) more forcefully by providing certain variables a suffix of bitVector or vertexRank.

With all of these changes folded in, the final implementation reduces to a little more than 200 lines of code (with comments).

Alright, now it’s reading time…