#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 LouisWasserman):
Even lazy pairing heaps have the O(n) worst-case delete-min performance.
Amortization isn't going to cut it.
Wikipedia suggested that skew heaps usually outperformed leftist heaps. I
wrote a reasonably refined implementation of skew heaps and got
Times (ms)
min mean +/-sd median max
Pairing: 8.000 12.401 4.274 12.001 28.002
Binomial: 24.001 31.842 6.200 28.002 44.003
Skew: 24.001 31.922 6.280 32.002 48.003
for sorting of random data. Also, more importantly, skew heaps don't even
support amortized O(1) insertion, let alone worst-case. Binomial heaps
support amortized O(1) insertion, worst-case O(log n). There's a variant
of binomial heaps which supports worst-case O(log n) insertion, but it's
not very pretty to code, and it would make an already large amount of code
blow up hugely. I'm willing to settle for the amortized bounds there.
Conclusion: I'm inclined to stick with binomial heaps. Further
experimentation has indicated that there isn't much difference between
lazy and strict sorting speeds, so I'm inclined to stick with the strict
implementation -- again for the crowd who needs real-time performance.
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/3909#comment:20>
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
