Python で計算量を意識する

アルゴリズムとデータ構造ワークショップ3日目(最終日)。

受講生たちの進度を聞くと、ちょっと厳しそうだったので、午前中いっぱいはデータ構造を続けてもらう。

お昼はくら寿司である。宅配だと高くなるので、車を持っている後輩に車を出してもらったら、たまたま今日に限ってなぜか家を出るときパンクして、結局タクシーでお寿司を持ってきてくれたりというハプニングがあったようだが、参加者の満足度は高かったように思う。3日それぞれ違うメニューを35人分オンタイムで届ける、というのはかなり大変だろうが、しっかり最後まで大過なく準備してくれて、とても助かった。毎年こんなワークショップができるわけではないが(TAの予算も毎年はつかないだろうし)、ときどきはこういうのがあってもよいかな、と思った。

午後はマージソートクイックソートを実装してもらう。マージソートは自分も思い入れがあるアルゴリズムなので、ちょっと解説してみたりする。

Python で書いている人たち、答えは正しいはずなのに処理速度が遅いようでタイムアウトする、という報告を受け、自分でも書いてみたりする。どうも Python 3 が Python 2 よりも若干遅いようで、そこで少し差があるようだが、それ以外は書き方の問題のようである。基本的に計算量がどこで節約できるか(最低限これだけは処理しなければいけない、という最小回数は仕方ないが、それ以上の無駄な処理をしていないか)ということを意識するかどうかで、差が出てきているようである。まあ、同じように効率をあまり意識せず実装しても、C/C++ ではタイムアウトしないので、最初から C や C++ で書けばいいという話でもあるが……。

あっという間にワークショップが終わったが、振り返るとけっこうおもしろいワークショップだったように思う。参加者も、来るまでは不安だったが、来てみたらすごく楽しくて、、おっとやりたかった、と言ってくれていたし、TA の人たちも勉強になったようだ。

結局詳しい人とそうでない人をどのようにインタラクションさせるか、書けない人にどうしたら手を動かしてもらえるか、ということに尽きるのだが、書けないという気持ちが先行して手が動かないのが一番の問題なので、とても簡単なところから何回も練習するのがいいのだと思う。Python では CodingBat をまずやってもらうのだが、こういう「素振り」「100本ノック」をコツコツやるとよいと思うのだ。小学生の国語ドリルや計算ドリルのようで、できる人にはかったるいのだろうが、小学校のドリルは、繰り返し練習すれば誰でもそれなりにできるようになる、という意味で、けっこうすごい教材なのではないか?と思ったりしている。(ドリルが必要なかった人は、そうは思わないのかもしれないけど)

毎年少しずつ授業や基礎勉強会を入れ替えていて、誰でも自然言語処理ができるようになる最小セットを比較検討しているのだが、まだいろいろ試す余地がある、ということが発見でき、有意義なワークショップであった。