Gerth S. Brodal and Gabriel Moruz Proc. ESA 2006, pp. 708-719 doi:10.1007/11841036_63 今日の勉強会で紹介したら好評だったので,ここでも紹介. 二分探索木は左側と右側がバランスするように構成すると探索時間が短くなる,と思ったら,実はそうでもなかった,という話. ある程度アンバランスにした方が探索時間が実際短くなり,その理由として,左部分木をたどるコストと右部分木をたどるコストが違うというモデルを提案している.コストが異なるようになる理由は分岐予測ミスやキャッシュミス,命令数の違いというものが挙げられている. 言われてみれば当たり前のような気もするが,言われなければ全然気づかないことで,とても面白いと感じた.
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く