スポンサーサイト
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
【--/--/-- --:-- 】
| スポンサー広告 | コメント(-) | トラックバック(-) |
Ruby との悪戦苦闘で明けた新年

年明けには Ruby プログラミングをやった.去年の夏に「プログラミング教育用なんかにもいいかも」と書いたことのある ruby だけど,いま教えているオペレーションズ・リサーチの授業でじっさい ruby プログラミングをやることにした.プログラミングの経験がないという受講生が「プログラミングをやってみるいい機会」と意欲を見せたため,「じゃあ,すぐにマスターできる言語で行こう」と,急遽予定に組み入れた.

といってもボクもほとんど知らない言語だ (というか,プログラミング自体の経験も浅い) .まずはこちらの文献集にあった,まつもとの「rubyユーザガイド」 (ちょっと古い; また,初心者である自分にはあまり分かりやすくなかった) と Chris Pine の「プログラミング入門: Rubyを使って」(大部分は初心者でも読めるだろうけど,9章の後半と10章はむずかしそう) をざっと読んだ.プログラミングをはじめてからは,その文献集の「入門編」の「サイト」にある情報や,「オブジェクト指向スクリプト言語 Ruby リファレンスマニュアル」その他を参照した.

プログラミングに出した課題はこんなタイプの問題だ: 「カップ 0, 1, 2 はそれぞれ 10, 7, 3 の容量を持つ.最初は容量10のカップに水が満杯の状態 [10, 0, 0] である.カップ i から j への水の移し替えを繰り返して,目標である [5, 5, 0]を実現したい.」この例にかんするかぎりは,9段階の移し替えで目標が達成できることが,すべての場合を網羅的に調べることで手作業で確認できる. (上述の科目で少し学ぶ) グラフ理論を知っていれば,この種の問題をプログラムで扱えるように表現するのは簡単だろう.アルゴリズムを考えることもたやすい.

それでもはじめての言語というのはいろいろと戸惑うものだ.ありがちなミスのパタンは,マニュアルと悪戦苦闘したり試行錯誤を繰り返すうちにだいたい分かって来た.で,できあがった最初のプログラムは,9段階の移し替えを実行するだけで 5 時間もかかり,10 段階以上は結果を出せなかった.そんなバカな! 「オブジェクト指向でプログラムを書いたのが悪かったんだろうか?」「再帰で関数を定義したのが悪かったんだろうか?」などと疑った.Mac OS X にはじめからインストールしてあった ruby がたまたま当たりが悪いバージョンなのかもしれないと思って,最新安定版 1.8.6 に入れ替えたり,クリスマスにリリースされたばかりの「高速」不安定版 1.9.0 を (一年近く触れていなかった) Windows PC にインストールしたりもした.だがそれらの対処法はいずれも見当違いだった.

ところでMac OS X に ruby 1.8.6 をインストールするのには,MacPorts を使った.これはボクにとっては前進だ.Unix ふうというだけでいままで毛嫌いしてたけど,やってみたらたいしたことはなかった.最初の導入は多少面倒だけど,こいつをいったんインストールしておけば,ほとんどの unix 向けソフトがコマンド 1 行でインストールできるようになる.そういうソフトとしては,pTeX, Octave, Maxima などがある.可能性が一発で広がるわけだ.こちらのサイトも参考になるだろう.MacPorts を使えるようになったのは,失敗から生まれた収穫といえるだろう.

では,なにがプログラムをそんなに遅くしていたのか? どうやら関数の相互参照であるようだ.たとえば history(t) という関数を定義するのに history(t-1) と obtained(t-1) を参照する一方で,obtained(t-1) を定義するのに obtained(t-2) と history(t-1) を参照するようになっていた.数学的には問題はなさそうだが,おそらくプログラム的には問題になるんだろうな.history(t) の定義のなかに使われていた関数 obtained(t-1) を単なるローカル変数に置き換えた.するとそれまで5時間かかってもできなかった計算が,1秒程度でできるようになった! やれやれ.

「関数を変数に置き換えた」とあっさり書いている.「そんなに簡単にできるならはじめから変数で書けばいい」と思うだろう.実際そのとおりなんだろうけど,これは慣れあるいは経験の問題かもしれない.[以下,インデント部分に修正を加えた.追記参照.] たとえば 1 から 10 の整数 i を合計するプログラムでは s = s + i などと書いて,右辺の値の左辺の変数への代入を表すけど,数学ではふつうそうはやらない.添字をつけて si = si-1 + i とするか,関数にして s(i) = s(i-1) + i とやりたくなるわけだ.添字をつけて何段階目の更新かというのをはっきりさせるわけだ.そういう癖にしたがって書いたプログラムが (メモリを浪費せず,かつ素早く) 自然に動いてくれたほうが都合いいと思ってるアマチュアプログラマはけっこういるかもしれない.

ところで数の合計といえば,はじめに s = 0 と設定して(1..10).each do |i| とやるのがただしいが,ボクがはじめのころ書いたプログラムには (1..10).each do |i| と書いたあとに s = 0 とする類いの初歩的なミスがあった.(これだと合計は 55 ではなく 10 になってしまう.) さすがに合計を求めるだけのプログラムではそういうミスはしないだろうけど,ループとか条件が何重かにネストする,より複雑なプログラムだと,意外とおかしてしまうミスかもしれない.

それにしても「おまじない」の類いをほとんど記述せずにプログラムが書けるのは気持ちいい.できたプログラムは普通に書くアルゴリズムよりもむしろ簡単かも.たとえば (?) 上記の水移し問題 (油移し問題) のインスタンスである abura にたいする結果を表示する---より具体的にはその履歴 history(t) を t = 0 から t = 12 まで表示する---には,以下のように書けばいい:

(0..12).each do |t|
p abura.history(t)
end

追記 (1/10/2008). あまりにも単純すぎてポイントが伝わらなかった例を差し替えた.以下は修正前の記述.「プログラムでは x = x + 1 と書いて,右辺の値の左辺の変数への代入を表すけど,数学ではふつうそうはやらない.わざわざ添字をつけて xt = xt-1 + 1 とするか,関数にして x(t) = x(t-1) + 1 とやりたくなるわけだ.(この例は簡単すぎるので説得力ないけど,もっとむずかしくなると添字をつけて何段階目の更新かというのをはっきりさせた方が分かりやすくなる例は少なくないはずだ.)」

【2008/01/08 20:44 】
| プログラミング | コメント(2) | トラックバック(1) |
<<最短路問題,グラフ描画,家系図 | ホーム | 年末は家具の入れ替えとか順序数とか>>
コメント
Ruby1.8でしたら Enumerable#injectを用いて漸化式をすっきり書けますね。

(1..10).inject(0){|r,x| r+x } => 55
【2008/12/03 19:24】
| URL | tenfu #I9hX1OkI[ 編集] |
上記命令を試してみました.Thanks.
マニュアルによれば,
p [1,2,3,4,5].inject(0) {|result, item| result + item }
=> 15
のように使うそうですね.しかしめったにプログラミングしない自分には必要ないコマンドかも.笑

【2008/12/05 20:43】
| URL | 平凡助教授 #4TQqPKZU[ 編集] |
コメントの投稿











管理者にだけ表示を許可する

トラックバック
トラックバックURL
http://theorist.blog6.fc2.com/tb.php/145-8e0dba48
【オペレーションズリサーチ】についてのお得なブログリンク集
オペレーションズリサーチ に関する最新のブログ検索の結果をまとめて、口コミや評判、ショッピング情報を集めてみると… 旬なキーワードでお得なブログのリンク集【2008/01/14 04:33】
| ホーム |
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。