Haskellのコンパイルを爆速化！生物学から学んだ意外な最適化手法

この記事では、生物学のアルゴリズムをHaskellのコンパイラに応用することで、コンパイル時間を劇的に短縮するテクニックについて解説します。自然界の知恵をプログラミングの世界に持ち込むという、非常に興味深く実用的なアプローチです。

「最長チェーン境界とエクストリームカットのショートカットを適用することで、GHCの最適パスにおけるコンパイル時間の崖を効果的に解消できる。そして、残存する高密度な最悪ケースは、皮肉にも自然界の計算メカニズムを深く反映している。」

つまり、これって実際にGHCに実装できるってこと？まだ一度しか読んでなくて4分の1も理解できてないけど、結論の直前のセクションを読む限り、頑張っても巨大な定数を伴うO(n^2.82)が限界ってことみたいじゃない？

こういう依存関係の連鎖って、ざっと読んだ感じだとTarjanの強連結成分分解アルゴリズムみたいな深さ優先探索で扱えそうに見えるね。データベースのテーブルにある外部依存関係の解析や、makefiles/rakefilesでのタスクの依存関係解析なんかでよく使ってるよ。

面接で少しでも関連した質問をされると、TarjanやDijkstraみたいなシンプルなアルゴリズムと、より現代的で高速だけど概念的に難しいアルゴリズムのトレードオフについて深く語れるから楽しいよね。

これモノトーンmin-plusだから、挙げた計算量（単なるmin-plus）よりもさらに速くできるよ。
あと、数値が最大でもk以下なら、計算量をkに関連付けることもできるね。nをkに置き換えるのが可能なのはもちろん、それ以上の最適化もできるはず。実際にはkが小さいケースが多いだろうから、かなり現実的じゃないかな？