This is the mail archive of the
`gcc-patches@gcc.gnu.org`
mailing list for the GCC project.

Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|

Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |

Other format: | [Raw text] |

*From*: Daniel Berlin <dberlin at dberlin dot org>*To*: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>*Cc*: Michael Hayes <m dot hayes at elec dot canterbury dot ac dot nz>, gcc-patches at gcc dot gnu dot org, rth at redhat dot com*Date*: Tue, 3 Jun 2003 13:39:10 -0400 (EDT)*Subject*: Re: Unreviewed patches*References*: <20030603074901.GA9086@atrey.karlin.mff.cuni.cz><86C084A2-95C1-11D7-840D-000A95A34564@dberlin.org><20030603130546.GA6471@atrey.karlin.mff.cuni.cz>

> > can you send me a reference please? I was searching a web just now and > found nothing except the following citation (from a not really reliable > source) claiming that Cormen, T., C. Leiserson, and R. Rivest. Introduction to Algorithms. Cambridge, MA: MIT Press, 1990. Fredman, M. and Tarjan, R. "Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms." Journal of the Association for Computing Machinery, vol. 34, no. 3, July 1987. ^^^^^^^ Never reviewed this paper, actually, so don't know if it has actual performance results. >From another web page on using f-heaps: "The big surprise, though, is that the F-heap is even competitive on regular heap algorithms like heap sorting. The test programs generate random test data and compare the output against qsort() to make sure the heap is operating correctly. To determine the overall time complexity, you can compare the time for 2048-element and 1024-element data sets. If the process is O(n log), the ratio should be 2.2 to 1. The test program averages a ratio of 2.17 for a binary heap and 2.07 for a Fibonacci heap. The decreased ratio is due to the fact that more of the F-heap operations execute in linear time, including the Insert() and DecreaseKey() operations. In addition, the Fibonacci heap test runs about 15 percent faster than the binary heap test. Even if you remove the DecreaseKey() operation from the test, the Fibonacci heap is still over 10 percent faster. For algorithms like Dijkstra's, the difference can be two to ten times faster on a 1024-vertex graph. " Note, 10% faster even without the decreasekey usage. I'm not near a computer i can get to the rest of the references easily, i'll get you other reliable sources when i get home. I *really* think it's an implementation problem. There are a few ways to do various operations on the fibheap, and i just chose the simplest one, rather than speed testing anything. > > "Fibonacci heaps are asymptotically the best priority queues known: They > perform all heap operations in O(log n) time, some even in amortized > constant time. However, in practise they are "known" (by the > theoreticians) to be inferior eg. to d-heaps because their internal > maintenance is relatively involved. Performance tests (with random data) > indicated that they are indeed a bit slower but not too much (at least > for many elements)." > > Zdenek >

**Follow-Ups**:**Re: Unreviewed patches***From:*Zdenek Dvorak

**References**:**Re: Unreviewed patches***From:*Zdenek Dvorak

**Re: Unreviewed patches***From:*Daniel Berlin

**Re: Unreviewed patches***From:*Zdenek Dvorak

Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|

Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |