人生にもアルゴリズムって大事だよ、きっと

エンジニアになって日も浅いので、院生の頃の話を書いてみる。

付き合っていた彼女の研究がショウジョウバエの胚発生のシミュレーション。
モンテカルロ法のようなアルゴリズムで物質の拡散をシミュレーションし、ハエの胚が分化していく初期段階を解いていた。

しかし、遅い。

一番クリティカルな反応をシミュレーションする部分が遅く、一回の計算で一ヶ月以上かかる状況だった。
パラメータを色々と変えて何回も何回もシミュレーションしなければならないため、これでは研究自体が不可能だ。
一体どんな処理に時間がかかっていたのか？

このシミュレーションでは、反応する分子を乱数で選ぶ。
まずは、乱数を一つ作る。ここではモンテカルロの定番のMTを使っていた。
分子の反応しやすさの配列があり、前から順番に足していき、与えられた乱数を超えたところの分子を反応させる。そして、反応後に反応しやすさの値を変更し同じ事をくりかえす。

これは、たくさん分子があると反応しやすく、少ないと反応しにくいという化学反応の性質を実装したシミュレーションアルゴリズムで、ギレスピーアルゴリズムという。

最初の実装では、これを素直に実装していた。
つまり毎回足しながら比較を分子の数分繰り返していたのだ。
彼女から相談された時、プログラムの構造をなるべく維持しながら、計算と分岐をなるべく少なくしようとしてグループに分割してみた。
しかし、よくシミュレーションの仕組みを考えていくと、もっと根本的に変えられる事がわかった。

懸命な読者エンジニア諸氏にはもうお分かりだろう。

反応しやすさの配列をツリー構造にしてみたのだ。
このときは単純な二分木を使った。
そして、二つの子の「反応しやすさ値」を合計した物を親が持つようにした。
これで、ルートから2つの値と乱数を比較しながら辿っていくだけで、反応分子を検索することができる。
さらに、反応後に「反応しやすさ値」が変わった場合も、そのリーフからルートまで差分を足しつつツリーを辿るだけで、最新の「反応しやすさ値」が反映される。

これで計算時間が一日になった。

彼女の研究室の莫大なコンピューティングパワーをもってすれば、十分実用に耐えるスピードだ。
めでたく研究は論文になり、その分野で大きな評価を得、ジャーナルの表紙にもなった。(電子版だけど)
ついでながら、この部分のコードを書いたのと、シミュレーション結果の3D表示プログラムを作った功績で僕の名前を論文著者の一番下っぱのところにいれてくれた。

そして、ケーキカットよりも先に大いなる共同作業を成し遂げた彼女とは1年前に結婚し、今もお互いの仕事の技術的なことを相談したり、よいパートナーシップを築いている。