博士

ロボ子、今日のITニュースは数独ソルバーの最適化の話じゃ。

ロボ子

数独ですか、面白そうですね！ どのような内容なのでしょうか？

博士

Olivier氏がZigで書いた数独ソルバーを、これでもかと最適化した記録らしいぞ。アルゴリズムはDancing Links (DLX)というのを使うらしい。

ロボ子

Dancing Linksですか。初めて聞きました。

博士

数独をexact-cover問題に変換して、0と1の行列で表現するのじゃ。行列の列が制約、行が部分的な解を表すらしい。

ロボ子

なるほど。数独のセルに数字を割り当てるのが、制約を満たすことに相当するんですね。

博士

そうそう。初期実装では、各セルに対して`allocator.create()`を呼んでて、平均1msで解けてたらしい。

ロボ子

1msですか。十分速い気もしますが、最適化の余地があるんですね。

博士

そこからがすごいんじゃ。まず、1行の4つのセルを一度に割り当てることで、0.54msに短縮！

ロボ子

一気に半分近くまで速くなったんですね！

博士

さらに、すべてのセルを一度に割り当てると0.46ms、ArrayListのサイズを事前割り当てすると0.30msじゃ。

ロボ子

事前割り当ては効果的なんですね。

博士

`Doptimize=ReleaseFast`フラグを使うと、なんと0.13ms！

ロボ子

コンパイラ最適化も重要ですね。

博士

DLX構造体を「unmanaged」で使って、ヒープを使わずスタックのみを使うようにしたり、最初から入ってる数字を考慮して不要なセルのセットアップをスキップしたり…

ロボ子

細かいチューニングも積み重ねているんですね。

博士

最終的には、Zig 0.14.1にアップグレードしたら、平均0.061ms/puzzleになったらしいぞ！

ロボ子

すごい！ 初期の1msから考えると、16倍以上速くなっているんですね。

博士

しかも、マルチスレッドで20スレッド使うと、1秒あたり約138kパズルも解けるらしい。

ロボ子

それは驚異的なスピードですね。数独ソルバーでそんなに最適化できるとは思いませんでした。

博士

じゃろ？最適化って奥が深いんじゃ。私も見習わないとな。

ロボ子

そうですね。私も勉強になりました。ところで博士、数独は得意ですか？

博士

私にかかれば、数独なんて一瞬…って、あれ？鉛筆がない！

ロボ子

（苦笑）まずは鉛筆を見つけるところからですね。