Tim Blechmann wrote:
hi thomas,
reproduced and fixed the issue with the fibonacci heap ...
tim
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 (linux32): Performance Check for Linear Forward 270 ticks and 15952569 compares for TStaticHeap 280 ticks and 15952569 compares for TStaticHeap 100 ticks and 5495826 compares for TSequentialHeap 80 ticks and 5495826 compares for TSequentialHeap 470 ticks and 20929621 compares for b_heap 470 ticks and 20929621 compares for b_heap 400 ticks and 7012461 compares for binomial_heap 420 ticks and 7012461 compares for binomial_heap 300 ticks and 16164008 compares for d_ary_heap 290 ticks and 16164008 compares for d_ary_heap 210 ticks and 5637046 compares for fibonacci_heap 220 ticks and 5637046 compares for fibonacci_heap 850 ticks and 17013833 compares for skew_heap 850 ticks and 17013833 compares for skew_heap Performance Check for Linear Backward 280 ticks and 22976046 compares for TStaticHeap 260 ticks and 22976046 compares for TStaticHeap 100 ticks and 5225203 compares for TSequentialHeap 90 ticks and 5225203 compares for TSequentialHeap 620 ticks and 31971032 compares for b_heap 630 ticks and 31971032 compares for b_heap 260 ticks and 5636875 compares for binomial_heap 270 ticks and 5636875 compares for binomial_heap 350 ticks and 19465560 compares for d_ary_heap 350 ticks and 19465560 compares for d_ary_heap 220 ticks and 5866500 compares for fibonacci_heap 230 ticks and 5866500 compares for fibonacci_heap 140 ticks and 458856 compares for pairing_heap 150 ticks and 458856 compares for pairing_heap 100 ticks and 458856 compares for skew_heap 110 ticks and 458856 compares for skew_heap Performance Check for March 1590 ticks and 93489201 compares for TStaticHeap 1560 ticks and 93489201 compares for TStaticHeap 710 ticks and 53507489 compares for TSequentialHeap 730 ticks and 53507489 compares for TSequentialHeap 2550 ticks and 121120384 compares for b_heap 2530 ticks and 121120384 compares for b_heap 3400 ticks and 73639894 compares for binomial_heap 3410 ticks and 73639894 compares for binomial_heap 1620 ticks and 92667621 compares for d_ary_heap 1590 ticks and 92667621 compares for d_ary_heap 1250 ticks and 39902719 compares for fibonacci_heap 1260 ticks and 39902719 compares for fibonacci_heap 1910 ticks and 38838757 compares for pairing_heap 1900 ticks and 38838757 compares for pairing_heap 6380 ticks and 100758422 compares for skew_heap 6380 ticks and 100758422 compares for skew_heap 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. Regards, Thomas