#3909: Priority queues in containers
---------------------------------+------------------------------------------
Reporter: LouisWasserman | Owner: LouisWasserman
Type: feature request | Status: assigned
Priority: normal | Component: libraries (other)
Version: 6.12.1 | Keywords: containers, priority queue
Os: Unknown/Multiple | Testcase:
Architecture: Unknown/Multiple | Failure: None/Unknown
---------------------------------+------------------------------------------
Comment(by LouisWasserman):
A brief benchmark approach:
Heapsorting 25000 integers, with +RTS -H128m:
min mean +/-sd median max
Pairing: 32.002 34.042 2.756 32.002 52.004
Binomial/l: 64.004 67.324 2.348 68.004 76.005
Binomial/s: 72.004 76.205 3.134 76.005 88.005
/l and /s are lazy and strict spines, respectively. I should implement a
less-typesafe, more-compact version of binomial heaps for comparison, as
well.
How amenable would people be to exporting several different versions of a
priority queue from containers? If we only stuck to one, which one should
it be?
Binomial queues offer guaranteed O(log n) worst-case performance on any of
their operations, but pairing heaps offer almost everything in guaranteed
O(1) time in exchange for typically much faster, amortized O(log n),
albeit worst-case O(n), delete-mins. Which one of these is more critical
to most users, and which of these might be preferable to just put in a
package and recommend to users with particular needs?
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/3909#comment:11>
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
