GNU Smalltalk チュートリアル（その3）
続きです。
前回までのあらすじ
前回は、カモノハシ本 N-Queen 問題解法に、ncurses で GUI を付けてみつつ、Depandency機構（Observerパターン)をつかって、オブジェクトの コルーチン的側面を強調する・・のに失敗したところまででした。
とりあえず問題点をまとめますと、
- けんじさんをバカにするな！
- ていうか、中身って落書きだけじゃね
- 中途半端にOOPのチュートリアルになっているけれど、GNU Smalltalk のチュートリアルとユーザー層は被らないんじゃ・・
- そもそも絵を描くのならもっと萌える方向で
といったところでしょうか。
なんだか一体なんのチュートリアルだかわからなくなってきた感じですが、とりあえず前回のつづきから。
N-Queen の実行時間を測ってみる
こうしてリアルタイムにパラパラ Queen が移動するのを見れるようになると、なんだか嬉しくなっちゃいますね。なので、Queenの数を替えながらいろいろ動かしてみちゃうのですが、あれま、意外に少ないQueenでも遅いもんですね。画面を表示させながらだと、16-Queen で 30分以上かかります。
といってもこう言うのは表示自体が遅いのが相場ですので、「遅い」と文句を付ける前にちゃんと計測してみましょう。
- run.st
Eval [ | puzzle viewer time result | FileStream fileIn: 'nqueen.st'. puzzle := NQueenPuzzle new: 8. time := Time millisecondsToRun: [result := puzzle solvePuzzle]. Transcript show: time asString,'msec result:', (result collect: [:x|x asString, ' ']) join; cr. ]
Smalltalk で 時間を計測するには、計測したいコード自体を ブロックに入れて、Time class >> millisecondsToRun: に渡してあげるのが定石です。（残念ながら Squeak にあるブロックの #timeToRun メッセージはGNU Smalltalkにはありませんでした）
実行するとこんな感じ。
$ gst run.st 31msec result:1 5 8 6 3 7 2 4
意図したものとはいえ Queen が図的に見れないので少し寂しいですね。最後くらいは表示してあげるようにちょっとだけ改造です。
- nqueenResultPrinter.st
Object subclass: NQueenResultPrinter [ print: result [ | aStream | aStream := WriteStream on: String new. 1 to: result size do: [:line| 1 to: result size do: [:x| aStream nextPutAll: '+---']. aStream nextPut: $+; nextPut: Character nl. 1 to: result size do: [:col| aStream nextPutAll: (((result at: col) = line) ifTrue:['| Q '] ifFalse:['| '])]. aStream nextPut: $|; nextPut: Character nl. ]. 1 to: result size do: [:x| aStream nextPutAll: '+---']. aStream nextPut: $+; nextPut: Character nl. Transcript nextPutAll: aStream contents ] ]
・・と言い訳しつつ、その1 であまりに酷いコードを晒した結果表示クラスをさり気なくリベンジしてみたり(^^;
せっかくなのでちょっとチュートリアルっぽい薀蓄を。他言語の ostringstream や StringBuffer、StringBuilder みたいなことをやりたい場合、Smalltalk では WriteStream を使います。・・といっても Smalltalk のはちょっと変わっていて、WriteStream は「領域がいっぱいになったら 大きな領域を取得してそこにコピー」というアルゴリズムだけ。領域の構造は外から与えてあげる作りになっています。だから直接 new したらダメ*1。
で、これをバインドします。
- run.st
Eval [ | puzzle viewer time result printer | FileStream fileIn: 'nqueen.st'. FileStream fileIn: 'nqueenResultPrinter.st'. puzzle := NQueenPuzzle new: 8. time := Time millisecondsToRun: [result := puzzle solvePuzzle]. Transcript show: time asString,'msec result:', (result collect: [:x|x asString, ' ']) join; cr. printer := NQueenResultPrinter new. printer print: result. ]
もう一つ薀蓄ですが、今回は Viewer を連結しないので、NQueenPuzzle >> solvePuzzle の中で、null が Queen に addDependent: されてしまうのですが、気の付く人は「なんで落ちないの！？」って思ったと思います。
そこらへん、実は Object クラスでupdate: が
Object >> update: aParameter [
"Default behavior is to do nothing. Called by #changed and #changed:"
<category: 'change and update'>
]
という感じに実装されていて、よろしくつじつまを合わせてくれるのです。ここら辺の妙に阿吽なフォローっぷりに老舗の味というか、伊達に デザインパターンの宝庫を長年やっておりません、という矜持を感じます。
・・と、まぁ自己満足な薀蓄はここら辺までにして、実行結果はこんな感じ
$ gst run.st 26msec result:1 5 8 6 3 7 2 4 +---+---+---+---+---+---+---+---+ | Q | | | | | | | | +---+---+---+---+---+---+---+---+ | | | | | | | Q | | +---+---+---+---+---+---+---+---+ | | | | | Q | | | | +---+---+---+---+---+---+---+---+ | | | | | | | | Q | +---+---+---+---+---+---+---+---+ | | Q | | | | | | | +---+---+---+---+---+---+---+---+ | | | | Q | | | | | +---+---+---+---+---+---+---+---+ | | | | | | Q | | | +---+---+---+---+---+---+---+---+ | | | Q | | | | | | +---+---+---+---+---+---+---+---+
あっ、しまった。何ステップだか分かりません。で、さっきよりも5msec短いですね。うーんこの位の実行時間だと パズル自体の時間より他のいろいろで差のほうがおっきいのかな？
コンピュータって遅い
というわけで、もう少し速度が実感できる様、4-Queen から 30-Queen までの時間を測ってみます。
- measurement.st
Object subclass: StepCounter [ | step | initialize [ step := 0 ] update: aQueen [ step := step + 1 ] step [ ^step ] ] Eval [ | printer stepCounter | FileStream fileIn: 'nqueen.st'. FileStream fileIn: 'nqueenResultPrinter.st'. printer := NQueenResultPrinter new. stepCounter := StepCounter new. 4 to: 30 do: [:queenCnt | | puzzle result time | Transcript show: queenCnt asString, '-Queen'; cr. puzzle := NQueenPuzzle new: queenCnt. puzzle viewer: stepCounter. stepCounter initialize. time := Time millisecondsToRun: [result := puzzle solvePuzzle]. Transcript show: time asString,'msec', ' step:', stepCounter step asString , ' result:', (result collect: [:x|x asString, ' ']) join, ' (', (time / 25 / stepCounter step) asFloat asString, 'msec/step)'; cr. printer print: result. ] ]
実行結果はこんな感じになります。
4-Queen
1msec step:26 result:2 4 1 3 (0.001538461538461538msec/step)
+---+---+---+---+
| | | Q | |
+---+---+---+---+
| Q | | | |
+---+---+---+---+
| | | | Q |
+---+---+---+---+
| | Q | | |
+---+---+---+---+
5-Queen
1msec step:15 result:1 3 5 2 4 (0.002666666666666667msec/step)
+---+---+---+---+---+
| Q | | | | |
+---+---+---+---+---+
| | | | Q | |
+---+---+---+---+---+
| | Q | | | |
+---+---+---+---+---+
| | | | | Q |
+---+---+---+---+---+
| | | Q | | |
+---+---+---+---+---+
6-Queen
2msec step:171 result:2 4 6 1 3 5 (0.0004678362573099415msec/step)
+---+---+---+---+---+---+
| | | | Q | | |
+---+---+---+---+---+---+
| Q | | | | | |
・
・と、このままペタペタ貼ってくにはちょっと場所を取りすぎなので、結果を表にまとめなおすと、
| Queen | time(msec) | step | time/step | result |
|---|---|---|---|---|
| 4 | 1 | 26 | 0.0015384 | 2 4 1 3 |
| 5 | 1 | 15 | 0.0026667 | 1 3 5 2 4 |
| 6 | 2 | 171 | 0.0004678 | 2 4 6 1 3 5 |
| 7 | 1 | 42 | 0.0009524 | 1 3 5 7 2 4 6 |
| 8 | 17 | 876 | 0.0007763 | 1 5 8 6 3 7 2 4 |
| 9 | 9 | 333 | 0.0010811 | 1 3 6 8 2 4 9 7 5 |
| 11 | 26 | 975 | 0.0010667 | 1 3 6 8 10 5 9 2 4 7 |
| 12 | 79 | 3,066 | 0.0010307 | 1 3 5 8 10 12 6 11 2 7 9 4 |
| 13 | 27 | 1,365 | 0.0007912 | 1 3 5 2 9 12 10 13 4 6 8 11 7 |
| 14 | 604 | 26,495 | 0.0009119 | 1 3 5 7 12 10 13 4 14 9 2 6 8 11 |
| 15 | 459 | 20,280 | 0.0009053 | 1 3 5 2 10 12 14 4 13 9 6 15 7 11 8 |
| 16 | 3,889 | 160,712 | 0.0009679 | 1 3 5 2 13 9 14 12 15 6 16 7 4 11 8 10 |
| 17 | 2,320 | 91,222 | 0.0010173 | 1 3 5 2 8 11 15 7 16 14 17 4 6 9 12 10 13 |
| 18 | 18,491 | 743,229 | 0.0009952 | 1 3 5 2 8 15 12 16 13 17 6 18 7 4 11 9 14 10 |
| 19 | 1,216 | 48,184 | 0.0010095 | 1 3 5 2 4 9 13 15 17 19 7 16 18 11 6 8 10 12 14 |
| 20 | 115,886 | 3,992,510 | 0.0011610 | 1 3 5 2 4 13 15 12 18 20 17 9 16 19 8 10 7 14 6 11 |
| 21 | 5,216 | 179,592 | 0.0011617 | 1 3 5 2 4 9 11 15 21 18 20 17 19 7 12 10 8 6 14 16 13 |
| 22 | 1,114,49 | 38,217,905 | 0.0011665 | 1 3 5 2 4 10 14 17 20 13 19 22 18 8 21 12 9 6 16 7 11 15 |
| 23 | 17,972 | 584,591 | 0.0012297 | 1 3 5 2 4 9 11 13 18 20 22 19 21 10 8 6 23 7 16 12 15 17 14 |
| 24 | 306,234 | 9,878,316 | 0.0012400 | 1 3 5 2 4 9 11 14 18 22 19 23 20 24 10 21 6 8 12 16 13 7 17 15 |
| 25 | 38,631 | 1,216,775 | 0.0012699 | 1 3 5 2 4 9 11 13 15 19 21 24 20 25 23 6 8 10 7 14 16 18 12 17 22 |
| 26 | 352,230 | 10,339,849 | 0.0013626 | 1 3 5 2 4 9 11 13 15 21 23 25 20 22 24 26 10 7 16 12 8 6 18 14 19 17 |
| 27 | 40,4337 | 12,263,400 | 0.0013188 | 1 3 5 2 4 9 11 13 15 17 19 23 25 27 24 26 6 10 7 16 8 12 14 21 18 20 22 |
| 28 | 2,830,980 | 84,175,966 | 0.0013453 | 1 3 5 2 4 9 11 13 15 17 23 25 22 28 26 24 27 7 12 16 18 8 10 14 20 6 21 19 |
| 29 | 1,586,958 | 44,434,525 | 0.0014286 | 1 3 5 2 4 9 11 13 15 6 20 24 26 21 29 27 25 28 8 12 7 16 10 17 22 14 18 23 19 |
| 30 | 81,594,001 | 1,692,888,135 | 0.0019279 | 1 3 5 2 4 9 11 13 15 7 23 26 28 25 22 24 30 27 29 16 12 10 8 6 18 20 17 14 21 19 |
うーん・・・。
まぁ、1ステップあたりの時間のばらつきをみればあんまり、いやまったく正確なデータではないのですが、そんなことは だんだんもとい ぐんぐんと伸びる時間のまえにはまったく些細な事に思えてきます。*2
ちょっと非力な Atom N270 だということを差し引いたって、28-Queen で 47分、29-Queen は結構早くて26分、でも30-Queenではググっと伸びて 1359分・・・ってピンとこないな、えっと、つまり22時間ですか!?。*3
・・・遅！コンピュータって遅っ！
確かにはなから速さは狙っていない造りですが、それにしたって想像よりも遅いというか。なんだか今時コンピュータって、もう充分早くって、力が有り余っているようなイメージがありますうが、ぜんぜんそんなことはないんですね。N-Queen 問題ですら力技*4で押しきるには、まだまだコンピュータのパワーは発展途上です。
でもなぜでしょう。わたしのコンピュータ、標準エラーにこんな（↓）
一生懸命なメッセージをいっぱい破棄ながらうんうんファンを回して頑張ってる姿がなんだかとってもかわいらしく思えてきました。
（イメージ映像）
あぁ、風子さん*5かわいいよ風子さん。
というわけで、次回はもっと風子さんに優しいプログラムを組んでみたいと思います。
*1:GSTだとなぁんも言わずに落ちるだけですが、VisualWorksだと new すると親切に「newはダメだ。おまえら on: をつかえよ！」・・て教えてくれます.いいなー、VisualWorks
*2:最初は それぞれの Queen数で 複数回実行して平均をとってたのですが、あまりに時間が掛かりすぎて止めちゃいしました(^^;
*3:なにせこんなに長いとは思ってなくて、さすがに待ちきれずにメールチェックちゃったり、Webで調べ物したり、ちょろっとエディタつかっちゃったりと、そんな内職をすこしさせちゃったので、専念させたらもう少し早いかも
*4:バックトラッキングしてるので「力まかせ探索」ではないですが、さりとて速度にもまったく気を遣ってないわけで
*5:わたしの愛機 MSI Wind Netbook U100 は、2ch 界隈では「風子」と呼ばれています。愛い奴です
