Clean code for Algorithms

I recently had to dig into pure algorithmic code at work in order to implement a research paper.

Exploring the literature, I was pretty astonished to see how clean code is generally ignored in this sphere. I first assumed it was for performance reasons so I decided to investigate a bit further.

Let’s pick a classic Union-Find data structure, give a standard implementation then a clean one and benchmark both to see if there’s a difference.

Union-Find algorithms

Union-Find data structures are used to address dynamic connectivity problems . They always handle the 2 same functions :

connect 2 given nodes (using their specific data structure)
tell if 2 nodes are connected.

Connection rules are pretty simple :

a node p is connected to itself
if a node p is connected to a node q, then q is connected to p
if p is connected to q & q is connected to r, then p is connected to r

Example image

http://researchhubs.com/post/computing/algorithm-1/dynamic-connectivity.html

Our test algorithm

We’ll use the Weighted Quick-Union with Path Compression algorithm for our benchmarks.

And, here’s the sort of code you’ll usually encounter (golang) :

Original code

type UnionFinder interface {
	Union(p, r int)
	Connected(p, r int) bool
}

// wqupc : Weighted Quick Union with Path Compression algorithm
type wqupc struct {
	ids []int
	w   []int
}

func NewWqupc(n int) UnionFinder {
	result := &wqupc{}
	result.ids = make([]int, n)
	result.w = make([]int, n)
	for x := range result.ids {
		result.ids[x] = x
		result.w[x] = 1
	}
	return result
}

func (q *wqupc) Connected(p, r int) bool {
	return q.root(p) == q.root(r)
}

func (q *wqupc) Union(p, r int) {
	qp := q.root(p)
	qr := q.root(r)
	if qr == qp {
		return
	}

	if q.w[qr] > q.w[qp] {
		q.ids[qp] = qr
		q.w[qr] += q.w[qp]
		return
	}
	q.ids[qr] = qp
	q.w[qp] += q.w[qr]
}

func (q *wqupc) root(r int) int {
	for {
		if r == q.ids[r] {
			return r
		}
		q.ids[r] = q.ids[q.ids[r]]
		r = q.ids[r]
	}
}

Pretty easy to grasp the logic of this algorithm, isn’t it ? :)

Nope ? Let’s refactor this to see if we can make it more readable.

Cleaner code

type UnionFinder interface {
   Union(p, r int)
   Connected(p, r int) bool
}

// clean : Weighted Quick Union with Path Compression algorithm
type clean struct {
	ids     []int
	weights []int
}

func NewClean(size int) UnionFinder {
	uf := &clean{}
	uf.initializeArrays(size)
	return uf
}

func (cleanUF *clean) Connected(nodeOne, nodeTwo int) bool {
	return cleanUF.root(nodeOne) == cleanUF.root(nodeTwo)
}

func (cleanUF *clean) Union(nodeOne, nodeTwo int) {
	rootOne := cleanUF.root(nodeOne)
	rootTwo := cleanUF.root(nodetwo)
	if haveTheSameRoot(rootOne, rootTwo) {
		return
	}

	smallTreeRoot, largeTreeRoot := cleanUF.sortRootsByTreeLength(rootOne, rootTwo)
	cleanUF.attachSmallTreeToLargeTreeRoot(smallTreeRoot, largeTreeRoot)
	cleanUF.addSmallTreeLengthToLargeOne(smallTreeRoot, largeTreeRoot)
}

//
// privates
//
func (cleanUF *clean) root(node int) int {
	for {
		if cleanUF.isRoot(node) {
			return node
		}

		node = cleanUF.attachToRootRoot(node)
	}
}

func (cleanUF *clean) initializeArrays(size int) {
	cleanUF.ids = intVectorOfSize(size)
	cleanUF.weights = intVectorOfSize(size)

	for x := 0; x < size; x++ {
		cleanUF.ids[x] = x
		cleanUF.weights[x] = 1
	}
}

func intVectorOfSize(size int) []int {
	return make([]int, size)
}

func (cleanUF *clean) addSmallTreeLengthToLargeOne(smallTreeRoot int, largeTreeRoot int) {
	cleanUF.weights[largeTreeRoot] += cleanUF.weights[smallTreeRoot]
}

func (cleanUF *clean) attachSmallTreeToLargeTreeRoot(smallTreeRoot, largeTreeRoot int) {
	cleanUF.ids[smallTreeRoot] = largeTreeRoot
}

func (cleanUF *clean) sortRootsByTreeLength(rootOne, rootTwo int) (int, int) {
	if cleanUF.weights[rootOne] < cleanUF.weights[rootTwo] {
		return rootOne, rootTwo
	}

	return rootTwo, rootOne
}

func haveTheSameRoot(rootFirst, rootSecond int) bool {
	return rootFirst == rootSecond
}

func (cleanUF *clean) attachToRootRoot(node int) int {
	newRoot := cleanUF.ids[cleanUF.ids[node]]
	cleanUF.ids[node] = newRoot
	return newRoot
}

func (cleanUF *clean) isRoot(r int) bool {
	return r == cleanUF.ids[r]
}

Ok, the file is 30% longer but I hope the exported methods code is self-explanatory and you just have to read 20 lines in order to get the idea behind this implementation.

Benchmark !

BenchmarkMain/standard-4                    300000       3700 ns/op
BenchmarkMain/clean-4                       500000       3601 ns/op
BenchmarkMain/standard_second_time-4        500000       3630 ns/op
BenchmarkMain/clean_second_time-4           500000       3663 ns/op

The results are a bit flaky, so I ran the benchmarks twice for each algorithm.

As you can see, results are pretty much the sames. Sometimes the clean version is a bit faster, sometimes it’s a bit slower. My guess is they’re just as fast, it’s just the system is sometimes a bit more busy doing something else…


A question or comment ? Feel free to reach me on Twitter

 
Sorry for not tracking you, leave a little message or like below if you want me to know you enjoyed some content here
comments powered by Disqus