なるほど。なんつーか、さすが Windowsって感じ。
UNIX にしても別の点じゃ似たようなもんですかね。
あーもう、なんで Libretto はこんなに弱っちいのだ！ なにかって言うとファンをガーガー回してさ、 いきなり固まるしさ、いきなりリブートするしさ、 いきなりコンソールのカーソルが消えるしさ！ 特に Me で Cygwin 使うのがよろしくないようだ。
まあそれ以外でもガンガン固まるんだけどさ。見境なく。 Sleipnir でタブを 20 枚くらい開くとたっぷり 1 分は戻ってこないね。 そういうときに迂闊にスクロールさせたりするともうだめよ。即死よ。 いくらなんでも弱すぎじゃない？
久しぶりに ReFe をバージョンアップしました。
-withdocsrc はリファレンス全部と Ruby のソースコードのデータベースを入れたもの。 -withdoc はリファレンスのみ。無印は ReFe 本体だけ。全ファイルのリストは次のとこ。
それにしても、この程度の変更でこんなに時間使っちゃだめだよなあ。
ユニットテストが全然動かないな。 最初のが 1.6 で動かないのは単なる手抜きだけど、 いま直したので動くはず。 うーん、家の RubyUnit が古いのかなあ。
そうでもないな。 TestUnit の RubyUnit 互換インターフェイスが間違ってるようだ。 RUNIT::TestRunner.new の引数がない。
まあいいや。このさい TestUnit に移行することにしよう。
そっか、四月の頭だから普通の人は忙しいんだ。
なんと A4 15 ページにもおよぶ Unix の系譜図が！ 最後のほうは線の間隔が狭すぎて五線紙状態 (笑) さっそく印刷しますた。
しまった、大文字小文字を区別しないファイルシステムのことは考えてなかったー！ どうしよう。黙って大文字を全部エスケープするしかないか。 それとも -A にしようかなあ……うん、そのほうがいいな。そうしよう。
他に、refe -C data wrap で Data Wrap Struct が出ないという問題もありました。 こっちは検索ルーチンの間違い。
別のデータベースもいちおう用意してあるんですけどね。 そっちは AMarshal と同じで、 Ruby のソースコードとして格納して eval します。 ただし 10 倍くらい遅いです。
うわあ、なんかエスケープ周りがバグバグしてるよう。 これはグロブパターンを真面目にパースしないとだめだな。
あ。それどころじゃねえや。 一文字が複数文字になるだけでまずいんだ。 '?' とかキャラクタクラスが全然動かなくなる。
やっぱり検索ルーチンは自前で書かないとだめか。 さようなら 10 倍速。考えが甘かった。
メール出し忘れてた。
消える前に「バカが征く」ミラー (もう消えたけど)。
無闇に遅延初期化っつーのはどうかと思います。
def getFoo
if @foo.nil?
@foo = createFoo
else
@foo
end
end
こういうの。初期化しておくんならコンストラクタとかでやっとくのが本道じゃ
ないですかね。計算に時間がかかるとかがあれば別でしょうけど。
想像してみると、確かに initialize で初期化するほうがよいような気がします。 ではそれはなぜ「本道」なのかをできるだけ論理的に考えてみました。
まず、そういうもんだって言えば確かにそうです。 コンストラクタって言うくらいなんだからデータ構造を作るのに使うべきでしょう。 また読むほうもコンストラクタにはそういう役割があるだろうと期待しているので、 その期待に沿って書いたほうが読みやすいと感じるはずです (消極的な理由)。
またもう一つ、動的な構造をソースコードから想像するのが簡単になるという点が 挙げられます。データ構造を理解するのはコード読みの中でも根幹にあたりますから、 データ構造を想像しやすいコードは読みやすいでしょう。 従ってインスタンス変数はコンストラクタで初期化すべきです (積極的な理由)。
Ruby のように変数型のない言語では第二点は特に重要です。 変数が型ありの場合は、コンストラクタで代入していなくとも 変数定義さえ上のほうにあれば何が入るのかはとりあえずわかるからです。
逆に言うと、変数に型のない言語で読みやすいコードを書こうと思うと コンストラクタだけでデータ構造がわかるようにするほうがよい、 そうするように矯正される。かもしれません。単にわかりにくいコードに なるだけかもしれません。
ちなみに Ruby で遅延初期化をするときは次のように書くのが簡潔です。
@ivar ||= make_object()
また ||= を使う場合に限り @ivar を初期化していなくても警告が出ません。
~/c/tmail % ruby -vwe '@ivar = 0 unless @ivar' ruby 1.8.0 (2003-03-28) [i686-linux-gnu] -e:1: warning: instance variable @ivar not initialized ~/c/tmail % ruby -vwe '@ivar ||= 0' ruby 1.8.0 (2003-03-28) [i686-linux-gnu]
ただしこれはモジュール関数の中などでやむなく遅延初期化せざるを 得ない状況を救済するためではないかと思われます。
# 例
module FileUtils
module_function
def verbose_output( msg )
@output ||= $stderr # initializeが使えないので遅延初期化できない
@output.puts(msg)
end
end
そうだ、initialize はクラス定義の最初に置くべきでしょう。 最初のころは「private だから」つーことで一番下に書いてたんですが、 前述のような理由を考えると initialize が先頭にないとまず意味が ありません。せっかく initialize が自動的に private になるように なってるんだから、その機能を活用しましょう。
あ、でもクラスの特異メソッドは initialize より前に置いてます。
include はいまだにブレがあるんですが、 だいたいクラス定義文の冒頭か initialize の直前ですかね。 冒頭に置く理由は「スーパークラスの記述と近いから」で、 initialize の前に置く理由は 「include はインスタンスメソッドの記述 (のショートカット) だから」です。 だから一部でしか使わないメソッドのために include するときは 例外的にその直前で include する場合もあります。
require はファイル先頭。 最初の最初にファイル間の関係を理解するとき、 require が先頭にないと理解しづらいです。
■ ささだ [私は、遅延評価のことを忘れてしまったりすることが多多あるため、initializeで初期化します。require は、メソッドの中に書いちゃうことが結構あるんですが ^^;]
■ ただただし [じゃあ、「遅延初期化は最後から一個前の武器だ」ってことで。]
■
あおき [とか言いつつも遅延初期化使いまくってますけどね、ぼくは。
今日の話題は自戒を込めて書いてみました ^^;;;]
■ はら [attr_ 系は initialize の前ですかね。]
■
moriq [おお。タイムリー。
昨日このようなコードを書きました。
module DateOld
def roku
@roku = ほにゃほにゃ
instance_eval {
def self.roku
@roku
end
}
@roku
end
end
でも、こう書いたほうがいいですね。
module DateOld
def make_roku
ほにゃほにゃ
end
def roku
@roku ||= make_roku
end
end]
■ moriq [あ、でも make_roku は nil になることがある(@roku=nilでrokuは以後nilを返す)ので @roku ||= make_roku は採用しにくいな。]
すんごく間が空いたけど Haskell grep。 引数からファイル読むのは面倒なので stdin しか対象にしません。
module Main (main) where
import System
import IO
import Text.Regex
main :: IO ()
main =
do
args <- getArgs
doGrep $ mkRegex (head args)
doGrep :: Regex -> IO ()
doGrep re =
do
cs <- getContents
mapM_ (\line -> case matchRegex re line of
Just _ -> putStrLn line
Nothing -> return ()) (lines cs)
うーむ、ARGF が欲すい。
最近の Haskell にはライブラリが二種類ある。 主な違いはレイアウトで、新しいライブラリは階層化されている。 これを階層化ライブラリ (hierarchical library) と言う。
GHC はデフォルトで階層化ライブラリを使う。 Hugs はデフォルトで古いライブラリを使う。 Hugs で階層化ライブラリを使いたいときは runhugs +N とする。
いつもどおり
軟派な PC パーツショップは素通りして末広町方面に向かいます。
……
ごめんなさい
嘘です。
ちょっとだけ寄りました。
Matrox のレイテストなヴィデオカード 「ぱへりあ」が見たかったんです。
あ、
ちょっとだけ Otto 5F (UNIX本舗) も見ておきましょう。
ところで
高いから買わないけど
PC サーバ屋には
なぜかときどき
Alpha が置いてあります。
Sun や hp は絶対に置いてないのに
Alpha だけあるんです。
どうしてでしょう？
どうやったら Alpha が PC サーバに見えるんですか？
もしかして
PS/2 端子が付いてたら全部 PC サーバですか？
と言うわけで
なぜか
SparcStation5 が手元にあるんですが
どういうことですか？
いくら半額セールだからって
いくら 2415 円 (税込) だからって
いまさら SparcStation5 はないんじゃないですか？
MicroSPARC ですよ？
sun4m ですよ？
Solaris 9 でサポートが切られると一瞬噂になった sun4m ですよ？
しかも
その 2415 円 (税込) ですら所持金ギリギリで
電車賃が 10 円足りないというのは
どういうことですか？
ああ
あのときチチブデンキの前で生茶さえ買わなければ。
そう思っても後の血祭りです。
……
狙って外したギャクは寒いです。
幸い (fortunately,)
御徒町から乗ると電車賃が 30 円下がります。
ただし
SS5 は
重いです。
MicroSPARC は
伊達じゃないんです。
不幸にして (unfortunately,)
カートなんて便利なもんは
持っていきませんでした。
今日は絶対に買わないぞ！ なんて決意して
カートを持っていかなかったんです。
でも
買わないでいられるはずが
ないじゃないですか。
現実を見ればよかったんです。
ていうか
金持ってけよ。
(唐突に完)
Linux の Flash6 プラグインを入れてみた。 インストールはあっという間に終了したので about:plugins で確認。
動いてない……。なんでだろう。
~ % ldd /usr/mozilla/plugins/libflashplayer.so aamine@harmony
libpthread.so.0 => /lib/libpthread.so.0 (0x4022d000)
libdl.so.2 => /lib/libdl.so.2 (0x40241000)
libz.so.1 => /usr/lib/libz.so.1 (0x40245000)
libX11.so.6 => /usr/X11R6/lib/libX11.so.6 (0x40253000)
libXext.so.6 => /usr/X11R6/lib/libXext.so.6 (0x402ef000)
libXt.so.6 => /usr/X11R6/lib/libXt.so.6 (0x402fa000)
libstdc++-libc6.2-2.so.3 => not found
libm.so.6 => /lib/libm.so.6 (0x40341000)
libc.so.6 => /lib/libc.so.6 (0x40362000)
libSM.so.6 => /usr/X11R6/lib/libSM.so.6 (0x40484000)
libICE.so.6 => /usr/X11R6/lib/libICE.so.6 (0x4048d000)
/lib/ld-linux.so.2 => /lib/ld-linux.so.2 (0x80000000)
犯人は貴様か！
なんだよ libstdc++-libc6.2-2.so.3 って。
~ % ls /usr/lib/libstdc++* /usr/lib/libstdc++-libc6.1-1.so.2 /usr/lib/libstdc++.so.2.8.0 /usr/lib/libstdc++.a /usr/lib/libstdc++.so.2.9 /usr/lib/libstdc++.a.2.10.0 /usr/lib/libstdc++.so.2.9.0 /usr/lib/libstdc++.la /usr/lib/libstdc++.so.27 /usr/lib/libstdc++.so /usr/lib/libstdc++.so.5 /usr/lib/libstdc++.so.2 /usr/lib/libstdc++.so.5.0.2 /usr/lib/libstdc++.so.2.8
当然ないですな。 てけとうにシンボリックリンクを張っておこう。
~ % cd /usr/lib /usr/lib % sudo ln -s libstdc++.so.5 libstdc++-libc6.2-2.so.3
動いた。解決したようだ。
花見しに大阪へ行ってきます。 往復に高速バスを使って安くあげようと思ったのに切符が取れなかったので、 ヤケになってのぞみを使うことにしました。一度乗ってみたかったんだ。
たらいまわし関数と Haskell の話の続きです。 3/23 の原先生のツッコミより。
> 非正格ってnon-strictの訳ですよね。 > この「non〜」っていう用語が不思議な気がします。 > 非正格ならこのような最適化を必ずするのでか？ > それともこれは最適化ではなく、非正格なら自動的に > そういう計算の仕方をしてしまうのでしょうか。
必ずするわけじゃないと思います。 ぼくも勉強中なんであんまり深いことは言えませんが、 山下さんの受け売りで説明してみます。
Ruby で次のような式を計算すると、
f(g(1), g(2))
まず引数の g(1) と g(2) を計算して、それを f に渡します。 しかし Haskell では式のどこから計算されるかが決まっていません。 つまり f を展開してしまったあとに g(1) や g(2) を計算できます。
結果として次のようなことが起こります。Ruby で以下のような関数を書くと、 g(1) か g(2) どちらかの計算時間が必ず無駄になります。
def my_if( cond, t, f )
if cond
t
else
f
end
end
p my_if(true, g(1), g(2))
しかし Haskell だと先に my_if を展開してしまうことができるため、 g(1) と g(2) のどちらかは無駄になることがあらかじめわかるんです。 だからまず cond だけ計算してみて、 その後で t か f のどちらかだけを求めるということができます。 つまり g(1) か g(2) のどちらかはそもそも計算されずに終わります。 たらいまわし関数の計算が速いのはこのようなことが各所で起こるからです。
具体的に見てみると、
tarai :: Int -> Int -> Int -> Int
tarai x y z
| x <= y = y
| otherwise = tarai (tarai (x-1) y z)
(tarai (y-1) z x)
(tarai (z-1) x y)
三行目は「x <= y の場合は y」と記述しているんですが、 この場合 z は関係がありません。つまりそもそも計算しなくてよいわけです。 だから Haskell で計算するとかなり計算量が減って速くなるという仕組みです。
ところが John McCarthy が間違ったバージョン (竹内関数) では
tak :: Int -> Int -> Int -> Int
tak x y z
| x <= y = z
| otherwise = tak (tak (x-1) y z)
(tak (y-1) z x)
(tak (z-1) x y)
となっていて、x <= y のときは z を返すことになってます。 だからどの場合でも z の計算は省略できません。 結果として non-strict だろうが strict だろうが同じ計算量になるわけです。
■
笹川 賢一 [先日のSICPではどうも。
TAKyとTAKzがあるんですね。知らんかったです。Mathematica計算の楽しみ（ヴァルディ）に実行時間の話があるけど、当方難しくて理解不能。原始帰納的関数ではないけど計算可能なのか？
Hugsでやってみたら tak 12 6 0 の結果は１だった。SMLでやると１２になる。なぜ？？？]
■
笹川 賢一 [すみませ〜ん。tarai(TAKy)とTak(TAKz)を取り違えてました。
非正格も正格も同じ計算結果、しかしHaskellの方がダントツに速い。]
■
なかだ [なるほどねぇ。さすが言語レベルで遅延評価をサポートしてると違いますね。
class Tarai
include Comparable
def initialize(x, y, z)
@x, @y, @z = x, y, z
@t = 0
end
def tarai_inspect(level = 3)
return "?" if (level -= 1) < 0
s = "Tarai(" <<
[@x, @y, @z].map {|x| Tarai === x ? x.tarai_inspect(level) : x}.join(", ") <<
")"
s << ("%#d" % @t) unless @t.zero?
s
end
def +(val)
@t += val
end
def -(val)
@t -= val
end
def <=>(val)
to_int() <=> val.to_int
end
def coerce(val)
case val
when Integer
[val, to_int()]
else
super
end
end
def to_int
@t += if !@x
0
elsif @x <= @y
@y
else
Tarai.new(Tarai.new(@x-1, @y, @z),
Tarai.new(@y-1, @z, @x),
Tarai.new(@z-1, @x, @y)).to_i
end
@x = nil
@t
end
alias to_i to_int
def to_s
to_i.to_s
end
end
if $0 == __FILE__
a = 12, 6, 0
ARGV.each_with_index {|v, i| a[i] = v.to_i}
t = Tarai.new(*a)
puts "#{t.inspect} = #{t}"
end]
■ はら [あ、なるほど。最適化じゃなくて、引数に対する遅延評価なんですね。]
■
はら [こうすると Ruby でもそれっぽくなるかな。
class Integer
def call; self; end
end
class Proc
def -(x); proc{call - x.call}; end
end
def tarai( x, y, z )
if x.call <= y.call
then y.call
else
tarai(proc{tarai(x-1, y, z)},
proc{tarai(y-1, z, x)},
proc{tarai(z-1, x, y)})
end
end
puts tarai(12, 6, 0)]
12:10
大阪は森ノ宮に着きましたー。全国何処にでもある漫画喫茶から書き込んでます。
しかしのぞみは速いですね。さすがに線路の幅が太いだけのことはあります。
あ、そう言えば帰りの時間を書いてませんでした。明日日曜の深夜に高速バスで帰ります。これに伴い月曜まで反応が止まりますのでよろしく。
■ (う) [到着早過ぎ! ^^;]
17:02
あー、漫画喫茶って本当にどこでもありますね。
昨日は楽しかったです。ちょと寒かったですね。今日は暑すぎ。
まとめは柳川さんとSheepmanさんがあらかたかいてくださったようなので省略ー。Crayのガワだけでも欲しいなあ。
そだ、夜は無事ホテルに泊まれました。5800円でした。出たとこ勝負はうまくいったようです。ご心配おかけしました。
奈良に行ってきました。時計落とすわ、ドブにはまるわで泣きそうです。
日本橋にも行きました。最初はカニのあたりに行ってしまったりしたものの、何とかたどり着きました。しかし当然ながら店が全然わかりません。ワークステーションは見かけませんねえ。OEMのUltraとかCiscoルータを見かけたくらいでしょうか。それにもう足が痛くて痛くて…。法隆寺から王寺まで歩いたのはまずかった。
■
kjana [あら残念．今日みたところでもちゃんといろいろありましたのに．
「わんだーらんどの上」だけじゃ説明としては弱すぎだったか．
SUN Ultra Enterprise 3000 が増えてたな．4way SMP．]
関西行きは思ったよりこたえてたようです。 月曜にうっかり眠りこんだら火曜の午後まで 一瞬たりとも目醒めませんでした。
でまあ、記憶力が激烈にいいかたなら覚えているかもしれませんが、 先週 AlphaStation500 を確保してきたのでした。 それを受けとってきました。昨日。紺匡体ですよ紺匡体。 この型は [d|i|g|i|t|a|l] のロゴもきれいでいい感じ。
内部はバコバコとパーツが外れていくギミック満載でかなり萌えます。 このへんはいずれゆっくり写真付きページで。
OS は NetBSD にしました。いいっすね、NetBSD。 /etc/rc.conf 設定しないとシングルユーザモードに叩き落とすし。 inetd が動いてると思って油断したら一つもポートが開いてないし。 telnet して su しようと思ったら「wheel じゃないとダメ」って言われるし。 この偏屈さがいい感じだ。
メインマシンを新しくしました。というか、 いままで Linux と Windows 2000 のデュアルブートだったのを 二台に分割したついでにマシンをアップグレードしたんです。
というわけで自己満足スペック自慢
[Linux]
CPU・マザーボード・チップセットを Intel 固め。 秘かに Intel は好きです。AMD 嫌いです。
メモリ 1GB。使っても使っても余る。 正直、こんなにいらないっす。
HDD は IBM を見捨てて Seagate に流れました。 だって、だって、日立だよ日立！？ そんなもんを俺のメインマシンに入れてたまるかー！
サウンドだの CD-R だのと言ったヌルいデバイスは付けてません。 と言いたいところですがサウンドはオンボードです。ちっ。
ビデオカードがいまさら TNT2 なのは使いまわしだからです。
一番高いパーツはケース。 総アルミ製で 4 まんえんでした。
速度はあんまり変わったような気がしません。 ディスク I/O が速くなるとハッキリわかるんですが、 CPU が速くなるだけでは相当の速度差がないとわかりません。
あっ、Racc が速くなってる！ Ruby の parse.y を処理する時間が 8 秒から 4 秒になりました。 ますます高速化の意欲が薄れます！
ところで何か忘れてるような気がしてると思ったらフロッピードライブを 付けていませんでした。いいかげんいらないかなあ、とも思ったんですが、 昨日 NetBSD/Alpha のブートフロッピーを焼くのに使ったばっかりなので 必要ないとも言えません。
ついでにぷらっとほーむの PShare Ex を買ってきました。 モニタとキーボードとマウスを一括して切り替えられるってやつですな。 Linux と Windows 2000 が分かれたのが動機です。 ワークステーションとかサブの Linux マシンが増える分には ssh だけで 済むんですが、Windows が増えてしまうとどうにもなりません。
どうも KVM スイッチにはかなり当たり外れがあるらしく、 安物だとそれなりに玉砕するみたいです。 んで、いろいろ含めて評判がいいのは主に以下の二つ。
そのかわり値段も高いです。PShare Ex は 約 3 万円でした。
次回は使用レポート。
金使いすぎ。
ああそうそう、NetBSD/Alpha ですけど。 あまりに簡単にインストールできたんで拍子抜けしました。 特に書くこともないくらい。 インストーラがよくできてるってことでしょう。
ブザーが鳴るのは嫌いなのでずっとコード自体を外してるんですけど、 なんと今回のマザー (とケース) はコードを外してもブザーが鳴ります。 どこで鳴らしてるのか知らないけど、余計なお世話です。
端的に言って、かなりよいです。 以下の構成で何の問題もなく使えてます。
[共有デバイス]
[1号機]
[2号機]
「Ctrl 2 回」「Ctrl + Alt + Shift」「Scroll Lock 2 回」 のいずれかで切り替えモードに入り、さらに「数字 + Enter」で切り替え。 それぞれ有効無効も設定できるので安心です。 Emacs を使う人は「Ctrl 2 回」はオフにしといたほうがいいかも。
一番心配だったのはリフレッシュレート 85Hz だったんですが、 とりあえず問題ないようです。でもケーブルには「1600x1200 75Hz」 と書いてあるので本当はまずいのかもしれません。 でももしかしたらあれは「最大 1600x1200 75Hz」ということで、 解像度を下げればリフレッシュレートは上げてよい、 ということかもしれません。まあ、動いたんでよしとします。 85Hz と 75Hz は肉眼でも判別できてしまうので、 ちょっと 75Hz で使う気はしません。
画像も、切替器を入れる前と区別が付きません。 あ、これは元からモニタ切替器を使ってたからかな。 いずれにしてもテキストがくっきり読めるレベルですし、ゆがみも出ていません。
もちろんキーボード・マウスも正常動作してます。うーん、これはいい。 3 万円は高かったけど安定動作には変えられません。 きっちり動いてくれれば可です。
あ……？ 明日か！ うわあ、今日は木曜日だとばっかり思ってたよ。
大阪花見、なぜか一週間すぎた今になって思い出したように記録が出てますね……。 今日の RHG 読書会で出た話も合わせていろいろ書いてみます。
stdio を捨てるのはやっぱし 1.9 みたいです。 必然的に Windows の gets + スレッド問題も 1.9 で解決しそうですね。
鬼車も 1.9。 「regex.c でバグを見付けても鬼車で再現しないとどうでもいいような気がする」 という声がありました。
いろんなところで何度も出てる話ではあるけども、 やっぱり Ruby プログラムをパースするのは大変すぎます。 たとえば ruby-mode.el や irb はかなり苦労しているようです。 パーサが公式にモジュール化されるのは 2.0 ですから、 それまではどうにかしなければなりません。 Ripper みたいのを自動生成できると楽なんですけど……。
やっぱり tk 関係はディレクトリに入れたいよね。 という話を無理矢理してきました。
この話も含めて、1.7 では lib/ 以下にいろいろ入るので、 その分これよりも気を遣ってやる必要が出てきそうです。 「readbytes.rbなんていらねえだろ」とかいう話もありました。
オプション渡しを全面的にハッシュにする決意を固めました。 近日中にパッチ書いて ruby-dev ML に流します。 どうせまだ 1.7 にしか入ってないので互換性は一切考慮しません。 ちなみに instruby.rb だけはこっちで追従させときますので。
あーそうだ、パーサジェネレータ標準添付してほしい、ってのもあったなあ……。 いる？
http://sheepman.parfait.ne.jp/20030418.html#p05
あ、sheepman さんのところに派生してる。
うーむ、おかしいなあ。 家だと lambda 使って遅延評価しても Hugs のほうが速いです。 GHC でコンパイルするとさらに激速。
~/c/test/haskell % cat lazy-tarai.rb
def tarai( x, y, z )
if x.call <= y.call
then y.call
else tarai(lambda { tarai(lambda{x.call-1}, y, z) },
lambda { tarai(lambda{y.call-1}, z, x) },
lambda { tarai(lambda{z.call-1}, x, y) })
end
end
puts tarai(lambda{48}, lambda{24}, lambda{0})
~/c/test/haskell % cat tarai.hs
module Main where
main :: IO ()
main = do
print (tarai 48 24 0)
tarai :: Int -> Int -> Int -> Int
tarai x y z
| x <= y = y
| otherwise = tarai (tarai (x-1) y z)
(tarai (y-1) z x)
(tarai (z-1) x y)
~/c/test/haskell % time ruby lazy-tarai.rb
48
ruby lazy-tarai.rb 0.44s user 0.00s system 104% cpu 0.419 total
~/c/test/haskell % time runhugs tarai.hs
48
runhugs tarai.hs 0.07s user 0.00s system 148% cpu 0.047 total
~/c/test/haskell % ghc -O -o tarai tarai.hs
~/c/test/haskell % time ./tarai
48
./tarai 0.00s user 0.00s system 0% cpu 0.000 total
つーか、GHC は速すぎだなあ。 定数畳み込みされてるのかと思ったんですが、 引数を大きくすると実行時間も増えていくところからすると ちゃんと計算しているようです。
3/22 の原先生の返り値をキャッシュするバージョンでも、 引数を (96,48,0) にすると Hugs に負けます。
~/c/test/haskell % time ruby memo-tarai.rb 96 ruby memo-tarai.rb 0.40s user 0.00s system 101% cpu 0.394 total ~/c/test/haskell % time runhugs tarai.hs 96 runhugs tarai.hs 0.10s user 0.00s system 107% cpu 0.093 total
ようするに、こないだのでは引数が小さすぎると。
改めて見ると今週はすごい流量が少ないな。 _vsnprintf の話は結局結論が出てないっぽいし、 bigdecimal 関係だけか。まあこういう週もあるやね。
■
shiro [lambdaだけでは計算量が完全な遅延評価ほど減らないように思います。
http://www.shiro.dreamhost.com/scheme/wiliki/wiliki.cgi?Scheme:たらいまわしべんち]
■
shiro [おっと。リンク失敗しました。ごめんなさい。
http://www.shiro.dreamhost.com/scheme/wiliki/wiliki.cgi?Scheme%3a%a4%bf%a4%e9%a4%a4%a4%de%a4%ef%a4%b7%a4%d9%a4%f3%a4%c1&l=jp]
■
ささだ [原先生版のは配列生成のコストが結構ありそうな予感．あと，コンパイルによる最適かもあるんでしょうね．
配列生成は，tarai(96,48,0) なので，[x,y,z] が 35K 作られる．なら，作らないようにしよう．
というわけで，
$memo = {}
def tarai2( x, y, z )
getv(x,y,z) || putv(x,y,z)
end
def getv x,y,z
($memo[x] && $memo[x][y] && $memo[x][y][z])
end
def putv x,y,z
r = if x <= y
y
else
tarai2(
tarai2(x-1,y,z),
tarai2(y-1,z,x),
tarai2(z-1,x,y))
end
x = $memo[x] ||= {x=>{}}
#p x
y = x[y] ||= {y=>{}}
#p y
y[z] = r
end
=>
0.734000 0.000000 0.734000 ( 0.750000) # 原先生
0.375000 0.000000 0.375000 ( 0.391000) # 今回の
しかし，われながらダサい．]
■
はら [体裁を気にせずスピードを求めるなら：
def tarai( x, y )
if x <= y
then y
else
z = yield
tarai(tarai(x-1, y){z}, tarai(y-1, z){x}){ tarai(z-1, x){y} }
end
end
puts tarai(192, 96){0}]
しつこくたらいをまわしてみる。
うーむ、原先生ファイナルバージョンがかなり速いですねえ。 第三引数だけ遅延評価するとは凄いアイデアです。
ただ、やっぱりそれでも引数をデカくすると Hugs に負けるんですよー。
~/c/tarai % time ruby yield-tarai.rb aamine@harmony 768 ruby yield-tarai.rb 2.20s user 0.01s system 101% cpu 2.187 total ~/c/tarai % time runhugs tarai.hs aamine@harmony 768 runhugs tarai.hs 2.13s user 0.01s system 101% cpu 2.118 total
これは (768,384,0) で試した場合で、引数を倍にするともっと差が広がります。 笹田さん版も同じですね。 やはりどうやっても完全な遅延評価をしている Haskell 版には敵わないようです。
ちなみに笹田さんの多段ハッシュ版は次のように書いたほうが短くて速いです。
$memo = {}
def tarai( x, y, z )
(($memo[x] ||= {})[y] ||= {})[z] ||= tarai0(x,y,z)
end
def tarai0(x, y, z)
if x <= y
then y
else tarai(tarai(x-1,y,z),
tarai(y-1,z,x),
tarai(z-1,x,y))
end
end
puts tarai(768, 384, 0)
~/c/tarai % time ruby mhash-tarai.rb # 笹田さんのオリジナル
768
ruby mhash-tarai.rb 15.21s user 0.25s system 100% cpu 15.452 total
~/c/tarai % time ruby mhash-tarai2.rb # 青木改良版
768
ruby mhash-tarai2.rb 10.41s user 0.08s system 100% cpu 10.487 total
また負の整数がないと考えてよいのなら 配列を使うとさらに高速化できます。
$memo = []
# x だけは -1 になることがあるので +1 しておく。
def tarai( x, y, z )
(($memo[x+1] ||= [])[y] ||= [])[z] ||= tarai0(x,y,z)
end
def tarai0(x, y, z)
if x <= y
then y
else tarai(tarai(x-1,y,z),
tarai(y-1,z,x),
tarai(z-1,x,y))
end
end
puts tarai(768, 384, 0)
~/c/tarai % time ruby mhash-tarai3.rb aamine@harmony
768
ruby mhash-tarai3.rb 8.15s user 0.09s system 100% cpu 8.230 total
まだ「第三引数のみyield」には敵わないものの、かなり速くなりました。
C の力任せに計算するやつが Ruby memo 版にすら負けているのが気にくわなかったので、 C でも多次元配列に計算結果をキャッシュするようにしてみました。
#include <stdio.h>
#include <stdlib.h>
#define K1 192
#define K2 96
#define K3 0
static int tarai(int, int, int);
static inline int tarai0(int, int, int);
static void initialize_cache_table(int);
#define max3(a,b,c) max(max(a,b),c)
#define max(x,y) ((x) > (y) ? (x) : (y))
int
main(int argc, char **argv)
{
initialize_cache_table(max3(K1, K2, K3) + 2);
printf("%d\n", tarai(K1, K2, K3));
exit(0);
}
static int *cache;
static int table_width;
static void
initialize_cache_table(int width)
{
int i, j, k;
table_width = width;
cache = malloc(width * width * width * sizeof(int));
if (!cache) {
fprintf(stderr, "malloc failed\n");
exit(3);
}
for (i = 0; i < width; i++) {
for (j = 0; j < width; j++) {
for (k = 0; k < width; k++) {
cache[(i * width * width) + (j * width) + k] = -2;
}
}
}
}
static int
tarai(int x, int y, int z)
{
int result;
int key;
int w = table_width;
key = ((x+1)*w*w) + ((y+1)*w) + (z+1);
result = cache[key];
if (result != -2)
return result;
result = tarai0(x, y, z);
cache[key] = result;
return result;
}
static inline int
tarai0(int x, int y, int z)
{
if (x <= y) return y;
return tarai(tarai(x-1, y, z),
tarai(y-1, z, x),
tarai(z-1, x, y));
}
これもかなり速かったんですが、キャッシュの密度が粗すぎるため、 (768,384,0) では malloc() が失敗してしまいました。がくり。
やはり多次元配列では芸がなさすぎました。 イリッフィベクタにしてみます。
#include <stdio.h>
#include <stdlib.h>
#define K1 768
#define K2 384
#define K3 0
static void *new_cache(void*);
static int tarai(int, int, int);
static inline int tarai0(int, int, int);
#define max3(a,b,c) max(max(a,b),c)
#define max(x,y) ((x) > (y) ? (x) : (y))
void **cache;
int cache_size;
int
main(int argc, char **argv)
{
cache_size = max3(K1, K2, K3) + 2;
cache = new_cache(0);
printf("%d\n", tarai(K1, K2, K3));
exit(0);
}
static void*
new_cache(void *val)
{
void **p;
int i;
p = malloc(sizeof(void**) * cache_size);
if (!p) {
fprintf(stderr, "malloc failed\n");
exit(3);
}
for (i = 0; i < cache_size; i++) {
p[i] = val;
}
return p;
}
static int
tarai(int x, int y, int z)
{
void **p1, **p2;
int result;
if (!(p1 = cache[x+1])) {
cache[x+1] = p1 = new_cache(0);
}
if (!(p2 = p1[y])) {
p1[y] = p2 = new_cache(-2);
}
if ((result = p2[z]) == -2) {
p2[z] = result = tarai0(x,y,z);
}
return result;
}
static inline int
tarai0(int x, int y, int z)
{
if (x <= y) return y;
return tarai(tarai(x-1, y, z),
tarai(y-1, z, x),
tarai(z-1, x, y));
}
ちっ、こっちのほうが多次元配列を使うより短かかったか。
~/c/tarai % gcc -O6 -finline-functions -omemo-tarai memo-tarai2.c memo-tarai2.c: In function `tarai': memo-tarai2.c:54: warning: passing arg 1 of `new_cache' makes pointer from integer without a cast memo-tarai2.c:56: warning: assignment makes integer from pointer without a cast memo-tarai2.c:57: warning: assignment makes pointer from integer without a cast
黙れコンパイラ。俺が正義だ！
~/c/tarai % time ./memo-tarai aamine@harmony 768 ./memo-tarai 0.57s user 1.68s system 101% cpu 2.227 total ~/c/tarai % time runhugs tarai.hs aamine@harmony 768 runhugs tarai.hs 2.11s user 0.02s system 100% cpu 2.122 total
おしい。もうちょっとなんですけどね。 まだキャッシュの密度が薄いみたいなので、 データ構造を工夫すればまだ速くできそうです。
ただ、こうやって速くしたバージョンが本当に正しい値を計算してるか わからないんですよね。Haskell 版にしても Ruby yield 版にしても、 プログラムが正しそうであることはちょっと見れば確かめられます。 でもここで書いた C 版のプログラムが本当に正しいかどうかは ちょっと見ただけではわかりません。 少なくとも引数に負の数を与えると SEGV するわけだし。
ええい、ここまでやったら行くとこまで逝け！ st_table を利用した C / memoise version 3。
#include <stdio.h>
#include <stdlib.h>
#include "st.h"
#define K1 768
#define K2 384
#define K3 0
static int tarai(int, int, int);
static inline int tarai0(int, int, int);
st_table *cache;
int
main(int argc, char **argv)
{
cache = st_init_numtable();
printf("%d\n", tarai(K1, K2, K3));
exit(0);
}
static int
tarai(int x, int y, int z)
{
st_table *t1, *t2;
int result;
if (!st_lookup(cache, x, &t1)) {
t1 = st_init_numtable();
st_add_direct(cache, x, t1);
}
if (!st_lookup(t1, y, &t2)) {
t2 = st_init_numtable();
st_add_direct(t1, y, t2);
}
if (!st_lookup(t2, z, &result)) {
result = tarai0(x,y,z);
st_add_direct(t2, z, result);
}
return result;
}
static inline int
tarai0(int x, int y, int z)
{
if (x <= y) return y;
return tarai(tarai(x-1, y, z),
tarai(y-1, z, x),
tarai(z-1, x, y));
}
~/c/tarai % gcc -O6 -Wall -finline-functions memo-tarai3.c st.c alloc.c -omemo-tarai
memo-tarai3.c: In function `tarai':
memo-tarai3.c:28: warning: passing arg 3 of `st_lookup' from incompatible pointer type
memo-tarai3.c:30: warning: passing arg 3 of `st_add_direct' makes integer from pointer without a cast
memo-tarai3.c:32: warning: passing arg 3 of `st_lookup' from incompatible pointer type
memo-tarai3.c:34: warning: passing arg 3 of `st_add_direct' makes integer from pointer without a cast
memo-tarai3.c:36: warning: passing arg 3 of `st_lookup' from incompatible pointer type
~/c/tarai % time ./memo-tarai aamine@harmony
768
./memo-tarai 1.34s user 0.07s system 101% cpu 1.387 total
やたー
真の最速はコレみたいです。
~/c/tarai % ghc -O -o tarai tarai.hs aamine@harmony ~/c/tarai % time ./tarai aamine@harmony 768 ./tarai 0.01s user 0.00s system 579% cpu 0.002 total
見逃してましたが、4/13 の中田さんのやつが結構速いですね。 基本的には lambda を使うのと同じですけど、to_int を使って むりやりオブジェクト指向ぽくしてるのが特徴ですか。
# ちょっと修正したものを再掲
class Tarai
include Comparable
def initialize(x, y, z)
@x, @y, @z = x, y, z
@t = 0
end
def tarai_inspect(level = 3)
return "?" if (level -= 1) < 0
s = "Tarai(" <<
[@x, @y, @z].map {|x| Tarai === x ? x.tarai_inspect(level) : x}.join(", ") <<
")"
s << ("%#d" % @t) unless @t.zero?
s
end
def +(val)
@t += val
end
def -(val)
@t -= val
end
def <=>(val)
to_int() <=> val.to_int
end
def coerce(val)
case val
when Integer
[val, to_int()]
else
super
end
end
def to_int
@t += if !@x
0
elsif @x <= @y
@y
else
Tarai.new(Tarai.new(@x-1, @y, @z),
Tarai.new(@y-1, @z, @x),
Tarai.new(@z-1, @x, @y)).to_i
end
@x = nil
@t
end
alias to_i to_int
def to_s
to_i.to_s
end
end
t = Tarai.new(*ARGV.map {|n| n.to_i })
puts "#{t.inspect} = #{t}"
めも
# Ruby
"15".to_i # チェックが甘い。e.g. "a".to_i == 0
Integer("15") # チェックが厳しい。 e.g. Integer("a") は例外
; Scheme
(string->number "15")
-- Haskell
read "15" :: Int
-- Haskell (2) HaXml から抜粋
atoi :: String -> Int
atoi = foldl (\x y-> x*10 + ord y - ord '0') 0
遅ればせながら shiro さんとこの Wiki も見てきました。
おおっ、delay/force なんてので遅延評価できるんですね。 Scheme って凄いなー。
うーむ、原先生最新バージョンは……これは…… デフォルト引数を使うことで第三引数の無駄な評価を さらに一段減らしたんですね。す、凄すぎ。 これで (768,384,0) までは Hugs に勝てるようになりました。
■
ささだ [失礼ながら，笑ってしまいました．いやぁ，ようやる．つまり，Cで最速を目指すなら，GHC相当を書け，と．
ちなみに，mswin版だとスタック足りないっぽいです＞768
インチキとして，tarai(z-1,x,y) は消してしまう，とかありますけど（卑怯）．まぁ，そのための遅延評価なわけですが．
しかし，一般的にどういうシチュエーションでこの発想を利用するんだろう？]
■
はら [ピンポイント遅延評価ってのはどうでしょう：
def tarai( x, y, z = nil )
if x <= y
then y
else
z ||= yield
tarai(tarai(x-1, y, z), tarai(y-1, z, x)){ tarai(z-1, x, y) }
end
end
puts tarai(ARGV[0].to_i, ARGV[1].to_i, ARGV[2].to_i)]
■
はら [本来のHakellの話に戻すと(^^;、、、質問です:
(1)Haskell はmemoiseはしないのでしょうか。
(2)Haskell はローカルなmemoise（引数を２度評価しないこと）はしますよね？
(3)gosh の lambda 版が速くないのは、クロージャ生成のコストのせいでしょうか。
ruby-math に行った方がいいかなあ。]
■
あおき [Haskell ML はどうでしょ。
http://www.sampou.org/haskell/
に案内があります。]
■
shiro [(3)に関して：ちゃんと測ったことは無いのですが、delayも環境を保存しているので、生成のコストはクロージャとあまり変わらないと思います。lambda版が速くないのは単純に計算量の問題だと思います。
実装れべるで言えば、delayで作成されたpromiseは最初のforceの時にその内容が評価されて記憶されます。以降のforceは記憶された内容を返すだけです。クロージャの場合は呼び出す度に内容を評価してしまいます。Rubyでも結果をキャッシュするpromiseオブジェクトを作れば同じ様な計算量になると思います。
(キャッシュするというと副作用めいていて関数的でないですが、セマンティクスとしては、そもそも関数的な式は何度評価しても同じなので、その結果をキャッシュするのは処理系による最適化ということになると思います)。]
■
はら [内容を評価するタイミングについてはlambda版もHaskellも同じでは。違いは（僕の言葉でいうところの）ローカルなメモを取るかどうかではないかと想像するのですが。例えば
(define (tarai x y z)
(let ((x0 (x)) (y0 (y)))
(if (<= x0 y0)
y0
(tarai (lambda () (tarai (lambda () (- x0 1)) y z))
(lambda () (tarai (lambda () (- y0 1)) z x))
(lambda () (tarai (lambda () (- (z) 1)) x y))))))
とすると劇的に速くなります。]
■
shiro [確かに、ローカルで一回評価しておくと、計算量は遅延評価と同じ、線形になりますね。こちらで検証してみました：
http://www.shiro.dreamhost.com/scheme/wiliki/wiliki.cgi?Scheme%3a%a4%bf%a4%e9%a4%a4%a4%de%a4%ef%a4%b7%a4%d9%a4%f3%a4%c1]
■
nobsun [うぇーっ。すごいことになっていますねぇ。
Haskellの簡約は、outermost graph reduction といって、同じ変数に束縛
した式は高々一度しか簡約しないというものです。要するに、変数は式を指す
ポインタでみたいなものになっているわけです。
Introduction to Functional Programming using Haskell 2ed. §7.1]
もうお気付きかと思いますが、 ツッコミ表示欄で改行とインデントが効くようにしました。 tDiary の思想 (『ツッコミは、短く鋭く……』) からは 外れていきますが、便利なのでいいということにします。
つーか、この日記は bpt 値 (Bytes per Tukkomi) が異様に高いよね。
やつを追う前に言っておくッ！
おれは今やつのスタンドをほんのちょっぴりだが体験した
い…いや…体験したというよりはまったく理解を超えていたのだが………
あ…ありのまま 今起こった事を話すぜ！
『おれは 椅子を買いに行ったと思ったら いつのまにか FlexScan L665 を買っていた』
そういうわけで L665 です。NANAO の 18.1" 液晶モニタでは一番安いやつです……。 ビック P 館で約 13 万でした。 ポイントで 10% 引きなので実質 115000 円くらいでしょうか。 秋葉原で粘ればもうちょっと安いところはあるんですが、 衝動買いイオンが抜けてしまう前に買わないといけなかったのでやむをえません。
財布が許せば L685EX (同じく NANAO の 18.1" 液晶モニタのかなり高いやつ) を買いたかったんですが、税抜で約 20 万の値札を見てしまうとさすがに躊躇します。 画質は明らかによさそうなんですけどねー。 ですがそんなことばっかり言っていると L685 のインプレッションになってしまうので 未練はサッパリ捨てて L665 に戻ることにします。
感想。うん。いいんじゃないですかね。モニタだけで手持ちの金が尽きてしまって DVI 出力のビデオカードが買えなかったもんでとりあえずアナログ接続なんですが、 すげえクッキリ画質で満足です。滲みなし、ムラなし、歪みなし。 白は白く、黒は黒く、非常にキチッと出てます。 これまでは同じく NANAO の E55D っていうそこそこ良い CRT モニタだったんですが、 今度の L665 があまりにクッキリ映るため、 今まで平気で使ってたフォントがすんごく汚く見えます。 明日 DVI のビデオカード買ってきたらいったいどうなることか。
大きいのもやっぱいいですね。液晶 18.1" だと CRT ではどのくらいかな。 20" くらいですか？ 目が悪いのでサイズが上がってかなり楽になりました。
ドット抜けもほぼなし。端のほうに常時点灯が一個と常時青が一個。しかも 常に白背景の kterm を開いていると常時点灯は見えません。有利です。
デザインも NANAO のはたいてい好きなんで文句なし。 強いて言うとスリムエッジのほうがカッコいいけども、 L557 とか L767 の階段パネルよりはずっといいでしょ。
あっ、そうだその前に、Linux で液晶モニタを使うときって特殊なんですね。 液晶モニタを使うときは XF86Config のモードラインでは モニタの種類に関係なく VESA の値を指定しないといけないみたいです。 L665 は 1280x1024 ドットなので、以下の二つを指定しました。
# モードライン指定：X 3.3 の解説ページに載ってたけど X 4.3 でもそのままで OK だった # 1280x1024 @ 60Hz ModeLine "1280x1024" 108.000 1280 1320 1440 1688 1024 1025 1028 1066 +HSync +VSync # 640x480 @ 60Hz (緊急用) ModeLine "640x480" 25.175 640 648 752 800 480 490 492 525 -HSync -VSync
なにぃ、xf86cfg？ そんなもんは却下だ。手で書け！
ああ、L665 を買っちゃったから椅子はおあずけかなあ。 いいかげん壊れかけの 9600 円の椅子は捨てたいんだけど……。
あ、ちなみにぼくは NANAO 信者なので モニタの感想に関してはあまり信用しないでください。 しかも買った直後ですから。
へー、最近は nVIDIA が直接 Linux 用ドライバを提供してるのか。 GeForce4 が使えるとは思わなかったな。 どーしようかな、古いの探すのも面倒だし、GeForce4 にしようかな。
■ なかだ [bin/refeなどがrefe/config.rbをrequireしていないという問題の他に、
case-insensitiveなファイルシステムでは一部のデータファイル名が衝突するという問題があります。
具体的にはdata/refe/function_source/rb/の下でいくつかファイルとディレクトリが衝突しますが、気づいてないだけで他にもあるかも知れません。]