コンピュータサイエンス

コンピュータサイエンスというのは色々なパラダイムが共存しているように思えます。

論理学や離散数学の延長といえるものもありますし、UIなど認知に伸びていく分野も多いですし、そもそもサイエンスといいつつ工学的な応用が非常に大きな部分を占めているように思えます。そうするとコンピュータサイエンスというくくりは大きすぎるのかもしれませんね。

それでも、ゴールは多岐に渡っても学ぶべきスキルというのはある程度収束するものだと思います。つまり共有できるツールや枠組みというのはあるのでしょう。やはり基礎から学ぶというのは定石の一つだと思います。イメージとしてはピラミッド型に伸びている科学技術の要の部分から学ぶということです。

さて、では基礎を学ぼうとしたときに、じゃあ基礎って何なんでしょうか。思うに本屋に並ぶ本はアプリケーションレベルのものばかりで、むしろ末端を深く解説するものが置かれている印象です。だからといってアプリケーションを作りたい人が記号論理学とかを学ぶにはモチベーションがないとやってけないように思えます。


ということでまずはコンピュータサイエンスを俯瞰するという作業がまず必要になるでしょう。どういう分野があって、どういう内容をやっていて、それらはどう関連しているのか。

お勧めの教科書はこちら。



一冊でだいたいの俯瞰が出来るようになります。
Cやjavaなどの高レベル言語が物理レベルまでどう翻訳されていくか、コンピュータが下部構造をいかに隠蔽してあるか、丹念に説明されています。


あとはADUniがおすすめです。
これは元々、他分野のバックグラウンドを持つ学生に一年間で情報科学を一通り教えるというコンセプトで生まれたプログラムです。各分野を体系立って学ぶことが出来ます。前述の教科書を見て面白いと思う分野があればこっちでもっと深く学ぶというのが良い方法だと思います。

プロファイラを使ってみよう

プロファイラって使ってますか？

なんか思ったよりもっさり動いているなぁという時に思いつくがままに改良してみて、あまり上手くいかないというのは、改良している部分がプログラムのボトルネックではないからです。

しかしプログラムの中のどの部分が時間を食っているのかは分かりづらいこともあります。

そこで便利なのがプロファイラ。

プロファイラは実行されたプログラムの関数ごとの計算時間、呼び出し回数などなとを計測するかなり便利な代物です。

ここでは例としてgnuのg++プロファイラ、gprofの使い方を説明します。

使い方の手順としては、


1. -pgオプションをつけてコンパイルする。 
g++ -pg main.cc

2. 実行する。 
./a.out

3. gprofを実行する。
gprof a.out


とするだけでプログラムの各関数の消費時間が空間的に理解できるように表示されます。

gprof出力の全文を載せるとちょっと詳細過ぎるのでここでは一番に見るべき情報に絞ります。

Flat profile: 各関数で結局どのくらい時間がかかったのか。
Call graph: 各関数がどのように他の関数から呼ばれたか。

Flat profile:

Each sample counts as 0.01 seconds.
%        cumulative self           self    total
time  seconds       seconds calls  s/call  s/call  name
67.15 30.77         30.77     2    15.39  23.14    f2
33.82 46.27         15.50     1    15.50  15.50    f1
0.07   46.30         0.03                          main

Call graph (explanation follows)

granularity: each sample hit covers 2 byte(s) for 0.02% of 46.30 seconds

index   %time        self  children  called  name

[1]     100.0        0.03   46.27             main [1]
                     30.77  15.50     2/2      f2 [2]
-----------------------------------------------------
                     30.77  15.50     2/2      main [1]
[2]     99.9         30.77  15.50     2      f2 [2]
                     15.50   0.00     1/1      f11 [3]
----------------------------------------------------
                     15.50   0.00     1/1      f2 [2]
[3]        33.5      15.50 0.00       1      f1 [3]
-----------------------------------------------

この辺りを見ればどの関数を手直しすべきか分かると思います。
プロファイラはユニットテストみたいに使うと便利なんじゃないかと思います。
つまり、


1. コードを改善する。

2. 実行してプロファイラにかける。

3. プロフィールを分析し、次に改善すべき関数を決める。


のイテレーションを行えば効率良く質の高いコードがかけます。

とにかくはしから改善していけばいいじゃないか、という考えもありますが、アムダールの法則をみるに、ボトルネックとなっている関数から改善するという考えの方がプログラマ的なんじゃないかなと思います。

複数人の開発なら端から改善していく、TOYOTA生産方式というのは有用でしょうが、一人の開発の場合資源の投下場所は考慮すべきでしょう。

データ構造とアルゴリズム

データ構造とアルゴリズムの本は五万とありますね。アプリケーションレベルに近いほど多様性を増していくというのは書籍の数にも表れますね。

しかし考えてみると、データ構造やアルゴリズムというのは離散数学なので、例えばマージソートの説明の仕方にそんな五万通りもあるようには思えません。

逆に、アルゴリズムを学ぶメリットというのはアルゴリズムが汎用的であり、一度根幹を学べば同じフレームワークを似た問題で何度も使えるというところにあると思います。

つまるところ、汎用的で再利用可能であることが特にアルゴリズムを学ぶべき理由であると思います。そうすると、javaアルゴリズムだとかC++アルゴリズム事典だとかいう本はややアドホックにすぎるように思えます。

でもこういうアドホックな本が出回るのは自然なことで、アルゴリズムが抽象的すぎて学習しずらいということは大いにあるでしょう。目的からの距離が遠いですから。

データ構造とアルゴリズムで一番評判の高い本はIntroduction to Algorithmsでしょう。


しかしこの鈍器に等しい厚さの数学書を一人で全て理解しきることが出来る人はそんなにいないでしょう。

そこで、なんとも素晴らしいことに、MITOPENCOURSEWAREでこの本の講義が開かれております。

Introduction to Algorithms MIT OPEN COURSEWARE

You TubeのVideo Lectureに比べて充実しているのは、Video Lectureだけでなく講義ノート、宿題や試験とその解答まで公開されていることです。MITの学生と殆ど変わらない学習環境になるんじゃないでしょうか。


もっと薄い和書だとデータ構造とアルゴリズム(杉原厚吉)とかがコンパクトにまとまっています。しかし薄いということは内容が凝縮されていることであって必ずしも簡単だとは限らないと思います。いずれにせよ上の洋書があまりにもきついという人はこちらから初めてもよいように思います。

コンピュータアーキテクチャ

今や大学の授業はタダで受けられる世界です。

テキストファイルのチュートリアルはいくらでもあるし、動画ならCoursera, iTunes, Youtubeで見られる。具体的に知りたいことがあるならgoogle検索で調べればいいし、見つからなければStack Overflowに聞けばいい。

ただ、こうなってくるとどう手をつけていいか分からなくなってきますよね。情報がありすぎると今度は適切なMiningをする必要が出てきます。

ということでData Miningの話も面白いと思うのですが、今日はComputer Architectureを学ぶための１セットをまとめてみました。

・Computer Architecture - Carnegie Mellon

カーネギーメロンのコンピュータの授業です。
これを見れば少なくともアプリケーションレベルのプログラマは困ることはないんじゃないかと思います。35回×1.5時間なのでかなりしっかり学ぶことが出来ます。そんなに時間をかけられないという人でも最初の２、３回だけでも見るべきだと思います。コンピュータアーキテクチャの概念とか目的といったものが非常に明瞭に分かります。Trade-offや隠蔽のヒエラルキーなどの本質的な考え方というのは本では学びにくいことなので。

Computer Architecture Video Lecture

・Computer Organization and Design (Patterson & Hennessy)

世界的に有名でコンピュータアーキテクチャの金字塔といえる教科書です。

しかし、この本、声を大にして言わなければならないのは、日本語訳があまりにもひどすぎる！和訳版は残念ながら学術書ではない。(こんな価値の高い教科書がこんな訳で出てしまう限り日本のIT技術がアメリカに追いつくことはないだろう・・・)

ので原著を強くお勧めします。アセンブラ、ISA、 プロセッサまわりの説明が充実し手織り、今後必ず必要になるであろう並列プログラミングを真に実現するのに非常に役に立つ教科書だと思います。

また、上のCarnegie Mellonの講義でも教科書的に使われていますので、この本を読みつつ講義を見れば、理解がいっそう深まるかと思います。

しかしこの本の翻訳の問題はもっと根が深いでしょうね。
IT関連で何か検索すると英語でした方が100倍位情報があるというのは非常に大きな問題でしょう。もう日本語で科学やビジネスは出来ないということなのでしょうか。

・CPUの創りかた

なんとも人を選ぶ表紙で、キャッチーなだけの中身のない本かと思ってしまいますが、とても面白い本です。かなり本格的な理論を学びつつ、手を動かして4BitCPUを作ることが出来ます。

４bitCPUなのでもちろん実用性はないのですが、ゲートや回路レベルからCPUレベルまでの階層がどうなっているのかを理解するのに非常に役立ちます。

この本を学べば結構本格的な電子工作も出来るようになると思います。というかこの類の本でこんなにAmazonのレビューが高いというのも驚きです。

ということでコンピュータアーキテクチャのまとめでした。

この流れでコンピュータサイエンスを俯瞰していこうかなって考えています。

Mutex Profiler Mutrace

プロファイラはコードのパフォーマンスをあげるのにとても役立ちます。コードのどこに時間がかかっているのかが非常に明瞭にわかるからです。

並列計算のパフォーマンスも一般的なプロファイラでかなり分かることがたくさんありますが、同期処理などのオーバーヘッドを見出すのは結構難しいです。

また、ロックをもっと細かくするにせよatom型を使うにせよ、そのような同期処理を改善するのは結構手間がかかるしどちらが速いか見積りずらいことは多々あります。

そういうときに便利なのがmutrace、Mutex Profilerです。

実行ファイルと一緒に使い、mutexのロック回数、ロックの推移回数、合計待ち時間、ロックの種類などを列挙してくれます。ので改善すべきロックが一目瞭然で分かります。

$ mutrace gedit

とシンプルなコマンドで使えます。出力はこんな感じ。

mutrace: 10 most contended mutexes:

 Mutex #   Locked  Changed    Cont. tot.Time[ms] avg.Time[ms] max.Time[ms]       Type
      35   368268      407      275      120,822        0,000        0,894     normal
       5   234645      100       21       86,855        0,000        0,494     normal
      26   177324       47        4       98,610        0,001        0,150     normal

(公式ページより引用)

こんな感じで出たら、35番のロックは改善した方がいいかな？って絞ることが出来るという訳です。

便利。

・参照リンク

公式ページ

mutraceのGitレポジトリ

エクスプローラ+コマンドライン

かなり簡単だけど便利なお話を。

エクスプローラからすぐにコマンドラインを出す方法があります。

それはエクスプローラのアドレスにcmdと打つ。それだけでそのディレクトリをcurrent directoryにしたコマンドラインを開くことができます。便利。

Linuxにも似た機能はありませんかね。

以上！

Kinectを使った指揮者体験

音楽なんて全く分からない素人だけれども、一回オーケストラの指揮をしてみたい！

そんな方は多いんじゃないでしょうか。題名のない音楽会なんてのもありますし。

そんな夢を叶えるアプリがあります。

The Computer Orchestra

クラウドソーシングの形でネットから音源を取ったり自分で作ったりしたものを組み合わせて曲を作れる。それにKinectで取得したジェスチャーに結びつけて指揮を可能にする、ということのようです。Kinectを持っている方は試してみては？PCはこんなに必要ないので。

簡易版ですが、オーケストラの指揮のような非常に機会の限られる経験を可能にするというのは面白いですね。簡易版と言いましたが、音色や曲から作れるし、ジェスチャーでリアルタイムに指示を出すことも出来るので本当に指揮者のようなことが出来、強いこだわりを感じます。ちゃんと音楽してます。

やっぱりkinectのような実世界にせり出して来るようなインターフェースは面白いですね。身体性というのでしょうか。

こんなアプリを作りたいです。

printfよりもデバッガを使おう

デバッガを使わない人って意外にいるように思えます。

printfとかの出力で済ませられるバグも多いでしょう。いちいちデバッガをつかうのも大袈裟です。私がデバッガを使うべきだとする目安は、「ここが原因だろう」と考えて書いたprintfがハズレだった場合です。

多くの場合原因の候補箇所はいくつかの、直近に編集した表層部分のエラーでしょう。九割くらいのバグはここで解決されます。

しかし予想が外れた場合。これはえらいことです。エラーの原因がシステムのより深いところにあったということになります。人は、こういう予想外の自体に対してより近視眼にして対処してしまいがちだと言います。結果としてだんだんコードの狭い部分、狭い部分へと目を絞ってしまいます。

printfでのデバッグは、「ここに原因があるだろう」と予想して、それが正しいか否かしかわかりません。対してデバッガは「どの辺りに原因があるか」を測ることが出来ます。

謂わば、printfがクローズドクエスチョンなのに対してデバッガはオープンクエスチョンが出来る、ということです。

なので原因がよく分からないバグに対してはデバッガを使う方が賢明に思えます。二分木探索の方がリストを頭から探索するより速いですし。（そういう理由でデバッガの使い方のコツとして、二分木探索を心懸ける、というのがあったりします。）

デバッガの使い方は、UI部分はネットにいっぱい資料があります。「Eclipse デバッガ」で検索すれば丁寧な解説が見られるでしょう。デバッグの理念、例えば上述の二分木探索みたいな話を知りたい方は以下の「実践　デバッグ技法」をお勧めします。