This is the mail archive of the 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]

Re: Unreviewed patches

> 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

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]