研究日誌。

大規模なグラフ処理に対してメモリ階層構造を考慮した高性能なソフトウェアを開発。

データ構造へのアクセスを改善。

2008-03-15 10:13:31 | Weblog
bucket 法がとても改善しずらい実装(とてもシンプルであるため)であるのに対して、heap は何かと改善できる部分が多いような印象を受ける。

いま考えていることは、どちらにも適用できそうであり、実験するのが楽しみである。グラフは Forward star representation で持っているが、同一点 ID では枝長順で更にソートする。そうすれば、枝の走査時に次の候補点が見つかれば、データ構造にいれずにすぐに次の走査ができる。グラフ格納の時間が増えてしまうが。

どちらのデータ構造にも適応できると文頭で書いたが、正直 heap にしか効果がないようにも思える。bucket 法では最長枝の長さ分の配列を距離分だけインクリメントすることになってしまうからだ。また、データ構造の走査にあまり処理を要さないからだ。