Heap VS MLB。

ヒープ法(Binary Heap)と、マルチレベルバケット法(Multi-Level-Bucket) の実行時間の差がなくなってきたという記事は書いたが、DIMACS 9th で公開されている USA-road-d.XXX.gr というグラフに関して実行時間を計測した。

実行環境は以下の通り。
CPU : Xeon X5460 3.16GHz (L2 6MB)
Mem : 48GB

これだけ競っていて、要求メモリが半分以下というのは大きいことだといえるだろう。しかしながら、アルゴリズムが異なり、実装方法も全くと言ってよいほど違う（MLB はポインタ多用、メモリ要求量大）２つの実装がこれほどまで似ている特性を持っているのは、不思議なことである。