#3909: Priority queues in containers
-------------------------------------------+--------------------------------
Reporter: LouisWasserman | Owner: LouisWasserman
Type: feature request | Status: assigned
Priority: normal | Milestone:
Component: libraries (other) | Version: 6.12.1
Keywords: containers, priority queue | Difficulty:
Os: Unknown/Multiple | Testcase:
Architecture: Unknown/Multiple | Failure: None/Unknown
-------------------------------------------+--------------------------------
Comment(by milan):
Hi,
another benchmark [[attachment:benchmark_2.tgz]]. This time I benchmarked
* Binomial -- {{{Data.PQueue.Min}}} from (v5) patch
* Pairing -- {{{Data.PQueue.Pairing}}} from (v5) patch
* Skew -- [[attachment:Skew.hs]]
* !PairingByMilan -- in the [[attachment:benchmark_2.tgz]]
* !LeftistByMilan -- in the [[attachment:benchmark_2.tgz]]
This time I measured only the heap-sort of random list with various
lengths -- the number in the test name is the logarithm of the list size.
[[Image(plot_2.png)]]
* the Pairing implementation is still too strict -- I believe there are N
inserts and N deletemins in the persistent settings, such that Pairing
will need O(N^2^) to answer them
* my !LazyPairing in the previous benchmark was buggy. This time it
works, but is worse than Binomial
* !LeftistByMilan is actually pretty good for small inputs (up to ~
2^16^), 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 think the pairing heaps are out of the question now. I would choose
between Binomial and Leftist. The Binomial have O(1) amortized inserts,
but beware, that this does not work in persistent setting -- the insert is
O(log N) when the heaps are used persistently (there are Skew Binomial
Heaps with O(1) insert in the persistent setting too).
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).
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/3909#comment:32>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
