Re: Libraries Digest, Vol 79, Issue 31
Yo,
* I'm not comfortable with having two redundant modules, one for Min- and one for MaxQueue. It is possible to implement both in the same data structure and still get type errors when e.g. 'union' on a Min- and a MaxQueue (I did that in [1], please have a look at the latest version). My solution needs type families, which would not be good for containers, but I'm pretty sure there's a containers-compatible solution.
I'm pretty sure there won't be a containers-compatible solution, certainly not a solution compatible with the style of containers as it's currently written, because your solution depends on exporting functionality with type classes. If we're going to change that style in containers, it should be done all at once, in a complete rewrite. Whether or not priority queues get added to containers, I'm at least going to keep the style *consistent* with containers. With regards to benchmarks, we examined a comparison with leftist heaps earlier. The biggest complaint is the O(log n) insert time, which is really kind of icky. Here was Milan's conclusion: LeftistByMilan is actually pretty good for small inputs (up to ~ 216), and
the implementation is super-trivial compared to Binomial. But when the list gets bigger, the complexity gets worse. I think this is beause of O(log N) inserts -- the Binomial implementation with O(1) amortized inserts allocates much less memory and does not need to run a GC. I vote for current (v5) Binomial implementation, even if the O(1) amortized inserts works only non-persistently (ie. under heavy persistent usage, leftist heaps might be a _little_ better).
Furthermore, I added your implementation to the benchmarks that we'd been using previously, which was essentially a full heapsort, rather than just searching for the five smallest elements as in your quickie benchmark. By this comparison, your implementation is moderately slowerhttp://code.haskell.org/containers-pqueue/bench-chart.pdf. (The source code and data for this benchmark version are now in the code.haskell.org/containers-pqueue directory.) Though your implementation might be faster for some particular cases of problems, I think this is a fair comparison overall, and I'm definitely not willing to accept leftist heaps' O(log n) insert time given the slower overall performance for heapsort. This is what the Haskell Platform is for. No real need to add more
stuff to containers; if anything, the libraries stored there should be decoupled so that e.g. the recent Data.Map proposals wouldn't disturb programs not using Data.Map.
Again, my preference is to add pqueues to containers, and then if containers gets decoupled, then so will priority queues. If I'm going to split off a separate package for priority queues, it'll be because I've been convinced that it ought to be separated from containers, period -- not just because people think containers should be broken up, and this is a good place to start. Meh. Louis Wasserman wasserman.louis@gmail.com http://profiles.google.com/wasserman.louis
On 03/19/10 09:39, Louis Wasserman wrote:
Yo,
* I'm not comfortable with having two redundant modules, one for Min- and one for MaxQueue
I'm pretty sure there won't be a containers-compatible solution, certainly not a solution compatible with the style of containers as it's currently written
On 03/19/10 06:26, Ross Paterson wrote:
If keys are separate, the two versions could be easily achieved using an inversion adaptor on Ord, which has been proposed before and would have many other uses.
I agree with Ross. We should add Data.Ord.Opposite, or whatever we decide to call it, (newtype Opposite a = Opposite { getOpposite :: a } deriving (Eq, Show, ...), and the obvious Ord instance.) This works with Data.Map too. Additionally I suggest, since folding a Map produces keys lowest-first, that we choose the same behavior for the priority queue. On the other hand, separating the key and the value gives us the same Data.Map vs. Data.Set mess (which maybe is not a bad mess, but, it would suggest there should be two different PQ modules too, one with associated non-ordered data and the other with only the priorities). -Isaac
Okay, here's my current plan: I think I'm going to withdraw the ticket for containers, and launch a package to be included in a future release of the Haskell Platform. First off, I'd like to know what the procedure is for adding something to the Platform. I haven't been able to find a mailing list dedicated to it, so I don't know where it should be discussed. (In all likelihood, I'm missing some obvious link on either Trac or HaskellWiki or something...) First, people should look at my current setup, and complain at me about the design. Haddock documentation is herehttp://code.haskell.org/containers-pqueue/pqueue-1.0.0/html/, though I've only so far documented the minimum-queue variants; in general, I aimed to use the same function names used by Data.Map and Data.Set wherever possible, so "extract," "top," and "delete" have been replaced by the function names used for the analogous methods in Data.Map and Data.Set. Probably the single aspect of the design I'm least happy about is how I distinguish between the priority queues that distinguish a key and an element, and those which don't. Currently, the Data.Map-style key/element version is named MinPQueue k a, and lives in the module Data.PQueue.Prio.Min, and the Data.Set-style version is named MinQueue a, and lives in the module Data.PQueue.Min. Can anybody think of better names for these things? Finally, I'm not going to consider any more alternative implementations at this point. My implementation has performed outstandingly on benchmarks, and has beaten a number of competitors. If someone believes that they have a superior implementation, they should email me off-list, and perhaps a later version of the package will be based on a different implementation, but for the moment I'm sticking to the type-magical binomial heap implementation. Louis Wasserman wasserman.louis@gmail.com http://profiles.google.com/wasserman.louis
My implementation has performed outstandingly on benchmarks, and has beaten a number of competitors. If someone believes that they have a superior implementation, they should email me off-list
So far, the only benchmarks I have seen have been heapsorts. I think it is worth at least discussing whether or not other benchmarks are worth considering. Heapsort, for instance, calls insert and extractMin the same number of times. It also does not use the data structures persistently. It does not necessarily test toUnsortedList or meld. Furthermore, I think it is better to discuss performance comparisons and requirements in the open, rather than in private off-list emails. Louis, if you're too busy to engage in additional performance discussion on this list, I'm sure nobody will think less of you for it. Finally, I agree with Louis that there is probably no rush to get the implementation perfect before fixing an interface. I just think we should carefully work to measure and improve priority queue performance out in the open.
On Sun, Mar 21, 2010 at 09:56:02PM -0600, Louis Wasserman wrote:
First off, I'd like to know what the procedure is for adding something to the Platform. I haven't been able to find a mailing list dedicated to it, so I don't know where it should be discussed. (In all likelihood, I'm missing some obvious link on either Trac or HaskellWiki or something...)
It does seem hard to find starting from http://hackage.haskell.org/platform/ Anyway, it's here: http://trac.haskell.org/haskell-platform/wiki/AddingPackages Thanks Ian
participants (4)
-
Ian Lynagh -
Isaac Dupree -
Jim Apple -
Louis Wasserman