My long path towards O(n) longest-path in 2-trees – Jordan Biserkov
An experience report of using Clojure to implement a novel graph algorithm.
We’ll quickly go over the algorithm, then dive into optimization techniques like choice of data representation, using transient variants of persistent data structures, using macros to inline computations, implementing our own memoization and benchmarking.
We’ll discuss examples of using generative/property-based testing both at the unit and algorithm levels, turning a recursive algorithm into an iterative one and “unrolling” recursion.