Feb 08 2007
Two Whitepapers Every Developer Should Read
Just forwarding these around work, so I thought I’d share with the blog, too.
Why Functional Programming Matters — It is fundamentally different and fundamentally better than imperative programming. Note that “imperative programming” includes “object-oriented” languages like Java. This article argues why with illustration.
http://www.math.chalmers.se/~rjmh/Papers/whyfp.pdf
Skip Lists — This is my go-to priority queue implementation these days.
ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf
Popularity: 4% [?]
My go-to datastructure these days for priority queues is leftist heaps.
Short explanation of how they work: the core operation is the join, which joins two leftist heaps into one. A leftist heap is either empty or contains a head node with the highest priority element and two child heaps, a left and a right, and the height of the heap (the smallest distance between the root node and a leaf node). Joining two empty heaps results in the empty heap. Joining an empty heap and a non-empty heap simply results in the non-empty heap. Joining two non-empty heaps is the interesting case. I compare the highest priority nodes (root nodes) of the two heaps. The higher priority of the two becomes the new highest priority (root) node of the joined heap. This leaves me with three heaps- the heap containing the root node I didn’t promote, and the two child heaps of the root node I did promote. I pick the tallest of the three and make that the left child of the joined heap. I then recursively join the remaining two shorter heaps to make the right child.
To insert a node, I just create a one-node heap (both children are empty) and join it with the current heap. To remove the head node, I just replace the heap with the join of the two children of the root node.
Note that it’s easy to prove hard O(log N) worst case peformance, as you always go down the shortest branch. The algorithm oddly becomes more efficient if the heap becomes imbalanced. The best skip lists can give you is expected or media behavior, the random element prevents harder gaurentees. Leftist heaps are also easier to implement. And they’re easy to implement in a purely functional manner.
Why functional programming matters is a classic, though.
[...] Looks like skip lists made it into Java 5 — there isn’t a naked version that I can find, but they crop up in java.util.concurrent as a nifty way to bypass some awkward synchronization issues. You can also bookmark this on del.icio.us or check the cosmos [...]