Subject: Re: [boost] [heap] A performance test and some questions
From: Tim Blechmann (tim_at_[hidden])
Date: 2011-06-08 04:07:24
> I now also included pairing_heap and skew_heap in the performance test.
> However, I get a segfault for pairing_heap when running the "Linear
> Forward" performance test. That's the place with "// if (0)" in the
> attached file. When I uncomment that line, I get the following results
... the pairing heap is a self adjusting data structure ... and it is
recursively implemented. there are some use cases, where the heap degenerates
into a linear list ... the bigger problem is the fact that the heap is
implemented recursively ... that means that in some cases you can run into a
recursion of O(n) ...
in your example, your simply run into a stack overflow ... (there is a warning
in the class reference about this issue)
> What's impressive here is that pairing_heap and skew_heap have a compare
> count a factor 10 smaller than any other heap for the "Linear Backward"
> performance test.
skep heaps have an amortized complexity for all operations. pairing heaps are
difficult to analyze but give pretty good real-world results ...
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk