1. 19

  2. 8

    This is a pretty sad story, for several reasons:

    • Java has a builtin PriorityQueue, which you can use in Clojure if you want. It’s mutable, but it’s really easy…

    • In the real world, Fibonacci heaps only give you a marginal speedup over binary heaps (see this stack overflow). With two hundred nodes in a dense graph, its unlikely that there’d be any noticeable difference.

    • For such a small graph, the offline O(N2) algorithm which computes the shortest paths for every node to every other node seems attractive.

    • The standard reference for functional data structures suitable for Clojure is Chris Okasaki’s 1996 thesis Purely Functional Data Structures. He implements pure, functional binary heaps in that in Standard ML. In that same year, Okasaki has also published an asymptotically optimal heap with the same complexity as Tarjan’s Fibonacci Heap. This probably would have helped the author avoid her “OMG How do I do mutable data structures in Clojure??” moment (she also could have resorted to atoms if she was desperate, or java interop if she was super-desperate).

    1. 9

      i read this as a pretty happy story - at the cost of a few days of work, the author gained a deeper understanding of fibonacci heaps, persistent data structures and the tradeoffs they make. all in all i’d call it a win and i’m pretty sure she does too, despite the “ruins my life” (which i read as humorously over-the-top)

      1. 4

        As a story of exploring algorithms and data structures, I found it a fascinating exploration. Often times, this is how I learn new things: might try to explore how a data structure or algorithm might be relevant to a project, even if it’s not the best, in order to better understand it and maybe get a feel for when it would be appropriate.

      2. 4

        I don’t think the point of the project was a Fibonacci heap deliverable. The point was to learn about an interesting data structure in an interesting language. If I’m not mistaken, the author was participating in Hacker School, which has given rise to such interesting things as: http://jvns.ca/projects/#os-rust which I followed as she was writing it. Despite having taken an OS class already, this was a very interesting review of some topics we didn’t cover.

        1. 2

          The article is from two years ago. At the time, she was a hacker schooler, and is now a member of the faculty.

          1. 1

            Ah, thanks for the correction! Edited above.