Pythonのe-learning続編、アルゴリズムとデータ構造

6月30日のPythonのe-learningを試してみたで、interractivepython.orgの用意しているe-learning　How to Think Like a Computer Scientist: Interactive Edition　を紹介した。
タイトルからは、これを終えるとコンピュータ科学者のように考えることができるということだが、実際にはごく普通のPythonの入門コースだった。再帰が出てきて、オブジェクト指向をちょっとかじってオシマイだった。

これだけでは、プログラムが組めるようにはならない。
ということで、この続き、より高いレベルのコースは無いかと探したら、用意されていた。
Algorithms and Data Structures using Python

「アルゴリズムとデータ構造」というタイトルは昔から非常によく見かける。

アルゴリズムの説明が中心なのだが、その前に、ちゃんと計算量、ビッグ・オーについての説明があった。
Pythonには配列はなく、何でもリストにして扱うので、柔軟性は良いのだが、リストの特徴を考えずにプログラムを組むと激遅になってしまう。そのあたりを、実際にリストの基本操作１つ１つについて丁寧に説明してある。

Big-Oを求めるだけでなく、実際に時間計測をして、きちんと体感するようになっている。
そのために、timeitモジュールを使って計測し、アルゴリズムの比較をしている。
プログラム内の小さな部分の処理時間を計測するには、timeitはとても便利に出来ているのだ。
でも、timeitについては今回は説明を省略するので、今すく知りたい場合は自分で調べてください。

まだ一部しか読んでいないが、最後はツリーやグラフのアルゴリズムまで紹介しているようだ。
ここまでやれば、まあ簡単なデータ構造は操れるようになると思う。

演習問題の形式が入門編とは違っていた。
入門編では、問題毎にブラウザ上で用意されているプログラムを修正したり、ゼロから書いたりであったが、アルゴリズム編では、演習問題は問題文だけになっていて、自分のPython環境でプログラムを作るようになっている。
問題によっては計算量が多かったりして、ブラウザ上で実行させるのが困難な問題も多い。また、ファイル入出力などいろいろ行う場合、ブラウザ上では制限があり過ぎてできない。
それよりも、もうブラウザ上でのプログラミングを卒業し、実際のPythonのプログラム開発環境で課題をやりましょうということらしい。

アルゴリズムについて本格的に勉強したければ、やはりＭＩＴのアルゴリズム入門だろうか。
イントロダクションとあるので入門書と思ってはいけない。1000ページを超える本で、延々と書かれている。価格もとても立派で、税抜きで14,000円である。
この本を教科書に使っているＭＩＴの授業のビデオも多数（何年分も）公開されている。
とくに、2005年のビデオは、原著者らが講義している。
その後の同じ内容で講師が異なるものがいくつも公開されている。
ビデオが全部あるだけではなく、音声をテキストにしたものもあるので、英語の聞き取りが苦手でも大丈夫になっている。さらに、大量のドキュメントも用意されていて、至れり尽くせりで、なおかつ無料である。