PEP 703

https://peps.python.org/pep-0703/

Python の GIL 外す話。これすごく楽しい読みものでした。参照カウントのところが一番人気だと思うのですが、他のところも色々良い。こういう、「んーこういうことするとこういう問題が起きない？」と思ったら次の章くらいでそれが説明される、みたいな読みものは大変好きです

• 参照カウント: オブジェクトっていうのは作ったスレッドが解放するというのがほとんどなんだから、その場合はロックをいらなくする、他に渡ったら普通の参照カウントぽくする、という話。 Swift に 2018 年に導入された 話らしい。他のスレッドに渡された後で DECREF すると他スレッド用の参照カウントが負になりうるのだけど、その時に queue に入れるということをして、ややこしいので、なんかこれ無しですむ方法はないのかなぁ……と
• Immortalize と Deferred reference count: ずっと解放されないオブジェクトは不死にして contention を避ける。ほとんどの場合 cyclic になることが知られているオブジェクト(トップレベルのモジュールや関数など)も、 refcount やめて GC 任せにすることによって contention を避ける
• mimalloc: pymalloc は GIL 前提でスレッドセーフにするの面倒なので、 mimalloc に変更。 mimalloc の内部状態を見ることで、 python が自力管理してた object のリストとかの管理はいらなくなった。後で他のメリットも出てくる
• GC: Stop the world する。途中でデストラクタとか呼ぶとデッドロックしうるので後でやる、とか、まぁそうよね的な。 concurrent は writer barrier 入れられないから諦め。 generational は refcount あるしいらないもん！という感じで撤去、らしい
• コンテナ: GIL 任せにしてたところをオブジェクト単位のロックにする。 list_a.extend(list.b) みたいな、複数のオブジェクトがあるとロック順序問題にならない？と思ったら、二つの mutex を受けて、 mutex のアドレス順でロックする、て関数をみんなが呼べば大丈夫、という話らしい。すごく単純だし、他でもよくあるのだろうけど、なるほどというアイデア
• 楽観ロック: list と dict は大事なので、 getter は楽観ロックで高速化する。値取り出した後、もう一回変わってないかチェックするようなやつ。 rwlock は遅いから RCU にせよとかいうおきまりの話
• 楽観ロックのための mimalloc 改変1: python オブジェクトは専用のプールを使う。それによって、オブジェクト取った後に仮に他スレッドによって解放されたとしても、 refcount は refcount のまま。なぜなら PyObject の先頭の方のレイアウトは共通だから (実際は二種類あるらしい)
• 楽観ロックのための mimalloc 改変2: とはいえ munmap されたり、他のサイズ用のプールとして再利用されてしまうと困る。次の GC まで munmap しない、が安全だがメモリ使用量が増える。ので、ほど良い sync 頻度で安全なタイミングを保証する方法を実装する。グローバルな write カウンタと、各スレッドに read カウンタを用意する。空っぽのプールができたら、そのプールの番号を今の write カウンタとし、 write カウンタをインクリメント。各スレッドは楽観ロック中でない時に、時々 write カウンタを観測して自分の read カウンタに入れる。すると、全 read カウンタの最小の値より大きい番号を持つ空プールは捨てて良い、となる

行動遺伝学

社会的に成功した人は、遺伝的に有利だったのか、環境が良かったのか、本人が頑張ったのか、犯罪を犯した人は、先天的になにかあったのか、教育や環境が悪かったのか、よくそういうことが気になります。ときどきその手のことを考えるヒントになりそうな本とかを読んでみたりしてたのですが、友人から教えてもらった本のおかげで、行動遺伝学というジャンルが、この手のトピックに科学的なアプローチで取り組んだりしているぽい、ということを知りました。というわけで、冬休みの自由課題的に色々読んだりしてみたので、なんか色々と書いてみます

結論から書いておくと、最初にあげたような疑問は、行動遺伝学を学ぶことによって完全に解決する、ということはなさそうです。ですが、いろいろわかっていることもある、考えるヒントになる、というあたりが収穫かな、と思っています

読んだもの

• Introduction to Human Behavioral Genetics (https://www.coursera.org/learn/behavioralgenetics): Coursera です。 Coursera は新しいこと学ぶには最強ですねコレという感じです。今まで見た Coursera は全部そうだったのですが、さすが動画にして配信しようというだけあってか、すごく洗練された講義という感じで、わかりやすいし楽しいし、非常に良かった。余談ですが僕は Coursera で機械学習の講義やっただけで AI 人材をよそおっています
• 心はどのように遺伝するか (https://www.amazon.co.jp/gp/product/B00GHHYDIU/): 専門の先生が人間行動遺伝学についてわかりやすく書いた本で、 Coursera を除けば一番良かったものでした。科学的主張にちょっと著者の思いが混じっている？という感覚を受けたところがありました
• なぜヒトは学ぶのか　教育を生物学的に考える (https://www.amazon.co.jp/gp/product/B07H7HXV91/): ↑と同じ先生がもう少し新書ぽく、学習に集中して書いた、という感じかと思います。こっちはより思いが乗っていたような印象を持っています
• 言ってはいけない―残酷すぎる真実― (https://www.amazon.co.jp/gp/product/B01E6JQBD0/): 行動遺伝学の知見をセンセーショナルに書いた新書という感じ。ここまでで「思いが乗っている」みたいなことを気にしていた理由がこの本なのですが、出ている結果に対して著者が解釈を与えている量が多すぎるように思いました。 X という結果が出た時に、 A とも B とも解釈できる時に、 A だと断じて論じるような感じというか。あるいは新書によくある、衝撃的な一例を紹介して、そのサンプルを一般化するとかですね。科学的に真摯になると、どうしても歯に衣着せた書きかたになる傾向があり、この本はそれが無いので、痛快な解説になっていて、読み物としてウケそうな感じだなーと思います
• 行動遺伝学入門―動物とヒトの“こころ”の科学 (https://www.amazon.co.jp/gp/product/4785358475/): 他と違って、人間以外の行動遺伝学についてが7割くらい。線虫とかマウスとかは倫理的な制約がゆるく、遺伝子ノックアウトして大量に生めよ増やせよ高速イテレーション、とかのワザが使えて便利そうだなと。哺乳類とかに対しても行動遺伝学研究があるらしいのだけど、これは便利でもなく、人間行動遺伝学のように実用的でもないので、研究も少ないらしい。まぁそうかという

おおむね Coursera の講義で面白かったことについて書くことになると思います

行動遺伝学とは。その歴史

遺伝学的なアプローチを使って行なう、心理学の一分野、らしいです。現代的な形になるまでにちょっと暗黒の時代があります

進化論のダーウィンのいとこであるところのゴルトンという人が優生学を始めたところに端を発します。優生学は「なんかナチス……」とかいうイメージですが、当時は世界的な流行だったとのこと。その没落はよく知られている通り。ユージーンという名前は優生学 (eugenics) の没落と同時期に減っている、とかいうグラフが面白かったです

Eugene という名の子の人数

その後、優生学ブームの反省から、今度は逆の方の極端に倒れ、環境で全てが決まると主張するのが人道的であり、それを肯定することが科学的にも正しい、という雰囲気が作られました。行くところまで行ったケースとして紹介されているのが John Joan case というやつ

ある双子、生まれた時に割礼手術をして、片方で失敗して男性器がダメになってしまいました。悲しむ親。そこにアドバイスする「環境が全て」論者の権威であった医者。いわく「手術して女性化するので、 Joan (女性名)として育てなさい。この件に関して本人には伝えてはいけない。大丈夫、人間は環境が全てなので性も変えられる」この教えに忠実に育てた両親。権威の医者は大成功と論文を書きます。ですが、本人は自殺願望持つ程度に違和感を感じ(今の感覚で考えると要するに性同一性障害ということかなと理解)、両親は秘密を明かし、本人は再度男性になる手術を受けます。いろいろあって、関連は定かではないですが(あるに決まってるという気もしますが)、元 Joan さんは自殺してしまっています

John/Joan は研究紹介に使われた仮名で、本名の Wikipedia エントリーがあります(なんか Coursera で紹介された話よりずいぶんエグい): https://en.wikipedia.org/wiki/David_Reimer

ずいぶんと野蛮な話に感じましたが、 1965 年とかで、比較的最近なんだなぁと

遺伝子で全てが決まる、選別しよう、は倫理的にもヤバいし、科学的にも正しくなかったが、環境だけで決まる、というのも科学的に正しくない。イデオロギー先行で科学をやっちゃいけない、というよくある教訓がここにも、という感じです

その後、タブーぽくなっていた遺伝に関する研究が許される雰囲気になります。行動遺伝学の方法で繰り返し確認されることは「たいていのことに関して、程度の差はあるが遺伝も環境もどっちも大事ぽい」ということ。非常に直感的というか、まぁ「それはそうだろう」という感じではあります。ただ、世間的には「優生学ダメ絶対」が強いドグマとして存在するので、例えば「IQ には遺伝の影響がある」と言うと攻撃される、みたいなのがあってツライ、という感じらしいです。そのツラみへの反論は紹介した和書にしつこいくらいたくさん書かれていました

双子法などの方法論

線虫とかであれば「遺伝子を欠損させて様子を見る」とかが許されるのですが、人間に対しては「良い教育を受けた群と悪い教育を受けた群を作る」とかですら人権問題です。というわけで自然とできた差を有効利用するしか無いのですが、そこで最も役に立っているのが双子のようです

一卵性双生児は、遺伝子的には完全に同一なので、一卵性双生児の間で差がある場合、それは全て環境起因であるということが言えます。そういう感じで「人の差が何起因か？」をモデル化したものとして、 Falconer model というものがあり、差を作る要因を、遺伝率 (A) 、共有環境 (C) 、非共有環境 (E) の3つに分解します。「人の差が出る要因は遺伝か環境である」は真だろうし、「環境は兄弟などで共有される環境と、友達関係など共有されない環境がにわけられる」と言われても、まぁそうねと思います

この A と C と E が完全に同一なら相関係数は 1 になるだろうということで、 A + C + E = 1.0 と考えます。これを使うと色々な方法で連立方程式が作れるという話になります。例えば一卵性双生児をたくさん見て、身長の相関係数が 0.92 であったとすると

0.92 = A + C

なので E = 0.08 となります。一卵性双生児は遺伝子が完全に同一で、共有環境もその定義から一致しているので、残りは非共有環境 E の影響であろう、と

次に二卵性双生児では身長の相関が 0.56 であった場合、二卵性双生児は遺伝子を半分共有しているので

0.56 = 0.5 * A + C

連立方程式を解くと A = 0.72 と C = 0.20 、となります

この論理、理解 & 納得できましたでしょうか。僕はまるで納得できず

1. そもそも相関係数て足したり引いたり処理できるもの？
2. 二卵性双生児の遺伝率の影響て厳密に 0.5 で良いの？
3. これ簡単に A が 1 越えたり C が負になるけど大丈夫？

などの疑問がずっと残り続けました。式を追ったりしていないので、完全に理解はしていないのですが、ある程度は納得したつもりです。 1 については分散を評価してるので OK という話で、 2 は遺伝要因の種類に依存するが 0.5 で良い特性が多い、らしい、 3 は実際論文の実験結果とか見ると、素直に計算すると C が 負になるようなデータが結構あるのですよねえ。その場合 C を 0 にクリップしてるように見えるけど、その特性に対してはモデルを見直すべきなのではという気も。共分散構造分析とかを勉強すると腑に落ちるのでしょうか。謎

この図の >85 years woman とか、素直に解くと A=1.28 C=-0.64 E=0.36 となるのですよね……

60 より早く死んだ人は事故とかだろうから、遺伝影響がない、という説明はわかりやすいのだけど

3つの値の解釈

この3つ、遺伝率と共有環境と非共有環境、語感と実態が割と違うので注意が必要、ということは、読んだもの全てで言及されていました

まず遺伝率 vs 環境ですが、例えば身長の遺伝率 90% というと、「親が高身長なら 90% の確率で子も高身長」のように感じますが、定義からも明らかなように、そういうい扱いができる数字ではないです。あくまで「人の個人差、統計的には分散を作る要因のうち遺伝子起因の割合」という、なんだかよくわからない数字です。その数字を言われたからといって即座に結論を導くことは難しい、その後の考察が必要な数字と理解しています

また、語感に反して、遺伝率は生物学的な数字というよりは、社会学的な数字と考えた方が良さそうで、人類全体や人種に対して不変なものではなく、社会環境に依存します。例えば身長の遺伝率は数十年のスパンで増加しているそうです。もちろん遺伝子が強力になってその影響力がガンガン増えている、というわけはなく、社会が豊かになり十分な栄養を取れない人が減り、環境がそろったから相対的に遺伝率が高くなっていく、という話です

平均身長は年々増えている

共有環境と非共有環境の分離も注意が必要です。共有環境は、直感的な説明は「家庭環境」ですが、親が双子の子供に対して違う扱いをしていたら、非共有環境の方にカウントされるのが注意が必要なところです

行動遺伝学3つの法則

以上を踏まえて、色んな調査をして、いろいろな特性に対して、3つの値を求めていきます。特性というのは、身長、 IQ 、統合失調症、学校での成績、社会的な成功、宗教性、犯罪性向、などなど、多岐に渡ります

色々とやった結果、3つの法則に合意が取れているようです。さっき紹介した双子法は行動遺伝学の方法で最も強力なものですが、例えば養子を使うと共有環境の影響の推定ができる、など、他の方法でも consistent に確認されている法則である、とのことです。いわく

1. 人間には行動特性のは遺伝の影響がある
2. 共有環境の影響は小さい
3. 非共有環境の影響は大きい

1 は「人間は環境によってなにものにもなれる」主義者でなければ、まぁ受けいれらるものかなと思います。まぁ僕はたぶんアメリカ大統領にはなれない。 3 も常識的な話で、遺伝と環境、どちらもだいじ、という話です

2 について、 IQ 、反社会性、宗教性などの、一部の特性を除けば、おおむね共有環境の影響の影響はゼロか非常に少ない、という結果が出ることが多いようです。これは共有環境を家庭環境と考えると、かなり直感に反する話だと思います。これの解釈としては、単に「家族の子への影響は小さい」と考えることもできますが、「家族の影響は子によって違う働きかたをする」と考えることもできます

Coursera では「例えば離婚は、子の個性、性別や年齢に応じて、違った形で影響を与えるのかもしれない。そうだとすると、その影響は非共有環境に分類される」などと述べられています。行動遺伝学の行なっている実験では、この分別に関して結論は出せないと思っています。ので、ここからは科学的方法を離れて、各人が好きな解釈を考えれば良い領域だと思います。個人的には、「家族の影響が全くないとするのはさすがに不自然で、ボリュームゾーンの家庭はたぶん似通っていて大きな分散を形成しないという点と、指摘されている子が違った反応をするという理由の2点で、小さい数字が出るのでは」くらいに思っています

A=遺伝率 C=共有環境 E=非共有環境 緑の領域はおおむね狭い

遺伝子と環境の相互作用

遺伝子と環境は相互作用することが知られています。例えば、社会的経済的に有利な家庭と、社会的経済的に不利な家庭を何段階かに分類した上で、 IQ の遺伝率を調べる、みたいな研究があります。これでわかったことは、「社会的経済的に有利な家庭では、遺伝率が高くなる」ということだそうです

SES は socio economic status らしいです

これは高い能力を持ちうる遺伝子は、良い環境でこそ発揮されがちで、社会的経済的に不利な家庭では、高い能力を持ちうる遺伝子がムダになることもある、ということもあると。あともう一つ、頭が悪い遺伝子持ってると良い環境でも頭良くなりにくいということで……これはなかなか discouraging な結果ではあります。希望を持てる解釈のしかたとしては、「自分が得意なことを見極めてそれに取り組めば、才能を発揮できる可能性が高い」とも言えそう、というのがあるかな、と思います

一般的に悪いとされている特性についても、遺伝子と環境の相互作用があります。例えば MAOA という遺伝子が欠損していると、犯罪を犯す率が有意に高くなるそうですが、幼少期に虐待を受けていない群では特に犯罪性向が増えない、というようなことがあるらしいです

この相互作用のポジティブな使いかたとして、特定の病気になりやすい遺伝子を持っているとわかれば、その対策がうてる、ということがあります。行動遺伝学の本などによく出てくる例として、フェニルケトン尿症という病気があり、この原因遺伝子を持ってる人は、ほっておくと脳障害を発症しまいます。ですが、フェニルアラニンの摂取を食事制限でコントロールすることによって、発症を止められる、なんてのがあります。こういう話を聞くと自分も全ゲノム解析やってみたくなります

ところで、相互作用の話を考えると、 Falconer model というのは適切なのだろうか……という気持ちになります。 Falconer model のように遺伝率と環境を足し算で考えるのは輻輳説と言われ、しばしば相互作用説に攻撃されるが、輻輳説で良いのである、的なことが本には書いてあります。個々の人間で足し算は不適切だけど、集団の分散を考える場合は OK 、という話だと理解しているのですが……このあたりは統計知識不足のせいか、あまり腑に落ちていないです

行動遺伝学4つめの法則

Coursera では、「一般的な3つの法則に加えて、私としてはもう一つ追加したい」ということで、4つめの法則が提案されていました。 "Human behavioral traits are polygenic." つまり「人間の行動特性は複数の遺伝子に依存する」というものです

これはまぁ普通に考えてそうでしょう。行動特性というのは普通、複雑なものなので、この遺伝子があると高 IQ 、とか、この遺伝子があると統合失調症になる、とか、そういう単純なものではない、と。逆に単純に一箇所で原因が特定できる遺伝子もあり、少し前であげたフェニルケトン尿症なんかは、遺伝子を一箇所見ればわかるものらしいです。メンデルが豆の色とかで研究していたのは、この手の polygenic でない遺伝子ですね。がまぁ、そういうのは例外で、ほとんどの行動特性は、複数の、非常に多くの遺伝子に依存している、という話です

例えば統合失調症では、 1990 年代から15年かけて行なわれた、大規模実験があります。これは 2000 人の統合失調症患者と、 2000 人の対照群に対して、 648 箇所の遺伝子を調べた、というものです。この実験では 15 年もがんばってやったにも関わらず、「この中に有意に統合失調症と関係があると言えるものはない」という悲しい結論となって終わりました

このような結果になった理由として考えられているものは、「統合失調症の強い原因遺伝子なんてものはなく、非常にたくさん、少なくとも1000を越える原因遺伝子があり、それら一つ一つの影響は非常に小さいので、 2000 人くらいのサンプルでは有意なことは言えない」というものです

その後、ゲノム解析はすごい勢いで進化していき、ゲノムのほぼ全域をカバーできる GWAS という手法が確立し、またサンプル数を患者2万以上、対照群4万近く、という規模に増やして始めて、 22 の遺伝子が有意である、という結論が 2013 年に出た、という感じらしいです

2013 年の結果に対するマンハッタンプロット

このグラフはマンハッタンプロットと言うらしいのですが、横軸は遺伝子の場所で、縦軸は、縦軸は P 値に対して log_10(p) です。 7 くらいのところに赤い横線がありますが、 10M くらいの箇所を調べているので、 P 値が 10^-7 より小さくならないと、統計的に有意である、とはいえない感じです。つまりこの赤い線を越えたところにあるいくつかの点が、有意に統合失調症への影響がありそう、とされた 22 の遺伝子らしいです (なんか20個も赤線越えてる点無いように見える気もするけど)

感想

この手の話題、個人の信条の問題だと思ってたので、こういうことを統計的に分析する、ということ自体を楽しく思いました。おおむね直感的に真と感じるようなことを裏打ちするような形で、割といろんなことがわかっているのだなぁ、と

最近は遺伝学側の進化により、社会学的な雰囲気より生物学的な側面が大きくなってるのも面白ポイントに思いました。特に遺伝子情報の医療利用など、夢があって良いなと

あと、このあたりの話は、簡単に科学的な知見がイデオロギーに歪められうる、というのも面白いところだな、と。これは色んな科学分野であるあるでしょうけど……そういえば、行動遺伝学と似たような興味から、 犯罪学という本を読んでいたことがあったのですが、古い時代だと「犯罪をするやつは脳が小さい」みたいな珍説が色々出てきて楽しかったです。ちなみにその説を提案した学者は脳が小さかった、というオチつきです

開発イテレーション偏重

開発イテレーションを早くすれば、かなりの問題が勝手に解決される、と信じています。なんか最近、他の要素を軽視しすぎていたり、特にイテレーション速度に影響しなさそうなことすらしている気がしていて、信仰とかのレベルかもしれない、という気がしてきたので、ちょっと書いてみようかなと。主に C++ の話です。

仕事とかしてると良い判断力が求められたりしますが、判断というのは結構難しいですよね。アプローチ A と B で悩んだ時に、手が速ければ両方できたりします。開発イテレーションを無限に速くすると、必要とされる判断力はゼロに漸近していきます。やったね。

2手で変更の正当性を高速に確認できるようにする

make (かその他のビルドコマンド)てやったらビルドができて、 make check (かその他のテストスクリプト)てやったら遅くないテストが全部走る、という体勢が好きです。試すためにはあっちのディレクトリで make してこっちで build.sh を走らせて、それで bin/test foobar とかするとできる……みたいなのはとても良くない。単純に新しくチームに入る人とかにとっても厳しいですしね……

そのためには(正直どうかと思うけど)テストの網羅性を捨てて良いとさえ考えてます。まあ理想的には CI では網羅的なテストが走るけど、手元でイテレーション回す時のテストはそのサブセット、みたいなのが良いのでしょう。 CI といえば CI の時間ちょっと削るとかも好きで、好きなんだけどその時間たぶん本来の作業に回した方が良いケースも多いと思うので、信仰だなあと思うゆえんでもあります。

イテレーションを高速化するためならどんな努力でもするので、ちゃんと複数プロセッサ使って並列にテストが走る仕組みを整えたりもします。

細かいユニットテストを避ける

ユニットテストをちゃんと書いていても、なんか結局それを使っている main の部分とか、 Python インターフェイス生やしていたらその接続部分にバグが出たりするので、なんか結局 end-to-end で起きる挙動でテストするのが一番確実だと思っています。 Ruby なんかはほとんど (全部だっけ？) のテストが Ruby で書かれてると思うんですが、そんな気持ちです。

なんなら、これもどうかとは思うのですが、細かすぎるユニットテストを書かないようにしています。細かいテスト書いてるとコケた時にその場所の特定がラクになるなどのメリットがあるのですが、テストがコケる確率ってそんなに高くなくて、コケた時にかかる時間の節約に対して、ちゃんとユニットテストを書くコストの方が高いということは結構あるように思う。 Ruby の例のように、 end-to-end のテストの方が、細かいユニットテストを書くより楽なケースは特に。 AST を自分で構築するより、テストしたい AST になってくれるであろうコードを書いた方がラク、という話。

ヘッダを最小化する

ビルド時間を最小化したくて、ヘッダサイズって結構効くという信仰を持っているので、なるべくヘッダを小さくしています。昔はヘッダ書くと最低1つはクラスがあったのだけど、最近は関数2,3個宣言されてるだけ、みたいなことが多い。

信仰なので本当に効いてるのかはわかりませんが、ヘッダオンリーライブラリとか使った時に、その部分だけ明らかにコンパイルが遅かったりするので、世の中の人もっとヘッダをシンプルに、できればヘッダで template 使わない、など気をつけてくれるとなあ……とよく思っています。

あとまあよく言われることですが、過剰な抽象化とかですね。 YAGNI!

やたらチェックする

イテレーションを最速化したいのであって、タイピングを最速化したいのではないので、割とやたら assertion 相当のコードを入れます。例えば

CHECK_LE(0, i);
CHECK_GT(x_.size(), i);
return x_[i];

のようなコードを書きます。 x_.at(i) をすればチェックした上で失敗したら throw してくれるのはもちろん知っているのですが、例外が起きた時に、どこで起きた例外かをバックトレースから特定して、 gdb で i の値がどうなってるか、などをするのが結構手間なので、呼び出し元の行数と、比較している値を表示してくれる、上記の(glog由来の)マクロがお気に入りです。

また、 CHECK_EQ(x, y) << z みたいなことができて、 z は x != y の時だけ評価されて表示されるのですが、この時 operator<< が x, y, z の全てに定義されていないといけないので、めんどくさいけど、積極的に stringify するコードを書くようにしています。

最適化オプションつきで開発

これはケースバイケースで、特に初期の頃はむしろ -O はつけずに作業しますが、テスト時間が増えてくると、基本的に常に最適化オンで作業して、たまに起きる gdb でのデバッグ作業がつらくなるのは我慢する、というスタイルにすることが多いです。上記マクロでそこらじゅうにチェックが入っているはずなので、 gdb が必要な可能性を落としている……はずです。

あと、大きいプロジェクトなら -g も切って、イテレーションを最速化して printf 入れまくった方がデバッグしやすい、とする時もあります。 LLVM で遊んでる時とかはそれが結局一番良いように思いました。

あと、リリースビルドで消える assertion 、という概念が嫌いです。ほぼ 99.9% パフォーマンスに影響しないくせに、副作用のある式の記述が面倒になり、それを解決すると参照されない変数ができることがあって嫌い。 NDEBUG 時だけ起きるコンパイルエラーとかで時間を消費させられるのが嫌い。

なるべく auto を使わない

auto 、書いてる時はラクなんですが、読んでる時にかかるコストが増えるので、損益分岐点は 20 文字くらい、かなあと思っています。 iterator なんかはめんどくさいし文脈から自明なことが多いので、 auto 使う、みたいな気持ちでいます。

auto に限らず、ループ内包や std::transform 、三項演算みたいなやつも、書くのがラクになるかわりに、単なる純朴なループや分岐の方が可読性が高いと感じることが多くて、他の人より使う頻度が低いなあ、とよく感じます。

一方で using namespace はあまり実害が無くてコスパ良いと思っている(特に std はスタイルが違うので無くても明白)のですが、コーディング規約で許されてないので諦めています……

まとめ

なんか他にもある気がするのですが、他と見比べてて、自分のスタイルが違うと感じることが多いところを並べてみました。他の人の工夫とかも気になるところです。

20%ルールについて

20%ルールという仕組みの雑談になって色々考えていたことを思い出しました。

僕はこう、20%ルールがあまり好きじゃない。まず、時間が細切れになって効率が悪い問題というのがある。「20%ルールのおかげでイノベーティブなプロダクトが生まれた」というのは、イノベーティブなアイデアにも関わらず100%の時間をそこに費やすことができなかった、ということなんじゃないか、と思ってしまう。1ヶ月で実現できたはずのアイデアに、単純計算で5ヶ月かかるわけで

ここで、僕の好きじゃないスタイルの20%ルールは、金曜日は20%、他はメインのプロジェクト、というスタイルのやつに限定している

好きなスタイルとして、 http://shinh.hatenablog.com/entry/2016/03/11/142748 に書いた「半年メインプロジェクトに集中してた僕ですが、なんかやってみたいことができました、1ヶ月時間これに集中する時間を下さい、うまくいかなかったら捨てます」てやつ。集中できるのが良いし、1週間に1日スタイルより、失敗した時に捨てやすいというのも良いように思う

次に最初のやつより嫌いなやつとして、自分磨きやおよそ会社に関係ないことに20%を使うやつ。これはなんか、僕から見ると、スプラトゥーンやってるのと区別が全く無い。使わないと損な勢いになって、不公平感さえでかねないように思う。これを認めるのであれば、単純に、福利厚生として週休3日、とする覚悟がほしい

もう一個好きなスタイルとして、言い訳としての20%というか、5%ルールとでもいうか。今直近の仕事では必要ないけど、長期的に見たら役に立ちそうな知識を仕入れるとか、便利スクリプトを整備するとか、 zshrc を充実させるとか、なんか、そういう全然イノベーティブじゃないやつ。会社でこれをやりましょう、みたいなタスクがある時に、そういうことを突然やりたくなる時があって、そういうことに時間を使うのはちょっと気がひけるのだけど、「まあ20%てことで」みたいに適当に言い訳できるのは良い

ここまでは前職の話

今だと、エンジニアが10000人とかいないので、必然として、一人あたりが関わるプロジェクトの数が増える。そうなると、「このプロジェクトは重要だが、1人アロケーションするのですら多い」みたいなプロジェクトが出てくるんだなぁ、ということに気付く。そうなってくると、0.2人をアサインできる、金曜日は20%ルール、という、最初に否定したスタイルの20%すらアリかもしれないなあ……とか思えてくる。ただ、金曜日は○○、というスタイルは僕には効率が悪いように思うので、1週間ごとにどっちかに倒す、みたいなのを試してみることにしてみました。

20%のことだけでもそうだけど、前職で正しいとされていたことが、当たり前のことなんだろうけど、違う規模違う文化の会社で適用してうまくいくとは限らず、もちろん逆もあるなあと思います。色んなことについて、違いに思いを馳せながら、ケースバイケースな感じで最適なありかたはどうなんだろうなぁ……とか考えるのは結構面白いな、と思います。

転職してからやってること

転職してからやってるプロジェクトについて何か書いてみようかと思います。

https://github.com/pfnet-research/chainer-compiler/

公式ぽいブログも書きました。

https://research.preferred.jp/2019/01/chainer%E3%83%A2%E3%83%87%E3%83%AB%E3%81%AE%E3%81%95%E3%82%89%E3%81%AA%E3%82%8B%E9%AB%98%E9%80%9F%E5%8C%96%E3%80%81%E3%83%87%E3%83%97%E3%83%AD%E3%82%A4%E3%81%AE%E7%B0%A1%E4%BE%BF%E5%8C%96%E3%80%81/

あまり綺麗にまとまった文章を書ける気がしないので、つらつらと時系列で思い出して行こうかと思います。

転職前、 define-by-run とかについて考えていたこと

まだ前職にいた時、転職活動中に、 ChainerX の存在や、 Python からコンパイルして実行できると良いなと思っている、みたいな話を聞いたような気がします。これは結構、具体的かつ無茶ぶり感がある話で、まあ楽しそうだなと思ったし転職先を決める理由になったような気もします。

機械学習、どんな計算してるかというとおおむね行列のかけ算ばかりしている、とかよく説明します。とはいえ非線型な要素も必須だし、計算結果をどうつなぐか、みたいなのでなんかうまくいく方法が発見されたり、ブロックの接続をこねくり回してるような感覚があると思います。

で、そういう接続をごにょごにょする機械学習フレームワーク、色々あるわけですが、 Chainer 以前は、ブロックの接続を作る DSL があって、接続ができたら、誤差逆伝播の計算を考えて、ハイ実行、と実行する形式だったと。 tf.add(A, B) とかすると、 A + B を実行するんじゃなくて、足し算するための計算グラフ内のノードを返す、みたいな感じ

で Chainer は、 chainer.functions.add(A, B) とかすると、そのタイミングで実際に実行する。実行すると同時に、誤差逆伝播する時に必要なグラフも作っておく。コンパイラに対するインタプリタという趣きで、問題が起きた時に問題のある行で止まるので、デバッグがしやすい、分岐などを含むようなフレキシブルなモデルを普通に記述できる、などのメリットがあります。ただ、欠点が2つあります

• Python 無しのデプロイができない。計算グラフを作る DSL という形式であれば、そのグラフをエクスポートしてしまえば Python 無しのアプリから使えるわけです。
• 速度的にオーバヘッドがある。これは、 CUDA の関数実行が遅延されているおかげで、単純なモデルでは GPU 律速になって Python+CPU でグラフ作ったりしてるコストは隠れることが多いです。 cupy てセンスいいものだなあとつくづく思います。が、自然言語モデルや、小さいモデルだと CPU 律速になったりするし、 GPU が高速化し続けてることも相対的に問題を大きくしていっています。

ですが、まあ、研究者のイテレーション速度の方が重要だと考えていて、 define-by-run 良いなあと思っていました。ループがあるモデルを扱ってたことによるバイアスもあると思いますが。

そんな時になるほど！と思うものが現われました。 Swift for TensorFlow というやつです。 Swift for TensorFlow は、 define-by-run 、つまりモデル定義を実行時に行なうことが重要なのではなく、モデルがデータでなく、コードで定義されていることが重要なのだ、と主張しました。当時、 tf.while_loop じゃなくて Python の普通のループを使わせてくれ〜と思っていたので、このコンセプトが大変気にいりました。この図もなるほどーという感じでしたね

https://raw.githubusercontent.com/tensorflow/swift/master/docs/images/AutomaticDifferentiation-Approaches.png

グーグルの作ったもので Native Client の次くらいに好きなものといえると思います。つまり成功する気がしないのですが。 Swift 本当に使うようになるのか？？という普通の疑問がまああるわけです。

で、そういうタイミングで、転職活動中に、具体的にどういう計画かよくわからないけど、 Python コンパイルしよう、という話だったので、本当にできるのかはよくわからないけど、それは関われるものなら挑戦してみたい話だな、と感じました。

このへんの DL フレームワーク話は 退職直後、入社前の間の時期にも書いたりしました。

入社してみた

入ってみると、何も決まってないから、なんか IR をデザインして、 Python をそれに変換して、 ChainerX で実行するのやってくれ、という趣旨のことを言われたと思います。もうちょっと具体的に計画や実装が既にあるかと思ってたので、ずいぶん無茶振り来たなぁ、と思ったように思います。同日にインターンの人が入ってきて、その人には Python を ONNX という業界標準のモデルシリアライゼーションフォーマットに変換するタスクをやってもらおうと思っている、という話も聞きました。

いや似たような Python から変換するタスクを別々にやってどうすんねん、ということで、 ONNX をざっと眺めたところ、これを拡張したら十分にやっていけるだろう、と感じたので、インターンの人には Python => ONNX の部分、私の方は ONNX を実行するものを ChainerX を使って作る部分、と分担しようと考えました。これはなかなか良い決断だったんじゃないかなと思っています。実のところデザインとか全く自信が無いので、 IR とかうまく作れる気がしなかったし、ある程度考えられたデザインにタタ乗りできたのはおいしかった。あと、 ONNX のエコシステムまわりの他の人たちが作ったツールが使えたり、社内の ONNX 関係の別のツールとの協調とかも視野に入るのも良かったです。

このあたりで ChainerX についての理解も深めていきました。 Chainer は行列計算とかの重い計算は numpy/cupy というのに投げてるわけですが、 numpy とコンパチな ChainerX array というのを C++ で作って、 C++ 側に、従来 Python で実装されていた誤差逆伝播を持ってくる、というコンセプト。

前章でデプロイができない、速度が遅い、という問題に触れましたが、 ChainerX はこれらの問題を大幅に軽減するものです。 ChainerX array は C++ で書かれているので、 Python 無しのデプロイの道が開かれてくるし、速度が遅い一番の原因だったらしい、誤差逆伝播が Python で書かれているという問題もなくなるのでした。

作ってみた

とりあえず世の中にある、ある程度大きいネットワークを動かせるようにしていきました。 ChainerX に基本的に必要な関数があるので、基本的には ONNX と ChainerX 関数を対応づけていくだけです。最初は ChainerX を使う C++ コードを生成していたのですが、テストのイテレーションが遅くなるのを嫌って、 ChainerX の関数を次々呼んでいくだけ、みたいな VM を定義して、それを使うようにしました。 ResNet50 くらいは割とすぐ動いたような気がします。

時系列は覚えてないですが、このへんで誤差逆伝播のグラフを生成するコードもでっちあげたのではないかと思います。最適化やらなんやらを実装したいとすると、計算グラフを編集するライブラリとして機能できる必要がどうしてもあるので、そのあたりの proof-of-concept として、自動微分ができる、というのは最低限の機能担保という感があったのでした。

そうこうしているうちに、インターンの方が同じく ResNet50 くらいのシンプルなネットワークを ONNX 化できるようにしてくれて、実際にそのグラフを入力としてトレーニング用のグラフを生成して ImageNet という、 224x224 の画像データを 1000 種類に分類、みたいな使ってトレーニング、みたいなことができはじめていたように思います。

このへんからは時系列曖昧ですね

EspNet を end-to-end で通そうとする日々

EspNet というのは、音声認識や音声合成、その他もできるツールキットで、これのまあまあ複雑なコードパスを通そうと努力してました。とりあえず、ツールチェインの上から下までで、ループなどをちゃんと扱えますよ、という状態にしたいという気持ちがあったので、これをターゲットとした感じでした。 Conv + NStepLSTM + CTC + デコーダーは attention ついてるからループ回して LSTM やる、みたいな感じになってて、色々なものに対応しなければならないのです。

元々の ONNX の Loop や Scan といったオペレータは、固定長の ndarray 的なものの入力が入ってくる前提だったので、これは可変長の Python list とかが扱えるようにしたいなあ、と考えて、ここは結構大幅に拡張した部分でした。

インターンの人が、無茶ぶりにも関わらず、まあまあややこしいループなども動くように作ってくれていた感じでした。実際、ループ動かすための仕様みたいなのもキチンと決めず、かなりダメダメなメンターだったはずなのに、ちゃんとそれなりにそれぽかったのでとても感謝でした。それを引き継いで EspNet で必要な、かなりややこしい変換などをできるように努力していきました。 __init__ で self.x = None しておいて、後で if self.x is None: self.x = ... とかする、遅延初期化みたいなのがなかなか面倒でした。

それが通ると、次はループや if の微分というか誤差逆伝播を頑張って、あとは Python list まわりも逆伝播実装して、これらもなかなか大変でした。

このあたり、ループをちゃんと動かすとか、 Python の list を扱える、とかにこだわっていたのは、 Chainer のフレキシビリティを損ないたくないなあ、と思っていたことがあります。 dynamic shape とか可変長 list 扱うとかすると、どうしても最速が出ない局面は出てくるとは思うのですが、とりあえずフレキシビリティの方が重要かなと。あと dynamic shape を扱いつつも、 static に決まる部分は決める、みたいな方針でやってるので、次元が決まったところは高速化…みたいなこともできるのではないかと思っています。実装が追いついてないですが、 TVM のコード生成使う実験とかは shape がわかってる前提でやっていました(というか TVM は dynamic shape に関して結局なんか計画あるのだろうか)。

EspNet をまともな速度にしようとする日々

動くようになった最初はなんか、素の Chainer より圧倒的に遅い！みたいな状態でした。で…何したんでしたっけ。ちゃんと cuDNN の LSTM を使うようにしたり、 elementwise op の fusion したり、定数伝播やったり、などなど。 Python からグラフ生成してると、なんかゴミみたいなノードができまくるので、定数伝播みたいなのが重要なのですよね…

でまあ、まともな速度になって、 CPU heavy なケースでは Chainer に勝つなあという感じになりました。ただ CTC とかいう処理を実装してなかったので、実際に end-to-end で訓練することができなくて、しかしそんなの実装するのかったるいので、 Python インターフェイスを追加して、モデルの一部分だけを chainer-compiler で処理する、みたいなこともできるようにしました。

でまあそれぽくなりました。 Python コードに多少の、気持ち悪い変更が必要なのが、なんともはやな部分ではあるのですが…

TVM で遊ぶ

年末あたり、 TVM で遊びました。 LSTM は、会社としては直接そんなに重要でないということもあり、ちゃんと Conv とかを良くできるポテンシャルはそなえておかないとかなあ…と。

結果としては、色々面白いけど、 Python と C++ 行ききしまくりのコードがつらいというのがまず感想でした。あと、特に普通の Conv とかだと、伸びしろがそもそもあまりなくて、投下労力に対して得られるものがなあ…という気持ちもありました。

で、とりあえず保留することにしました。いずれにせよ、フレキシビリティという観点などから、自力でカーネルを生成できるオプションは中期的にはあるべきだと考えていて、どこかの段階で戻ってくることになると思っています。

オープンソース化

これやること無限にあるから、一人でやってると崩壊以外見えねえなあ…と思ってたので、人が欲しいです、みたいなことをわめき始めてました。これグーグルだと、人が増えるかあるいはお前のそれやってるそれ意味ないからやめろや、て言われる二択でわかりやすかったのですが、小さい会社でみんなそれぞれ忙しくて、人も増えないがお取り潰しにもならない、という雰囲気でした。

で、どうも社内で取ろうとするんじゃなくて、外から拾ってこい、という文化だと学びました。確かに、個々人で拾って来させるってのは、なるほどベンチャーの成長方法として理に適っているなあ、と思いました。というわけでツイッターでわめいたりしてみました。

ただ、なんかやっぱコミュニケーションがしづらいということを思っていて、ユーザ向けリリース、という感じではなくて、こういうことやってますよ、仲間募集、ということでオープンソース化したいと思って、しました。とはいえ、それなりには、色々整える必要があって、それなりにはめんどうでした。

これから

適当に風呂敷を広げて、結構広い範囲で実装してみたけど、とりあえず、という感じの仮立て付けぽい状態の部分が多い状態で、まだまだやることが無限にあるなあ、と思っています。

基本的に、 chainer-compiler にこだわらず、 Chainer まわりで静的なグラフを扱うシーンのエコシステムを、全体として整えていきたいな、と思っています。最近ちょっと onnx-chainer に手を出してみたりもしていたり、とか。このへんキチンとしてないことがデプロイの大変さみたいなことにも直結してしまっているので。

不完全な部分がそこらじゅうにあって、どこから手をつけても良いような感じだし、やっぱ社内需要を満たすところを優先するのが良いよねえ、と思っているので、社内需要満たす努力をしつつ、汎用的なツールチェインとして少しずつ育てていけると良いなぁ、とか思っています。

あと例のごとく一緒に働きたい人募集中です。うまくいくかは不明ですが、ある種の人には、楽しくはあるんじゃないかと思います。少なくとも僕は大変楽しんでいます。

ONNX はチューリング完全だよ、という話

シクシク素数列 Advent Calendar 2018 向けです。

ONNX はニューラルネットのモデルをエクスポートして、別の実装でインポートできたりする、相互運用のためのフォーマットです。複雑なモデルをサポートできるようにと、 Loop とか If とかがあるので、チューリング完全です。ただまあ実際にえぐい使われ方してる例は見たことがなかったので、やってみました。

https://github.com/shinh/test/blob/master/onnx_gen_4949_prime.py

が、4か9を含む素数を出力する ONNX モデルを出力するプログラムで、

$ wget https://raw.githubusercontent.com/shinh/test/master/onnx_gen_4949_prime.py
$ wget https://raw.githubusercontent.com/shinh/test/master/onnx_script.py
$ python3 onnx_gen_4949_prime.py
$ ls gen_4949_prime
model.onnx  test_data_set_0

とかで ONNX ファイルが出力できます。実行は、 ONNX のループとかをサポートしている処理系があまりないと思いますので、 ONNX runtime とかを使ってください

$ python3
>>> import numpy as np
>>> import onnxruntime
>>> sess = onnxruntime.InferenceSession('gen_4949_prime/model.onnx')
>>> input_name = sess.get_inputs()[0].name
>>> output_name = sess.get_outputs()[0].name
>>> sess.run([output_name], {input_name: np.array(104)})[0]
array([  19,   29,   41,   43,   47,   59,   79,   89,   97,  109,  139,
        149,  179,  191,  193,  197,  199,  229,  239,  241,  269,  293,
        347,  349,  359,  379,  389,  397,  401,  409,  419,  421,  431,
        433,  439,  443,  449,  457,  461,  463,  467,  479,  487,  491,
        499,  509,  541,  547,  569,  593,  599,  619,  641,  643,  647,
        659,  691,  709,  719,  739,  743,  769,  797,  809,  829,  839,
        859,  907,  911,  919,  929,  937,  941,  947,  953,  967,  971,
        977,  983,  991,  997, 1009, 1019, 1039, 1049, 1069, 1091, 1093,
       1097, 1109, 1129, 1193, 1229, 1249, 1259, 1279, 1289, 1291, 1297,
       1319, 1399, 1409, 1423, 1427], dtype=int64)

入力で指定しているのが 104 なのは、 8 の倍数じゃないと ONNX runtime がクラッシュするぽかったからです。他にもいくつか ONNX runtime のバグらしきものを見つけた気がするので、適当に報告しておきます。

チューリング完全ということで、 ELVM のバックエンドを作っておきたいのですが、 TensorFlow モデルバックエンドが遅くて実用にならないという問題があって、 ONNX も似たような感じなので、どうしたものかと思っていたのでした。ただ、なんか最近手っ取り早く高速化する方法を思いついた気がしたので、今度やってみようかと思います。

ICFP programming contest 2018

無職なこともあり、とても楽しい問題だったこともあり、久々にほぼガチで参加してる会になりました。いや楽しかった。順位表が凍結された段階での最終順位は2位で、1位は絶対に無理、その後にできた変更はしょうもないので、おそらく7位とかそのあたりの、5位強みたいなところに落ちついているのでないかと想像してます。暫定2位といっても特に良いところはなく、得点を決める式のおかげで、大幅なとりこぼしが無いだけで、推定1位のウナギに対して全順序がついて負けてる形のはずで、大変くやしい。が、まあ僕的には頑張ったとは思う。

初動

パーサやシミュレータを実装して、簡単なシングルスレッドAI、下から順に塗っていって、既にあるブロックとつながっていないところに置かざるを得なくなると、 Flip する、というものを Ruby で書く。デフォルトよりは大幅によくなることを確認して、いい問題だなあ……と思いつつ、寝る。

シミュレータについて、 SML 的ななにかからコンパイルされた JS だから、単純な方法でこれ切り出せるでしょ……と思ったけど、それに時間を使う余裕は最後までなかった。それに限らず、時間的余裕は最後までなかった。

起きて、 Flip のコストがとてもでかいこと、並列化が大変嬉しいこと、を再確認して、スケジューリングは賢くなくて良い(つまり無駄な動きをしても良い)から、 Flip はできればしない、かつスケールし、できればヘッドのMoveとFillの比が良い方針を考える。

思いついたのは、やはり下からスケジュールして行くのだけど、自分の左右と真下を塗る、という方針。Move:Fill比が最大1:3で、なんとなく良さそうに思ってた。

# B がボット、 O が担当する Fill する範囲
# 右方向が Z 軸、上方向が Y 軸、奥が X 軸で進行方向

OBO
_O_

でも実装してみると最初の戦車ぽい形のやつすらダメで、理由は説明しずらいけどとにかくこの方針で Flip 無しはできないのでした。もう少しちゃんと考えてから始めるべきだった。

エレベータ

次に考えたのは、上方向から見た X-Z の平面を 3x3 の区間に分割して、並列に動くボットは、その空間の中で一回以上塗ることが可能などこかにアサインされる。イメージとしてはエレベータなのだけど、その 3x3 の中心を下って上がって、途中で塗って返ってくる。 3x3 の中央は、ロボットが作業用なので、まだ塗っていない領域が下の方にある場合は底の蓋をしてしまわない。

この方針でたいていの問題が Flip 無しで塗れる感じになり、 3x3 のグリッドの作りかた9種類をそれぞれ試すと、どれかは Full Division の問題を解けるようになりました。

最初に間違った方針で時間を浪費してしまったこともあり、 Lightning Division 中には全部の問題にたいしてまともな点数の結果を返すことができませんでした。見積りをあやまったな、と。

Lightning Division が終わった後も、このコードはバグバグだったので、それを修正しまくって、一通りバグが取れて、一通り FA の問題に適用し終えて提出すると、 FA に対しては全て1位が取れている感じになっていました。潜伏していた人もいたかもですが、これが Lightning Division に提出できていればなあ……と残念。

さてこのエレベータの方針は、

• 3x3 のエレベータのどれを優先するかという判断を何もしていない
• さらに言うなら、 3x3 のうち、他の塗れる 3x3 が増える、つまり仕事が増える順序を優先するべきなのだけど、それをやっていない

という2点の TODO がありました。 Full Division のルールを検討するまでは、これは結構面白い課題だと思ってたので、是非やりたいなーとか思っていました。ですが、構築はそれなりにうまくいっているので、まだ実装してない解体を優先しました。最終的にもこれらの TODO は手つかずのままだった。

役割が無くなったボットは、とりあえず天井まで移動して、それから次に行きたい場所をアサインする、という流れだった。そういう感じでやると、当たり前だけど x=1 z=1 にいるやつは x=5 z=1 に移動しようとして、 x=5 z=1 にいる子が x=1 z=1 に移動しようとする、いわゆるデッドロックが頻繁に起きていた。これはまあ、定期的に全員が Wait を発行している場合、ランダムなタスクの担当者を入れ替える、という雑な方法で解決した。まあこの問題は頻繁に起きることではあるけど、しかしスコアに大幅な影響を与えるほどの問題ではないであろうとそのままにした。

解体して良いかという判断

解体は、構築と違って、この座標のブロックを消して大丈夫か…という判定が自明じゃないので、そこをまずあれこれと考えました。最終的に、近似的な方針でやることにした

• 最初に地面から幅優先探索する
• とあるブロック X に幅優先で辿りついた時、 X に同時に辿りついた元のブロック群が、ブロック X を支えている、と仮定する
• ブロック Y を消して良いかを考える時、 Y が支えている全てのブロックをチェックし、そのいずれかが Y によってのみ支えられている時、そのブロックは消してはいけない

例えば

ＡＢＣ
Ｄ
Ｅ

だと、依存関係は

Ａ→Ｂ→Ｃ
↑
Ｄ
↑
Ｅ

となるので、Ｃしか破壊できないと正しく判定される。

ＡＢＣ
ＤＥ
Ｆ

だと

Ａ→Ｂ→Ｃ
↑  ↑
Ｄ→Ｅ
↑
Ｆ

なので、Ｃに加えて、ＡとＥも、どちらかなら破壊して良い。何故ならＢはその両者から支えられているから。

保守的になりすぎて消せるブロックを消せないと判定するケースがあって、

ＡＢＣＤＥ
Ｆ＿＿＿Ｇ
Ｈ＿＿＿Ｉ

だと、どれを消しても大丈夫なはずだけど、Ｃしか消せないと判定されてしまう。

Void による解体

解体可能判定が上記で決まった後も、特に良いアイデアが無かった。よって、よく覚えてないけど、おおむね構築時の 3x3 に分配するアルゴリズムを使いまわす感じの、しょうもない実装で実現した。

解体時は構築時と違って、 Void によって移動範囲が減ることは無いため、あまり大変なバグは起きることはなくて、まあほどほどのタイミングでこれは完成した。ただ 3x3 に切っていくという方針はそもそも解体にとって良い方法ではないため(特に上述の解体可能判定が正しくないため)、かなり遅いものになってしまったという感じ。

感想戦で twitter で見た方法として、解体は構築の逆再生をすれば良いというのを見て、なるほどこれをやっていれば解体について使った時間の多くの人的時間を節約できたなあ……と思った。

平面 GVoid による解体

明らかに構築に比べて解体で得ている得点がイマイチだったので、解体をもう少し考えることにした。

結果、解体は GVoid でまとめてやるのがやりやすく、依存解析をすっとばせる部分がたくさんあるのもあって、むっちゃいいじゃん、となった。とはいえ、 3次元 GVoid はこの段階では「管理大変そうだなあ…」という感覚があり、2次元 GVoid で上から順に切りとっていくソルバを作った。

これはコード量はおおくはないし、このソルバ自体は前述のソルバと違って全ての問題を解く汎用性はないけど、多くの問題に関しては前述のソルバを凌駕するものとなった。こういう、問題によって違うソルバが有効になる問題は一人チームだとキツいんじゃよーと思いつつ、だがうまくいったのでよしよしと思いつつ次へ。

最高記録管理、あるいはインフラ

今回一人チームきっっつい、と思った部分はいくつもあったのですが、一番きつかった部分でした。今回の問題の場合、単一のプログラムがベストの解を出す必要はなく、複数の似たようなプログラムがそれぞれ出した解の最高の物を提出すれば良い形式で、かつ、その最高の解が必ずしも最終バージョンのプログラムによって生成されている必要はない、という形式でした。

そのため、提出できる解のうち最高のものを管理し、かつその最高のものを越えた解があればそれでアップデートする必要がありました。これは2種類のめんどくさいタスクを追加しました

• 開発中のシミュレータはおそらく正しくないため、現段階でのシミュレータで実行してみて、たしかに一番良い結果が更新された、と判断すれば最高記録として記録する仕組みを作りました。0点を取ると死ぬ今回のルールでは、これは安全で良いアプローチだと思うのですが、問題はシミュレーション自体が大変遅いものであったということでした。おかげで、常に「なんだかもう覚えてないけど、なんかの計算結果を(おそらくムダに)検証している、という状態になりました。
• 3D モデル X を別のモデル Y に変換する、というタスク(FR)は時間が足りなかったこともあり、単純にそれが一番効率だと考えられたこともあり、 X を完全に解体してから Y を完全に構築する、という方針で解きました(たぶん他のチームもそうやっているかと思います)。これは X を解体する最高記録を残しつつ、 Y を構築する最高記録も残して、んでその二つの最高記録をマージしなきゃだということになります。めんどくさい
• 当時の段階では、 FR なモデル(つまり解体&構築なやつ)は、ものによってはひょっとすれば解体+構築より効率的な実装ができるかもなあ……と思っていたので、解体+構築を同時にやるようなアルゴリズムが後でできるかも、という仮定の元、2日目寝る段階では、 FR は単に FA+FD をまとめてやる物を計算して寝たのでした。よって FR 解から FA 解と FD 解を切り出してきて、一番良い FA & FD を切り出す、というような余計なタスクが発生しました

などなどやってるうちに、結構な時間が溶けました。結果として、 FA+FD よりも FR を効率的に解く方法を考えられる問題はぱっと見見つからず、 FA+FD を効率的に解けることを期待したインフラも完全に無駄になりました。

今にして思えば、アルゴリズムで作った手順が、シミュレータで間違ってることは基本的に無いため、再確認は特にせず最高記録を更新する手順にすれば良かったなあ……と思う。

まとめて 3D GVoid

この段階でもう一度リーダーボードを眺めて、構築も解体もほどほどに良い解は提出できている(Flipも無いし並列化もされている)ので、特に「こういうタイプの問題で弱い」みたいなのは無く、単に全て弱いことがわかっていました。そこで、複雑な問題は再計算する時間が無いため、単純な問題に対して単純でかつ有効な解は無いか……ということを考えました。

すると、単純な問題での解体がイマイチな点数であることに気付いたので、あれこれ考えました。あれこれ考えた結果、単純な問題は問題全体を GVoid で消してしまえるのでは……と気付きました。

で、最初に8体に分裂して、全体を消して、終了、みたいなやつを作りました。あたりまえでしたが簡単な問題については劇的な効果がありました。今にして思えばこのロジックをさらに良くして、一回で消し切れない問題に対しても 3D GVoid を使う解を生成する価値があったと思っています。

たしかこれをやってるあたりでリーダーボードが凍結されました。

GFill を使ってみたい

このあたりで、「やりたいことは無数にあるけど、期間内で実際にやれて、かつスコア的に劇的に有効な手が思い当たらんなあ…」と思ってました。その結果、 GFill 使ってないのはムダすぎるよね、と思いました。

で……ごくシンプルな 1D GFill と Fill で解ける問題だけを解くソルバを作りました。序盤の方の問題はこれで全部解けるだろ……という気分で作ったのですが、実際見てみると壊滅的で、 FA 3問くらいの最高記録を更新できただけで終わりました……

まとめ

すごく楽しかった。まじですごかった(低語彙力)。問題をぱっと見た時に、「なるほどこれ俺もできそうだ」と思うにも関わらず、いざやってみるとすごく簡単なことですらクッソ大変、というのがすごく良かった。大変明確に動くヴィジュアライザなども用意されていた。

例年と比べてもノンゼロの点数が少なかったらしい。敷居が高かったのでは、という観測もあるみたい。ごくごく個人的な感覚では、今回の問題の敷居は高くなかったと思う。常に Flip on の状態で動く解が主催から与えられているので、その中にある移動命令いくつかをつなげるだけでノンゼロの点数は簡単に得られる。単に、今までノンゼロを得ていたチームの中でほとんど実質参加してなかった層が、自明なノンゼロ解を発見できなかった、もしくは ICFPC 自体の参加者が減っている、そのあたりが理由じゃないかなあ……と思う程度には、今回の問題は弱いチームに配慮されている問題だったのではないかと思う。

個人的には、 Full Division で追加されたルールは全て必要なかった。今思えば、全ての追加ルールが、単純にゲームをシンプルにする方向に変わった気がする。当初の問題で、勝てたかっていうと今よりもっとひどい負け方をしていると予想されるのだけど、ただどっちが楽しめたかっていうと、 GVoid/GFill の無いルールだったんじゃないかな。というか、最初に考えたエレベータ方針をもっときっちり詰めたかったな。

いやでもまじで当たり回だったとおもってますマジで