n-heap とは、1つのノードに対して n 個のノードを子に持つデータ構造である。n が増えることで比較回数が多くなってしまうが、swap 回数が減ることになるので、heap を配列で実装している場合は有効ではないかと考えた。
意外にも n = 2 のときが最も実行時間が短かった。n = 2 のときはもちろん通常のヒープになる。今回の実装では、容易に n を変更できるように実装していたのだが、こういった結果を得られた。
結局、通常のヒープ法が一番良いようだ。
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)
■unsigned int
n = 2 44.1[sec]
n = 4 41.0[sec]
n = 8 44.1[sec]
■unsigned long long
n = 2 42.5[sec]
n = 4 48.4[sec]
n = 8 46.8[sec]
n = 10 48.2[sec]
n = 12 53.9[sec]
意外にも n = 2 のときが最も実行時間が短かった。n = 2 のときはもちろん通常のヒープになる。今回の実装では、容易に n を変更できるように実装していたのだが、こういった結果を得られた。
結局、通常のヒープ法が一番良いようだ。
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)
■unsigned int
n = 2 44.1[sec]
n = 4 41.0[sec]
n = 8 44.1[sec]
■unsigned long long
n = 2 42.5[sec]
n = 4 48.4[sec]
n = 8 46.8[sec]
n = 10 48.2[sec]
n = 12 53.9[sec]