Heap と MLB。

Goldberg 氏によるテスト問題集についても、自作ソルバーとの比較を行っている。

やはり Multi-Level-Bucket は、枝長のばらつきに強い。というのも、「ポテンシャル値を 2^n により挿入するバケットを選択する」という部分がかなり効いていると言える。

それに比べ Heap は、常に少メモリで安定した実行時間である。こちらのほうが実行時間の見積もりが立てやすい。


また、２プロセス同時に実行した際に、１プロセスでの結果との差（％）を比べてみた。特に L2 キャッシュを共有した際の性能低下が大きい。

やはり並列での実行を考えるなら、Heap がよいだろう。