Does the F# library include a priority queue? Else can someone point to me an implementation of priority queue in F#?
A:
With F# you can use any .NET library so if you are ok with using an implementation which is not written in F# I Wintellect Power Collection Library.
Matthew Manela
2010-07-24 19:28:43
I didn't mention .net generally because I preferred something that I can understand (I don't know C#). Anyway, I had a quick look at the library and I can't find an implementation of a priority queue or a heap. There was a comment in http://stackoverflow.com/questions/102398/priority-queue-in-net that OrderedBag is usable but less efficient than heaps. Do you have any experience with it?
Muhammad Alkarouri
2010-07-24 20:10:58
The OrderedBag is what you want. It is implemented with a more complex algorithm but that won't really affect its performance in most cases
Matthew Manela
2010-07-24 20:23:57
+8
A:
Take a look at http://lepensemoi.free.fr/index.php/tag/data-structure for a whole bunch of F# implementations of various data structures.
kvb
2010-07-25 01:17:27
A treasure trove! That is brilliant. To be fair I accepted Lee's answer as I used the data structure in his link earlier. I was intending to write the Okasaki book structures in F# at some point, and here it is (largely).
Muhammad Alkarouri
2010-07-27 01:44:30
A:
Just use an F# Set of pairs of your element type with a unique int (to allow duplicates) and extract your elements with set.MinElement or set.MaxElement. All of the relevant operations are O(log n) time complexity. If you really need O(1) repeated access to the minimum element you can simply cache it and update the cache upon insertion if a new minimum element is found.
There are many kinds of heap data structures that you could try (skew heaps, splay heaps, pairing heaps, binomial heaps, skew binomial heaps, bootstrapped variants of the above). For a detailed analysis of their design, implementation and real-world performance see the article Data structures: heaps in The F#.NET Journal.
Jon Harrop
2010-07-29 18:15:40
The solution I ended up using is a [Binomial Heap](http://en.wikipedia.org/wiki/Binomial_heap) as described in Okasaki's book. Operations are generally O(log n). Can you tell me the time and memory properties of the F# set to be able to compare?
Muhammad Alkarouri
2010-07-29 22:37:48
Typically one asks for O(1) for access to the min element, since it's the primary operation of a PQ.
Mau
2010-07-30 10:54:17
@Mau: Inserting 1,000,000 random floats and then removing the smallest element repeatedly until none remain takes 32s with Okasaki's binomial heap in F#, 8s with F#'s built-in `Set` and 4s with .NET's built-in `SortedSet`. The difference between O(1) and O(log n) is insignificant in this context.
Jon Harrop
2010-07-30 11:57:01
@Jon: May be you are right. But you can't decide that a Set is the solution by fiat and then go on accusing others that they don't accept it. A main advantage of a priority queue is O(1) for access. I referred you to the web page before. If in measuring `Set` works then Ok. Just remember: (1) Your current test is wrong. If you insert all the points then extract then 1 by 1 then you are effectively comparing a heap sort (equivalent to sort using a heap) with whatever sort the set uses. (2) If you can explain the underlying data structure of F# `Set` then it may be obvious that it is better.
Muhammad Alkarouri
2010-07-30 16:51:24
@Jon: remember that this question did take some time till the answer is accepted. You've got to pu a little more effort in why everybody else got it wrong, if you want to accuse us.
Muhammad Alkarouri
2010-07-30 16:52:56
@Jon: while you are at it. Unlike `Set`, queues store duplicates. Does F# has a bag data structure that can be used instead of `Set` with the same functionality but can store duplicates?
Muhammad Alkarouri
2010-07-30 17:10:36
@Muhammad: A `Set` is implemented as a balanced binary tree and you can map duplicates onto unique elements by augmenting them with a unique ID.
Jon Harrop
2010-07-30 17:31:06
@Muhammad: I just did another benchmark adding 1,000 elements to a priority queue and then adding a random element and removing the smallest 1,000,000 times: Okasaki's binomial heap took 3s, F#'s `Set` took 1.9s and `SortedSet` took 0.9s. So, again, the difference between constant and logarithmic time complexity is overwhelmed by constant factors.
Jon Harrop
2010-07-30 18:24:53
@Jon: thanks. I quote wikipedia _To get better performance, priority queues typically use a heap as their backbone, giving O(log n) performance for inserts and removals. Alternatively, if a self-balancing binary search tree is used, all three operations take O(log n) time; this is a popular solution where one already has access to these data structures, such as through third-party or standard libraries._ In particular, a tree enforces more constraints than a heap.Still, your timing results show enough difference that a `Set` is probably better. I will see if it gives me better results.
Muhammad Alkarouri
2010-07-30 18:27:41
@Jon: In my application the `Set` behaves 3 times worse than the Binomial heap in the selected answer as a priority queue. As it happens, in my application the custom comparison is the expensive operation, and I wrapped my type in a wrapper as shown [here](http://stackoverflow.com/questions/1784485) before using `Set`. You may want to try it with custom comparers. Else publish the small benchmark you used so I can reproduce your results.
Muhammad Alkarouri
2010-08-02 23:34:02
Can you make your wrapper type a struct instead of a class to avoid one level of indirection? What is your actual element type? If you want more performance, .NET's mutable `SortedSet` is typically a few times faster that F#'s `Set` because it stores the balanced tree directly in an array. BTW, my code there includes a third test where a binomial heap comes between `Set` and `SortedSet` for performance. You might also try other kinds of heap such as a LeftistHeap: http://flyingfrogblog.blogspot.com/2010/05/purely-functional-heap-sort-in-ocaml-f.html
Jon Harrop
2010-08-03 03:20:13
FWIW, the leftist heap I just referred you to is not only simpler than a binomial heap in F# but it beats it on all three of my benchmarks.
Jon Harrop
2010-08-03 03:57:54
@Jon: Sorry I wasn't able to do the tests at the time, life intruded. Thanks for the code. I haven't tried the `SortedSet` yet because I am not on .Net 4, but the others are performing largely in line with your numbers (scaled by 1.5, uncannily accurately). I will test it on my data, probably with a better design for a wrapper, as well as `SortedSet` later this week.
Muhammad Alkarouri
2010-08-08 23:20:36
+2
A:
There is a discussion of functional data structures for priority queues in issue 16 of The Monad.Reader, which is interesting.
It includes a description of pairing heaps which are fast and very easy to implement.
Mau
2010-07-30 10:41:21