Archive
HashSet, Graph, Cognac
The post on applying GPU to finding Eulerian path mentioned a stumbling block: partitioning a very specific kind of graph.
In general, partitioning is a hard problem, NP-hard actually. The graphs we are dealing with are very specific, though, and may be partitioned in 
If we are “lucky” it consists of just one or very few (directed) loops, if not – we have lots of such disconnected loops. And it is this unlucky case that kept the bottle of good cognac sealed all these months (only a descent solution to the partitioning problem would break it out).
To partition such a graph, i.e., color every loop in its distinct color, all we need to do is walk the graph from any vertex and once the loop is detected, we pick a vertex at random from the set of those we haven’t visited yet and start walking again. We repeat until everything is visited:
let partitionLinear (end' : int [])=
let allVertices = HashSet<int>(end')
let colors = Array.create end'.Length -1
let mutable color = 0
while allVertices.Count > 0 do
let mutable v = allVertices.First()
while colors.[v] < 0 do
allVertices.Remove v |> ignore
colors.[v] <- color
v <- end'.[v]
color <- color + 1
colors, color
This is great, except it doesn’t work. The problem is revealed when a graph is very large and very fragmented. This is when the code at line 7 fails us. The problem is, we expect it to work in O(1): how hard can it be to retrieve the “first” element?! Well, since we are dealing with a data structure that does not have an intrinsic notion of order, it may be quite hard. In fact, the complexity here is 
The following code actually works:
let partitionLinear (end' : int [])=
let colors = Array.create end'.Length -1
let mutable color = 0
let mutable num = end'.Length
let mutable curIdx = 0
let mutable nextIdx = num - 1
while num > 0 && curIdx >= 0 do
let mutable v = curIdx
while colors.[v] < 0 do
colors.[v] <- color
v <- end'.[v]
color <- color + 1
num <- num - 1
while nextIdx >= 0 && colors.[nextIdx] >= 0 do
nextIdx <- nextIdx - 1
curIdx <- nextIdx
colors, color
In the worst case it is still
This won’t cure the performance problems of the GPU algorithm, which still relies on the number of graph partitions to be somewhat reasonable, but it will enable it to run in some respectable time. Perhaps time to break out the cognac after all!
Look-and-say: F#
This holiday season my brief indulgence was solving the Advent of Code puzzles. One was about the look-and-say sequence. It starts with “1” and grows as follows:
1 is read off as “one 1” or 11.
11 is read off as “two 1s” or 21.
21 is read off as “one 2, then one 1” or 1211.
1211 is read off as “one 1, then one 2, then two 1s” or 111221.
111221 is read off as “three 1s, then two 2s, then one 1” or 312211.
This has been analyzed. Members’ length grows exponentially, so
Advent of Code Day 10 is asking to output the length of the 41st member of this sequence, starting from 1113122113. And then, in the second part – of the 51st. This is simple enough, however, if one is not careful… It may take a while.
I wrote a solution fast enough, however I wasn’t satisfied with it at all: it looked too generic in style: it could be written this way in any language. The whole point of the indulgence being the aesthetic enjoyment of writing F#.
I looked around and found the following post, which I am delighted to quote as an example of the author’s amazing style and command of the language
let read (input : string) =
input
|> Seq.fold (fun acc x ->
match acc with
| (n, x')::tl when x = x' -> (n+1, x')::tl
| _ -> (1, x)::acc) []
|> List.rev
|> Seq.collect (fun (n, x) -> sprintf "%d%c" n x)
|> fun xs -> System.String.Join("", xs)
If you take a moment to read through it you will be admiring it as much as I was.
Here is my boringly generic solution.
let genNext (s : List<byte>) =
let mutable i = 0y
let mutable c = s.[0]
let reps = List<byte>()
for ch in s do
if c <> ch then
reps.Add(byte i)
reps.Add(c)
c <- ch
i <- 0y
i <- i + 1y
reps.Add(byte i)
reps.Add(c)
reps
If you look at mine – it is totally un-F#. It may as well have been written in C++! It is not motivated by a sense of style, or good taste, or sadly, by a deep sense of the language. It is, however, motivated by performance. The key to great performance is, of course, to know well ahead of time where your performance goes. In this case we do know it: since the structure holding the next sequence member grows in length exponentially, we would like to minimize all operations related to its manipulation. As far as reads – we cannot escape O(n) reads. Same for writes at every step. And now we are faced with a dilemma that a C++ (and possibly a C#) programmer would never face: are we being wasteful with our memory. In fact, so wasteful that it can bog us down? The answer in the first case is – yes, of course. In the second – no.
The first solution that would satisfy any functional purist, creates and destroys its immutable structures every step of the way. Not only that, its input is necessarily a string and so we also need to serialize the sequence we come up with into a string for the sole purpose of deconstructing it again in the next iteration.
At the same time, the second solution, using only an almost minimal amount of memory (it is provable, that the sequence never contains any numbers beyond 1, 2, and 3, so bytes are good), uses exactly one new structure which it returns. We actually don’t need to serialize it back to a string! Let’s see how these compare time wise (number of iterations over the sequence is along the X axis):
It is not unexpected, still kinda staggering. To zoom into the boring solution (it is still exponential):
So this raises a bunch of questions: as our technology evolves, are we going to be able to write more and more aesthetically impeccable (and shorter!) code without caring much for the real world? Or are performance concerns going to ever be looming somewhere very close, forcing more sensible choices? Who is the developer of the future? Is s/he going to be required to write great code but hold more down-to-earth alternatives in mind, effectively cancelling her immunity to trials and tribulations of machine machine-oriented languages like C++ or even C, something that Java set out to free us from ages ago? I don’t know, but I believe the answer for the nearest future at least, should be sought in the world of algorithms. Algorithmic and especially data structural efficiency would help us write in style while still holding on to great performance gains.
