#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
-------------------------------------------+--------------------------------
Changes (by milan):
* cc: f...@… (added)
Comment:
Hi,
I created a small benchmark benchmarking a performance of heap sort using
a
* pairing heap from pairing-heap.patch ("pq")
* binomial heap from containers-pqueue.4.patch ("bq")
* mine lazy pairing heap (in the benchmark) ("lpq")
[[Image(plot.png)]]
The benchmark is drawn from "pq" point of view. The number in the test
label is the logarithm of the size of the list to sort, asc/dsc means the
input list was ordered increasingly/decreasingly, rnd means the input list
was random. In every cases {{{toAscList . fromList}}} was used. The
sources of the benchmark are uploaded too, just unpact
[[attachment:benchmark.tgz]] and do {{{make plot}}} with {{{progression}}}
installed. I used GHC 6.12.1.
What is suprising is that lazy pairing heaps are faster than pairing heaps
on random input data, ie. in the "interesting" case.
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/3909#comment:16>
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
