Data Structures and Algorithms: Unterschied zwischen den Versionen
Aus FunkFeuer Wiki
Hannes (Diskussion | Beiträge) (first cut for data Structures) |
Hannes (Diskussion | Beiträge) |
||
| (3 dazwischenliegende Versionen von einem Benutzer werden nicht angezeigt) | |||
| Zeile 1: | Zeile 1: | ||
= Heaps = | = Heaps = | ||
| − | + | [[Wikipedia:Heap (data_structure)|Heap]] ... We need good heaps/priority queues for Dijkstra path exploration (relax function) | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
The following complexities<ref> | The following complexities<ref> | ||
| Zeile 88: | Zeile 45: | ||
|| Θ(1) | || Θ(1) | ||
|} | |} | ||
| + | |||
| + | |||
| + | |||
| + | 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'''... | ||
| + | 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 == | ||
| + | |||
| + | <pre> | ||
| + | --- 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, | ||
| + | </pre> | ||
| + | |||
| + | == AVL heap == | ||
| + | |||
| + | <pre> | ||
| + | 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> | ||
== other interesting data structures not directly related == | == other interesting data structures not directly related == | ||
Aktuelle Version vom 24. November 2007, 15:18 Uhr
Inhaltsverzeichnis
Heaps
Heap ... We need good heaps/priority queues for Dijkstra path exploration (relax function)
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) |
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,
- 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 ??
