距離変数を unsigned long long 型に その２。

以下のようなものについて実験を行った。
USA-road-d.USA.gr　23947347 nodes 58333344 arcs / length range(1, 368855)
USA-road-d.LKS.gr　2758119 nodes 6885658 arcs / length range(1 - 138911)
USA-road-d.NY.gr 　264346 nodes 733846 arcs / length range(1 - 36946)


やはり mbpC.exe(goldberg) はメモリ使用量が多い。また、距離しか求めていないようで、距離のみにしてしまえば上記のような構造体の問題もなくなるが、Web サービスを考えると外せない。コンパイル時に ON/OFF はできるようにしてあるので、こちらも必要なときだけ演算するようにしたい。

以下は、全米データについてである。

Graph : USA-road-d.USA.gr
Query : USA10.p2p
　(957498, 10453327)
　(19200797, 7727679)
　(13006257, 40639)
　(4314559, 22779984
　(17261435, 8424294)
　(8077810, 13186938)
　(3048748, 1475829)
　(21869636, 3531883)
　(13446936, 4981527)
　(18549540, 3230879)



データ構造　(距離配列のデータ型)　要求されるメモリ量

bucket (unsigned int) 903.2MB
　22.37[sec]
bucket (unsigned long long int) 1085.9MB
　27.73[sec]

heap (unsigned int) 993.2MB
　35.71[sec]
heap (unsigned long long int) 1358.6MB
　40.89[sec]

mbpC.exe　(unsgined long int) 2796.8MB
　35.73[sec]



図は、USA-road-d.USA.gr 以外にも、USA-road-d.LKS.gr、USA-road-d.NY.gr について、それぞれを実行した結果である。ちょうど点数が 10 倍ずつになっているものを選んだ。mbpC.exe を基準にどれほどの実行時間であるか[%]を示している。