COIN-OR::LEMON - Graph Library

Ticket #313: heap_benchmark_results.txt

File heap_benchmark_results.txt, 2.0 KB (added by Peter Kovacs, 11 years ago)
Line 
1Running time tests of Dijkstra algorithm on DIMACS USA road graphs:
2
3                   USA-East    USA-West  USA-Center      USA
4n =              3,598,623   6,262,104  14,081,816  23,947,347
5m =              8,778,114  15,248,146  34,292,496  58,333,344
6
7BinHeap
8   real time:      1.37882s    2.76038s    9.2069s     13.8576s
9   # decrease:      255,968     453,036   1,009,707   1,721,827
10
11Relative running times using different heaps:
12
13BinHeap            1           1           1           1
14FouraryHeap        1.0125      1.00388     0.95992     0.99249
15KaryHeap, K=4      1.06953     1.05834     1.00351     1.05584
16KaryHeap, K=8      1.10841     1.09064     1.0091      1.07601
17KaryHeap, K=16     1.21442     1.1885      1.07335     1.14117
18FibHeap            2.60177     2.49706     2.00734     2.28037
19PairingHeap        4.32173     4.21006     3.18253     3.61469
20RadixHeap          1.29437     1.25158     1.11141     1.15881
21BucketHeap         1.02371     1.0223      0.87654     0.87517
22
23
24
25Running time tests of Dijkstra algorithm on "worst case graphs"
26(for which a decrease() should be called for almost all arcs):
27
28
29n =                  1,000       10,000       20,000
30m =                499,500   49,995,000  199,990,000
31
32BinHeap
33   real time:      0.02595s     2.96707s      9.2069s
34   # decrease:      498,501   49,985,001  199,970,001
35
36Relative running times using different heaps:
37
38BinHeap           1            1            1
39FouraryHeap       0.586849     0.598493     0.586294
40KaryHeap, K=4     0.617215     0.623449     0.60979
41KaryHeap, K=8     0.538696     0.511745     0.496764
42KaryHeap, K=16    0.500899     0.465654     0.450195
43KaryHeap, K=32    0.474184     0.448789     0.425124
44KaryHeap, K=64    0.503833     0.452305     0.433415
45KaryHeap, K=128   0.477954     0.415909     0.393518
46FibHeap           1.09494      0.999109     0.948152
47PairingHeap       0.911916     0.827428     0.771995
48RadixHeap         0.377262     0.347746     0.327151
49BucketHeap        0.866452     0.788165     0.777849