Space Saving Algorithm

What Is It?

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, 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. Obviously, most production apps are written in an imperative style - but this wasn't one of those. It's just a theoretical exercise pulling data off stdin. So 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.

Commented With Love

Every line of both implementations has a comment explaining what it does and why. I was very excited to have a functional version of the program and didn't want to let go of working on it, so I also wrote extensive comments. Functional programming languages allow you to use unusual data structures and language idioms that are more suitable for particular problems that don't always arise at regular production work, so writing as many comments as possible allowed me to stay with my program for as long as possible, or at least for longer than otherwise :)

The Stack

Built With

Scala 2.11
Maven – build via scala-maven-plugin, packaged as a fat jar with maven-shade-plugin
ScalaTest – the functional and imperative versions tested against the same cases
scala.collection.immutable.HashMap / scala.collection.mutable.HashMap – one per implementation

The source is open, at jane-natucci/SpaceSaving.

First Job in Germany

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.