In 2017 I implemented the Space Saving algorithm in Scala — a streaming algorithm for finding the top-K most frequent elements in a stream without ever holding the whole stream in memory. You keep a running summary of K slots: if you've seen an item before, bump its counter; otherwise, evict the current least-frequent item and take its slot. By then I'd already been working with Spark for about a year (see the 2016 election analysis), so streaming and distributed processing weren't unfamiliar — but this was different: a plain, theoretical stream read straight from stdin, nothing fancy on top, no framework doing the heavy lifting.
Two implementations, on purpose. I'd just taken Martin Odersky's
Functional Programming Principles in Scala course on Coursera and was
completely into FP at the time. Most work-ready, production apps are written in an
imperative style — but this wasn't one of those; it's a theoretical exercise pulling
data off stdin, nothing more. There was no reason not to also write it as a purely
functional foldLeft over an immutable HashMap, alongside the
imperative version walking a while loop over a mutable one. Comparing the
two side by side taught me more about the tradeoffs between them than either one would
have alone.
Every line of both implementations has a comment explaining not just what it does but why. Looking back at the source now feels a bit like reading a letter from an earlier version of myself.
scala.collection.immutable.HashMap / scala.collection.mutable.HashMap — one per implementationThe source is open, at jane-natucci/SpaceSaving.
This project, together with the USA 2016 Election Analysis with Apache Spark GraphX from the year before, was the portfolio work that got me my first job in Germany.
That job mattered a lot to me. I left it too soon — life happened — but the work itself, and the projects that got me there, still hold up.
TODO: write more about the algorithm itself and what it was like starting that job.