Data Structures and Algorithms: Unterschied zwischen den Versionen
Hannes (Diskussion | Beiträge) K (→Fibonacci heap) |
Hannes (Diskussion | Beiträge) (→Heaps) |
||
| Zeile 4: | Zeile 4: | ||
* especially the [[Wikipedia:Fibonacci_heap|Fibonacci Heap]] has a to my knowledge the very best asymptotic complexity of O(1) almost everywhere. | * especially the [[Wikipedia:Fibonacci_heap|Fibonacci Heap]] has a to my knowledge the very best asymptotic complexity of O(1) almost everywhere. | ||
'''However, practice shows that'''... | '''However, practice shows that'''... | ||
| − | Currently as of 0.51pre we use a AVL tree which has complexity O(log(n)). Hannes tested the fibheap package from gcc and found out that in our networks (~ 200 nodes) the AVL tree heap implementation still beats the fibonacci heap by 60%. | + | Currently as of 0.51pre we use a AVL tree which has complexity O(log(n)). |
| + | Hannes tested the fibheap package from gcc and found out that in our networks (~ 200 nodes) the AVL tree heap implementation still beats the fibonacci heap by 60%. all results are in us based on a Intel celeron running at 1300 Mhz. | ||
== Fibonacci heap == | == Fibonacci heap == | ||
Version vom 24. November 2007, 14:14 Uhr
Inhaltsverzeichnis
Heaps
- Heap ... We need good heaps/priority queues for A*-Search / Dijkstra
- especially the Fibonacci Heap has a to my knowledge the very best asymptotic complexity of O(1) almost everywhere.
However, practice shows that... Currently as of 0.51pre we use a AVL tree which has complexity O(log(n)). Hannes tested the fibheap package from gcc and found out that in our networks (~ 200 nodes) the AVL tree heap implementation still beats the fibonacci heap by 60%. all results are in us based on a Intel celeron running at 1300 Mhz.
Fibonacci heap
--- SPF-stats for 203 nodes, 335 routes (total/init/run/route/kern/cleanup):,, 237, --- SPF-stats for 203 nodes, 337 routes (total/init/run/route/kern/cleanup):,, 238, --- SPF-stats for 203 nodes, 337 routes (total/init/run/route/kern/cleanup):,, 238, --- SPF-stats for 203 nodes, 339 routes (total/init/run/route/kern/cleanup):,, 239, --- SPF-stats for 203 nodes, 339 routes (total/init/run/route/kern/cleanup):,, 238, --- SPF-stats for 203 nodes, 341 routes (total/init/run/route/kern/cleanup):,, 240, --- SPF-stats for 203 nodes, 341 routes (total/init/run/route/kern/cleanup):,, 236, --- SPF-stats for 203 nodes, 341 routes (total/init/run/route/kern/cleanup):,, 238, --- SPF-stats for 203 nodes, 341 routes (total/init/run/route/kern/cleanup):,, 238, --- SPF-stats for 203 nodes, 345 routes (total/init/run/route/kern/cleanup):,, 239, --- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 238, --- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 238, --- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 238, --- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 238, --- SPF-stats for 203 nodes, 347 routes (total/init/run/route/kern/cleanup):,, 238,
AVL heap
AVL heap: --- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 143, --- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 142, --- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 142, --- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 144, --- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 145, --- SPF-stats for 203 nodes, 347 routes (total/init/run/route/kern/cleanup):,, 145, --- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 142, --- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 142, --- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 144, --- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 145, --- SPF-stats for 203 nodes, 347 routes (total/init/run/route/kern/cleanup):,, 145, --- SPF-stats for 202 nodes, 347 routes (total/init/run/route/kern/cleanup):,, 145, --- SPF-stats for 202 nodes, 347 routes (total/init/run/route/kern/cleanup):,, 142, --- SPF-stats for 202 nodes, 347 routes (total/init/run/route/kern/cleanup):,, 146,
The following complexities<ref> Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest (1990): Introduction to algorithms. MIT Press / McGraw-Hill. </ref> are worst-case for binary and binomial heaps and amortized complexity for Fibonacci heap. O(f) gives asymptotic upper bound and Θ(f) is asymptotically tight bound (see Wikipedia:Big O notation). Function names assume a min-heap.
| Operation | Binary | Binomial | Fibonacci |
|---|---|---|---|
| createHeap | Θ(1) | Θ(1) | Θ(1) |
| findMin | Θ(1) | O(lg n) or Θ(1) | Θ(1) |
| deleteMin | Θ(lg n) | Θ(lg n) | O(lg n) |
| insert | Θ(lg n) | O(lg n) | Θ(1) |
| decreaseKey | Θ(lg n) | Θ(lg n) | Θ(1) |
| merge | Θ(n) | O(lg n) | Θ(1) |
AVL heap
AVL heap: --- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 143, --- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 142, --- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 142, --- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 144, --- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 145, --- SPF-stats for 203 nodes, 347 routes (total/init/run/route/kern/cleanup):,, 145, --- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 142, --- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 142, --- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 144, --- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 145, --- SPF-stats for 203 nodes, 347 routes (total/init/run/route/kern/cleanup):,, 145, --- SPF-stats for 202 nodes, 347 routes (total/init/run/route/kern/cleanup):,, 145, --- SPF-stats for 202 nodes, 347 routes (total/init/run/route/kern/cleanup):,, 142, --- SPF-stats for 202 nodes, 347 routes (total/init/run/route/kern/cleanup):,, 146, </pre>
The following complexities<ref> Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest (1990): Introduction to algorithms. MIT Press / McGraw-Hill. </ref> are worst-case for binary and binomial heaps and amortized complexity for Fibonacci heap. O(f) gives asymptotic upper bound and Θ(f) is asymptotically tight bound (see Wikipedia:Big O notation). Function names assume a min-heap.
| Operation | Binary | Binomial | Fibonacci |
|---|---|---|---|
| createHeap | Θ(1) | Θ(1) | Θ(1) |
| findMin | Θ(1) | O(lg n) or Θ(1) | Θ(1) |
| deleteMin | Θ(lg n) | Θ(lg n) | O(lg n) |
| insert | Θ(lg n) | O(lg n) | Θ(1) |
| decreaseKey | Θ(lg n) | Θ(lg n) | Θ(1) |
| merge | Θ(n) | O(lg n) | Θ(1) |
- Wikipedia:Data_Structures general overview. Good entry point for trees: Wikipedia:Binary_tree
- NIST Directory of Data Structures has a very extensive overview
- succinct datastructures (trees)
- succinct datastructures overview
- Tries
- sparse matrices
- look at kazlib from IS-IS ??
