他の研究室の「Core i7、メモリ24Gバイト搭載パソコン」を使ってみた

「Core i7、メモリ24Gバイト搭載パソコン」（リンク）は、このブログ一の人気記事です^(*1)。今回の記事は、このコンピュータを使った研究の記事です。別の研究室の学生さんが書いてくれました。何故か、違う研究室の学生さんが、この高性能パソコンを使ってくれています (^_^;

^(*1) 「AKB48握手会」（リンク）に抜かれるのは時間の問題でしょう。「三浦春馬さんのガルボのCM」（リンク）には3日で抜かれました。瞬殺です (T_T)。

---

私の研究の目標は，文書の著者をPCを使って推定することだ。文書内の，良くつかわれる単語の組合せ（＝ルール）を見つけることで，著者の分からない文書を推定する際のヒントを作り出すことに目的がある．

初期の実験として10人分の小説を用意し，それぞれからルールを抽出する．
計算はPCに負担が掛かるため，夜，研究室を去る際にPCに作業するよう，プログラムを動かして帰宅する．小規模な文書でテスト済みのプログラムなので，明日来た時にはきちんと結果が出力されていると期待できる．

だが次の日，期待は裏切られていた．ほとんど進んでいない．2/10人だ．遅い…
中身を確認すると，ルールは出力されており，ヒントの作成には成功していた．プログラムはきちんと動いているし，計算が非効率であるのが問題のようだ．このペースだと３日近くかかることになる．修正か…いやでも面倒くさい…もっと高速なPCはないだろうか…と思っていたらおいしい話が舞い込んできた．
「隣の研究室にすごい性能のPCがあるよ」
ちょっと話を聞いてみると，自分が使っているPCの十数倍は凄そうな奴だった．
交渉してみると，研究目的ならば暫く貸して頂けることになった．
こんな機会はめったになく，せっかくならと思い立ち，ルールを抽出する文書の量，文字数を増やして早速動かしてみる．多少計算が非効率でも，マシンスペックに物言わせてどうにかしてくれるだろう，という期待だった．

これがいけなかった．

計算初日，一件も結果が出ていなかった．さすがに文量を多くし過ぎたか．
三日目，まだ出ていない．初期実験は終わり，まずまずの結果が出ていた．
少し間を空けた７日目，おかしい…途中結果を見てみると400万行と表示された．
文書1件からルール抽出のために400万行使われている．しかもまだ途中だ．
長いこと経った今も，それはまだ終わる気配を見せず，かといってここまでやって終わらせるのも憚られるため，ずるずると継続されている．

問題は大きく2つだった．一つ目は，プログラムの計算量を軽視したこと．文書量により爆発的に増加する計算量を，高スペックPCなら処理しきれると甘く見て，安易に増やしたことだ．根本的な問題が大きな支障になる良い例だ．
二つ目は，中止を決断できなかったこと．これは経験の無さに起因するが，さすがに3日目あたりで異常に気付くべきだった．結果として資源としてのPCを奪ってしまっている．
以上2点を反省し，より効率良い実験へとつなげていきたい．

研究で頑張り、休養しているところです

追記
約1ヶ月計算し続け、先ほど終了しました。

---

斜向かいの教員からのコメント


　CPUが10倍速くなったら、処理できる個数はどれくらい増えると思いますか？　これはアルゴリズムの計算量に依ります。計算量がO(2ⁿ)のとき、CPUが10倍速くなっても、処理できる個数は3個しか増えないって、びっくりしませんか？

時間計算量	スピードアップ後の最大サイズ
n	10倍
n log(n)	十分nが大きければ、ほぼ10倍
n2	3.16倍
n3	2.15倍
2n	+3.3個

　計算時間だけでなく、計算量を考慮できるのが、優秀な技術者です。今回の件で、計算量の大事さを学習してくれたと思います。


上の表は、以下の本の2ページ目から引用しました。
　A.V.エイホ. J.E. ホップクロフト, J.D. ウルマン 著
　野崎明弘, 野下浩平訳
　アルゴリズムの設計と解析I
　サイエンス社, 1977年