Design of Computer Programs - Arantium Maestum

今週末は約束や予定が５、６個あって大変そうだなぁと思っていたのだが、金曜日から覿面に風邪をひいて全部ブッチするという非常に申し訳ないことをしてしまった。

頭が少し朦朧としつつも暇だったので、映画やら見ながら（そういえば超久しぶりに「アマデウス」を見た！）、数年前からやりたかったUdacityのDesign of Computer Programsを始めてみる。教官はParadigms of Artificial Intelligence Programmingの作者でGoogleのDirector of ResearchのPeter Norvig。アロハシャツ着て教えてるのがすごい西海岸っぽい。使う言語はPython。Udacityのコースの中では上級者向けとのこと。

Udacityのいいところは、レクチャーの最中にマルバツ問題やコーディング問題が挟まれていること。３分に一回は問題があるんじゃないか。それで、いちいち自分のコードとPeter Norvigのコードを比較することになる。

思ったより彼のコードと私のコードが一致するケースが多くてホクホク。まあ、List ComprehensionやGenerator Expression、itertoolsの多用はここ数年心がけてきたことで、Python中級者への道の最たるものなので、こういうコースの頭の方で強調されるのは当然とも言える。

しかし、Peter Norvigの小技の冴えはすごい。

ranks = ['--23456789TJQKA'.index(r) for r,s in hand]

とか、私はなかなか思い浮かばない。

ranks = ['23456789TJQKA'.index(r)+2 for r,s in hand]

くらいならいけるが、そうだよね、placeholder入れたほうがエレガントだよね。

あと、地味な構文の割に驚愕したのはlist comprehension/generator expression内でif文をいくらでも入れられること。

例えば以下のコードは、特定の制約のもとにどんな名前の、どの国籍の人がどの色のどの家に住んでいるか、という問題を総当たりで答えるものになる。

houses = range(3)
answer = next((Albert, British, Cyan) 
                for Albert, Brian, Charles in itertools.permutations(houses)
                for Albanian, British, Chinese in itertools.permutations(houses)
                for Auburn, Black, Cyan in itertools.permutations(houses)
                if Brian is Black
                if Albert > Charles
                if Chinese is not Cyan
                if Albanian - British == 1
                if Cyan > Auburn)

このような書き方ができるということを始めて知った。今まではifの後は(... and ... and ...)のようにつなげていた。

これだけでも、読みやすくて非常にグッドなのだが。さらにすごいのは、forとifの順番がかなり自由に変えられること。そしてそれが計算量を劇的に省略することにつながること。

houses = range(3)
answer = next((Albert, British, Cyan) 
                for Albert, Brian, Charles in itertools.permutations(houses)
                if Albert > Charles
                for Albanian, British, Chinese in itertools.permutations(houses)
                if Albanian - British == 1
                for Auburn, Black, Cyan in itertools.permutations(houses)
                if Brian is Black
                if Chinese is not Cyan
                if Cyan > Auburn)

この記述で総当たりではなく、各段階で制約を与えて絞ることになる。generator expression内なのでインデントの心配もすることなく、自由にforとifの順番を入れ替えることができる(ifで絞る変数はすでに上の方でfor文で定義されている必要がある、という縛りはある）。for/ifの順番を最適化すれば、計算量が相当変わる。この例だと3!^3=6³=216なのでほとんど関係ないが、家の数と、名前などの次元が５つずつあれば5!^5=120⁵で、制約を早い段階で適用することで簡単に100倍以上早くなったりする。かなり多用できそうな構文で、これだけでもコースに使った時間の元が取れそう。

まだレッスン２までしか受講していない。レッスン７が最後なので、あと５つある。大変楽しみである。

追記：最近Clojureを使っているので、Python的に自然な構文を思い出すのにちょっと時間がかかった。新しい言語の習得が元の言語をよりよく使えることにつながる、というのは長期的な視点の話なのだろう。

追追記：アマデウスを見てる時は画面に見入ってしまって全然勉強が捗らなかったことは言っておきたい。