トップ 最新 追記

じじぃの日記、ツッコミ可

Twitter: @jijixi_org
Xbox Live: jijixi

初心者が書いた OCaml 入門
Spotlight tips サイト内リンク集
1970|01|02|
2003|10|11|12|
2004|01|02|03|04|05|06|07|08|09|10|11|12|
2005|01|02|03|04|05|06|07|08|09|10|11|12|
2006|01|02|03|04|05|06|07|08|09|10|11|12|
2007|01|02|03|04|05|06|07|08|09|10|11|12|
2008|01|02|03|04|05|06|07|08|09|10|11|12|
2009|01|02|03|04|05|06|07|08|09|10|11|12|
2010|01|02|03|04|05|06|07|08|11|
2011|05|
2012|01|

2006-07-01 [長年日記]

% [雑談] イタリア 2 点目〜

その前後に「どーしてそれが入らん!!」って感じのウクライナの攻撃。 あーもーめちゃめちゃおもしれえ。

……試合もおもしろいが、イタリアのゴールキーパーの顔もおもしろいな(何

% [雑談] イタリア 3 点目〜〜

さすがにこれで決まりだなあ……でもウクライナも一矢報いてほしいなあ。

% [雑談] イタリア勝った

オーストラリア戦ではパッとしないゲームをしてたけど、今回は強かったなあ。 準決が楽しみになってきた。

% [雑談] イングランド vs ポルトガル、後半 40 分

イングランドのピンチ継続中。 それは良いとして……

イングランドの 21 番は、やるスポーツ間違えてね? あんな手足がひょろ長いサッカー選手見たことないよ(苦笑

% [雑談] また延長か

厳しい試合が多いねえ。

% [雑談] ポルトガル勝利

稀に見る見応えたっぷりの PK 戦だった。

% [雑談] ブラジル vs フランス、前半終了

今のところフランスが押し気味。 ブラジルは全然攻めれてないなあ。


2006-07-02 [長年日記]

% [雑談] フランス先制

ジダンの FK からアンリ。綺麗すぎる。

しかし、ほんとブラジルはシャキっとしないな。どうしたんだ。

% [雑談] フランス勝利

ブラジル負けた〜

いやー、わからんもんだなー。

% [雑談][OCaml] 関数型言語脳の恐怖! (欝っぽい日記)

う……心当たりがある……

ただ、OCaml の場合は for とか while に break や continue みたいなのが無いから、どうしても再帰で回した方がやりやすいってのはあるんだよね。 んで、結局いつも再帰を使ってると、いざってときに for の書き方がわかんないの(苦笑

for とか while は配列とかの mutable なものを扱うときには便利だと思うんだけど、滅多に使わない分そういう場面に遭遇しても頭に浮かばない……

% [OCaml] メソッドを動的に呼び出したい (soutaroにっき)

しまった、わしもちょうど CamlinternalOO に目を付けて遊んでみようと思ってたのに、ワールドカップにうつつを抜かしてるうちに先を越された(苦笑

でも、おかげで自分で調べなきゃと思ってた部分をすっ飛ばせるのでありがたい。


2006-07-04 [長年日記]

% [Mac] MacOSX 流? dump & restore

今まで Fink 用に専用の UFS パーテーションを作って使ってたんだけど、そろそろ HFSX (HFS+ に Case Sensitive 拡張を付加したもの) を使ってみたいと思ったんで移行してみた。 んで、そのための作業としては…

  1. バックアップ
  2. ファイルシステムの変更
  3. バックアップの書き戻し

ってことになるわけだけど、ちろっと調べてみたところ OS 付属の dump/restore が HFS+ に対応してないとかって情報もあって (今はそんなことないような気もするんだが)、ちょっと不安だったんでディスクユーティリティ (Disk Utility.app)を使って全部やることにしたのであった。 そういうわけで、実際にやった手順は以下。OS のバージョンは 10.4.7。

  1. ディスクユーティリティを起動
  2. バックアップするボリューム (パーテーション) を選んで、メニューの『ファイル→新規→disk?s?(ボリューム名)からのディスクイメージ...』を選ぶ。("?" や "ボリューム名" の部分は選択してるものによって変わる)
  3. 『イメージを変換』っていうダイアログが出るので、適当に場所と名前を決めて、イメージフォーマットを『読み込み専用』(じゃなくても良いとは思うけど) にして保存 (もちろん、どっか別のパーテーションにね)
  4. インストール CD を使って起動 (UFS から HFS にしたり HFS から UFS にするにはディスク全体をアンマウントしなきゃいけないので。そういう状況でなければ CD 起動の必要は無い)
  5. ディスクユーティリティを再度起動して、ファイルシステムの変更 (今回の場合『Mac OS 拡張 (大文字/小文字を区別、ジャーナリング)』を選択
  6. 『復元』タブを開き、ソースに先程作ったディスクイメージ、復元先に今初期化したボリュームを指定して復元

今回は全部 GUI を使ってやったけど、たぶん diskutil コマンドを使えばバッチ処理もできるんじゃないかと思う (意味があるかは微妙だけど)。 それにしても、初期の頃に比べるとディスクユーティリティも随分使い勝手が良くなったなあ。

% [game] カルチョビット

某所でちょっと話題になってて気にはなってたんだけど、このインタビュー記事を読んで買う気になった。 この手のゲーム (サカつくとか) には手を出したこと無いんだけど、これは良いわ。

もうとにかく試合を見てるのがおもしろい。 サカつくとかだと、変に見た目がリアルなせいか同じモーションが目についたりして萎えるんだけど、こいつの場合そもそも見た目がショボいから全てはプレイヤーの脳内補完にかかってる。 んで、ショボいんだけどすごく活き活きとした動きっていうか、これはもう実際見てもらうしか無いと思うんだけど、とにかく本物の試合見てるような気分になること請合い。 インタビューで言われてる『もどかしさ』がたまらん(笑

つーか安いから GBA とか DS 持ってる人はとりあえず買っておけって感じ (さすがにそれは暴論だろう)。

% [雑談] ドイツ vs イタリア、前半終了

両チームとも、それなりにチャンスはあったけど結局 0-0 で折り返し。 どちらかと言えばイタリアペースかなあ? というところ。

それはそれとして、北朝鮮がミサイル発射ってニュースが。 日本海に着弾ってことらしいけど……え? まさかこれがテポドンだって言わないよね?


2006-07-05 [長年日記]

% [雑談] ミサイル発射情報のせいで見づらい

これが狙いか、北朝鮮 (んなアホな)。

なんかまた延長にもつれそうな気配。

% [雑談] 0 - 0 のまま延長突入

後半はドイツが押し気味だった。 でもイタリア守り堅いわ。

% [雑談] 延長早々イタリアの決定的チャンス

でも入んねー!!

% [雑談] イタリア先制〜

すげーーーー!!

残り時間ほとんど無し。

って言ってる間に 2 点目ーーーー!!

そして試合終了。 すげえ劇的。すごすぎ。大興奮。

% [本日のリンク元] Yahoo! 検索 (伝言ゲーム問題集)

なぜか検索のトップがうち。 無い無い、そんなものここに無いから。

……つーか、それくらい自分で考えろよ。

こういうのがあると、検索のリファラは隠そうかなって気になるんだけど、検索リファを辿っていくのをわりと楽しみにしてるんで二の足踏むんだよなあ……

% [雑談] ポルトガル vs フランス

フランス、PK で先制。 キーパーもコース読んでたんだけど、さすがにあそこに蹴られたら止められんか。

% [雑談] 前半終了

フランスの 1 - 0

ほとんど互角に見えるんだけど、ポルトガルにとってはあの PK が不運だったなあ。


2006-07-06 [長年日記]

% [雑談] 後半 32 分

C.ロナウドの FK がものすごい落ち方。 でも得点には繋がらず。

% [雑談] フランス勝利

結局 PK の 1 点だけ。ほとんど紙一重だったなあ。 ロスタイムのポルトガルの攻めは盛り上がった。

さて、決勝は今大会屈指の守備力同士の戦いになりましたな。 とは言っても、どちらも得点力が無いわけではないし、激しい試合になりそうだ。


2006-07-08 [長年日記]

% [雑談] カーンが出場しそう

準決で負けた時点でちょっぴり期待してたんだけど、現実になりそうな気配。 これで今日の (明日朝の) 三位決定戦も見逃がせない。

……や、どっちみち見るつもりではあったんだけどね。

% [雑談] ドイツ vs ポルトガル、前半終了 0 - 0

カーンは人気あるなあ。 バックパス受けるとか、ゴールキック蹴るとか、その程度でいちいち会場が沸くってどうよ(笑

ポルトガルに一回良いチャンスがあったんだけど、カーンがきっちり止めた。 あの辺、ベテランの味なのかな。 位置取りが絶妙だもんね。


2006-07-09 [長年日記]

% [雑談] ドイツ先制

豪快なミドルシュート。 キーパーのほぼ正面だったんだけど、ニアサイドを押さえに動きかけたところにファーに逃げていくような変化したんで、逆を突かれた感じになったっぽい。

……と、ここまで書いた時点でポルトガルのオウンゴール。 これで試合は決まりかなあ。 カーンは安定してるみたいだし、2 点も取られるとは思えない。

% [雑談] ドイツ 3 点目

タイガーシュート(違

強烈や……

% [雑談] ポルトガル 1 点

フィーゴの見事なアシスト。

% [雑談] 試合終了

ドイツの 3 - 1 .

シュバインシュタイガーの独壇場って感じやったね。 カーンの勇姿も見れたし満足じゃ。

% [雑談] ワールドカップ決勝、イタリア vs フランス

前半 7 分に、いきなりフランス PK で先制。 あれが PK って、ちょっと厳しい気がしたけども……

% [雑談] イタリア、コーナーから得点

早々に追い付いた。 まだ前半 20 分。

% [雑談] 同点のまま前半終了

うーん、互角……かな。 ただ、フランスは PK 以外でまだ決定的なチャンスって無い気がする。 イタリアは得点を上げたとき以外にも、セットプレイで何度か惜しいのがあった。

% [雑談] 後半 14 分ほど経過

後半開始からずっとフランスペース。 でもイタリアも要所を締めて無得点。

% [雑談] 後半 20 分ほど

相変わらずセットプレイは冴えているイタリア。 全然プレイにからめてなかったトッティを下げたら、通常のプレイも流れが良くなった印象。

% [雑談] 後半 41 分、デルピエロ投入

イタリアは枠を使い切る交代。 勝負をかけてきた形。

% [雑談] 延長突入

イタリアの勝負は実らず。 もうみんなヘロヘロなんだけど(苦笑

こうなると交代枠 2 つ残してるフランスがやや有利か。


2006-07-10 [長年日記]

% [雑談] 延長前半終了

フランスが攻めまくり。 けど無得点。 もうギリギリって感じだけど。

% [雑談] ジダンにレッドカード

頭突き。何やってんの?

% [雑談] 延長後半残り 8 分ほど

アンリが下がって、ジダンも退場。 なんかとんでもないことになってきたな。

% [雑談] イタリア優勝

結局 PK 戦にもつれこみ、5 - 3 でイタリアの勝利。

なんか微妙に消化不良な感じだったなあ。 ジダンはある意味伝説を残したね。 現役最後のプレーは『頭突き』みたいな……

しかしフジテレビ (なのかこっちの地方局なのかはわからんが) には殺意を覚えたぞ。 延長後半残り 1 分の辺りで思いっきり CM 入れやがった。予告も無く。 慌てて衛星放送が見れるテレビのとこまで走ったけど、最後のとこ見れなかったよ。


2006-07-11 [長年日記]

% [雑談] サッカーワールドカップはなかった! (bogusnews)

ツボった。

たまたまテレビのチャンネルを回していたわたしは、そのとき、ドイツからの生中継だという番組を視ることができました。しかしそれはサッカーの中継ではありませんでした。画面には、頭のハゲあがった大男がやや小兵の男にみごとなヘッドバットをかますシーンが映し出されていたのです! それはみごとな技の繰り出し方でした。明らかに素人ではありません。わたしの見たところではプロレスラーだったのではないかと思われます。

MVP だからなあ(笑

% [PC][雑談] キミならどう書く 2.0 - ROUND 2 - (LL Ring)

わしゃ頭悪いからやるつもりは無いんだけどさ…… (前回はたまたまネタがかぶっただけ)

f(3) -> f(10) -> f(5) -> f(16) -> f(8) -> f(4) -> f(2) -> f(1) -> 1

「ルークよ、ビット演算を使うのだ」って声が聴こえてくるような、こないような。 効率が良いかどうかは知らんけどな。


2006-07-12 [長年日記]

% [PC][雑談] Collatz 予想

関数 g の定義は素直にメモ化したものにするとして、関数 h は奇数だけ調べれば良さそうな感じかなあ。 んで、ステップが最大になる値 k が n / 2 以下のときは k * 2 が答え (大きければそのまま k ) って感じ?

なんとなく、もう少し値を絞れそうな気もするんだけど……わからん。 素数かなあ……?

(追記) 素数じゃダメだな。

% [PC][雑談] Collatz その2

n = 1000 くらいまでずらーっと表示させてみた感じだと、n / 2 以上の奇数を調べれば十分な気配。 んで、最大な k が n / 2 だった場合だけは答えが n って感じか。

なんとなく 2n / 3 以上の奇数と、n (偶数の場合でも) を調べるんでも良いような気もするんだが、ほんとかどうかはわからん。

% [PC][雑談] Collatz その3

何だかんだ言いながら結局ぐちぐち考えちゃってる自分がイヤ……

n が奇数のとき、3n+1 は必ず偶数になる。 ということは、n に対して関数 f を二回適用すると結果は…

(3n + 1) / 2

となる。 n の範囲が 1..m だとすると、(自然数相手なので細かい部分は端折って) 3n/2 が m を越えるのは…

n > 2m / 3

のときになる。 3n/2 が 1..m の範囲に収まる場合 (n <= 2m / 3 … (A))、そうではない値 (n > 2m / 3 … (B)) に対して増える回数はたかだか 2 だが、B が 1..m の範囲に戻ってくるには間違いなく 3 回以上必要なので、A の範囲の値が最大値になる可能性は無い。

よって調べるべき値は、

範囲が 1..m のとき
n = m もしくは
n > 2m / 3 かつ n は奇数

となると思われる。 コードはめんどくさいので書かない。

あと、関数 g のメモ化に関しては、あらかじめ n が 2 の累乗のケースを登録してしまうと多少速くなるかも知れない。 つーか、こっちももう少し工夫のしどころがありそうな気がするんだけど、今はちょっと思い付かない。

% [PC][雑談] Collatz その4

うーん……

これ、直感的には奇数だけをチェックすれば事足りるような気がする。偶数はすぐ2で割れてしまうので値は少なそうだ。というわけで、奇数だけを調べる版というのを作ってみたのだが、スピードアップしたような気はしない。

なんでかということを考えるに、けっきょくどっかで偶数の計算をしてしまうからだろう。たとえば f 3 -> f 10 -> f 5 -> f 16 -> f 8 -> f 4 -> f 2 -> f 1 -> 1 のように、16の計算は f 3 でやられているから省略をしても仕方ない。どういうパスを通るかわからないから、奇数だけ程度であれば、ほとんどの偶数値はけっきょく計算されてしまい、そのため差が出ないのだろう。

[haskellのある暮らしより引用]

そんな気はしてたけど、やっぱ関数 h より g で工夫しないとあかんのかな。

んで、考えたんだけど、h では奇数だけ調べるとして、g では逆に偶数だけ計算すると良いのかも知れない。 さっき書いたように 3n+1 (n は奇数) は常に偶数なので、奇数を…

g(3 * n + 1) + 1

と定義してしまえば良いんじゃないだろうか。 あんまり違わないかな? やってみないとわからん。……やらんけど (めんどい)。

本日のツッコミ(全1件) [ツッコミを入れる]

% TrackBack [http://jijixi.azito.com/cgi-bin/diary/index.rb?date=200607..]


2006-07-13 [長年日記]

% [雑談] 暑い……

夏やなぁ……夏やでぇ……ワールドカップも終わって気が抜けまくってるところに追い打ち。 あー、だりー。

そういや今週の土曜日は OSC Hokkaido なのだったよ。 今回あんまし食指が動くプログラムが無いんで、どうしたもんかなー…とは思ってるんだが。 つーか、こういうイベントよりも LL Ring みたいなのを北海道でやってくださいよー。

% [雑談] はい、そのとおりです(ぼそり

……何が?


2006-07-14 [長年日記]

% [game] LocoRoco

癒し系。ぷよぷよ感がたまらない。 ぱっと見、前例の無いようなゲームだけど、大雑把に言って『初代ソニック・ザ・ヘッジホッグを斜め上に進化させたら、こうなりました』って感じのゲーム性だと思った。

隠しルートなんかにこだわらなければ、わりと簡単なゲームなんで、まったり楽しむのが良さそう。 やりこみ要素も結構あるんで、やりこみ好きな人はやればよろしい。

% [雑談] このスレだけ10年先をいっているすれ (2ch)

全体的には特におもしろいわけじゃないんだけど、その中でさりげなく 26 がツボだった。

% [OCaml][雑談] Collatz 敗北編

結局自分でコード書いて試してみたんだけど、3 分の 2 以降だけ調べれば良い説はダメだなー。 6171 っていう強力なヤツがいて、これの次が 10971 なんで、n = 10000 前後で嘘の答が出てしまう。

あと、g で偶数だけ扱うのもあんまり意味無い感じ。 ってか、素直に全部メモするのより遅くなっちゃってハテナ?

つーか、OCaml のハッシュテーブルって遅いのかなあ。 ヘタクソな書き方すると、メモ無しの方が速かったりするんだけど…… 考えて書き直しても、はっきりわかるほどの違いが無い感じだし。

あんまりメモ化の恩恵が出にくい問題なのかね。 結局、メモはやめて末尾再帰だけでぶん回した方がすっきりしてるんで、あとは適当に n / 3 以降の奇数だけ調べる感じで (正当性は疑問が残るが) 終了。 あ、ちゃんと結果が n / 2 以下の場合は 2 倍するようにしてるんで、そこら辺は大丈夫じゃないかと。

% cat collatz.ml
let g n =
   let rec g' n' count =
      match n' with
      | 1 -> count
      | _ when n' mod 2 = 0 ->
           g' (n' / 2) (count + 1)
      | _ ->
           g' (3 * n' + 1) (count + 1)
   in
   g' n 1

let h n =
   let limit = n / 3 in
   let rec h' n' ((k, _) as ret) =
      match n' with
      | _ when n' < limit -> k
      | _ ->
           let ret' = (n', g n') in
           let max a b =
              if (snd a) >= (snd b) then a else b
           in
           h' (n' - 2) (max ret ret')
   in
   let ret = h' (if n mod 2 = 0 then n - 1 else n) (n, g n) in
   if ret > n / 2 then ret else ret * 2

let main () =
   let arg = int_of_string (Sys.argv.(1)) in
   let result = h arg in
   let result2 = g result in
   Printf.printf "h(%d) => k is %d\ng(k) => %d\n" arg result result2;
   exit 0

let _ = if not !Sys.interactive then main ()

んで、整数のオーバーフローとか考えるのはかったるいんで、64 bit 版でごまかすのである。

% ocamlc64 collatz.ml -o collatz

% time ocamlrun64 collatz 10000
h(10000) => k is 6171
g(k) => 262
ocamlrun64 collatz 10000  0.19s user 0.02s system 83% cpu 0.250 total

% time ocamlrun64 collatz 100000
h(100000) => k is 77031
g(k) => 351
ocamlrun64 collatz 100000  1.33s user 0.03s system 93% cpu 1.445 total

% time ocamlrun64 collatz 1000000
h(1000000) => k is 837799
g(k) => 525
ocamlrun64 collatz 1000000  14.77s user 0.13s system 89% cpu 16.600 total

% [PC] Virtual PC 2004 が無償に

諸方面より。

VM Ware が無償になったときに噂は出てた気がするけど、とうとうそうなったようだ。 わしの PC には Connectix 時代の 5.2 が入ってたんだけど、せっかくだからアップグレードしてみた。

……してみたんだけど、なんかあれだな、機能が低下してたりしないか、これ。 VNC ホスト機能が無くなってるし。 もしかしてサーバ版にだけは付いてるとかって寸法か? 代わりに、ネットワークアダプタを複数使えるようになってるのは便利そうだな。

まあ、それはそれとして、全体的にはそれほど変わりばえしないんだけど、5.2 時代のディスクイメージをそのまま使おうとしたら、NT 系 Windows はなんとかなったけど DOS 系は全滅だったのがショボーン。 さりげなくハード構成がいろいろ変わってるみたいっすねー。 いやいや、もうさすがに DOS 系 Win は考えなくて良いだろーと見切りを付けて思い切ってディスクイメージは破棄したよ。 もう MS のサポートも終わってんだから、「知りません」で済むよな。

ともあれ、ホスト OS が Windows なら VM Ware より快適だと思うんで、使ったこと無い人もこの機会に使ってみることをお薦めする。 VM Ware より劣る点と言えば、USB 機器を直接使えないことか。 Mac 版は使えるのに何で Windows 版はダメなんかねえ。


2006-07-15 [長年日記]

% [OCaml][雑談] Collatz 予想、Num モジュールを使ったバージョン

昨日の関数 g だけ以下のように変更。

open Num
let g n =
   let rec g' n' count =
      if n' =/ Int 1 then count
      else
         if mod_num n' (Int 2) =/ (Int 0)
         then g' (n' // (Int 2)) (count + 1)
         else g' ((Int 3) */ n' +/ (Int 1)) (count + 1)
   in
   g' (Int n) 1

うーん、見づらい(苦笑

% time ./collatz 1000
h(1000) => k is 871
g(k) => 179
./collatz 1000  1.08s user 0.02s system 84% cpu 1.308 total

% time ./collatz 10000
h(10000) => k is 6171
g(k) => 262
./collatz 10000  13.45s user 0.14s system 90% cpu 14.948 total

ぐへ、ひどく遅い。これ以上、大きな数でやる気にはならんな。 これくらい遅い処理になれば、メモ化も意味あるのかなあ。

% [OCaml][雑談] Num 版 Collatz その2

2 で割るときに問答無用で Ratio になっちゃうのが遅い原因のような気がしたので、ちょっと小細工してみた。

open Num
let g n =
   let rec g' n' count =
      if n' =/ Int 1 then count
      else
         if mod_num n' (Int 2) =/ (Int 0)
         then g' (if is_integer_num n'
                  then Int ((int_of_num n') / 2)
                  else n' // (Int 2))
                 (count + 1)
         else g' ((Int 3) */ n' +/ (Int 1)) (count + 1)
   in
   g' (Int n) 1
% time ./collatz 1000
h(1000) => k is 871
g(k) => 179
./collatz 1000  0.76s user 0.02s system 90% cpu 0.866 total

% time ./collatz 10000
h(10000) => k is 6171
g(k) => 262
./collatz 10000  8.92s user 0.09s system 91% cpu 9.896 total

それなりに速くなったようだ。

% [OCaml][雑談] Num で Collatz、もういい加減これで終わり

ぐあ、Num.is_integer って int かどうかじゃなくて整数 (Big_int 含む) かどうかを調べるだけなのか。 仕方ないから、再度改修。ついでに mod のところも小細工できるのでそこも。

open Num
let g n =
   let rec g' n' count =
      if n' =/ Int 1 then count
      else
         let is_int, int_n =
            try
               let tmp = int_of_num n' in
               (true, tmp)
            with Failure _ -> (false, -1)
         in
         let is_even =
            if is_int
            then int_n mod 2 = 0
            else mod_num n' (Int 2) =/ (Int 0)
         in
         if is_even
         then g' (if is_int
                  then Int (int_n / 2)
                  else n' // (Int 2))
                 (count + 1)
         else g' ((Int 3) */ n' +/ (Int 1)) (count + 1)
   in
   g' (Int n) 1
% time ./collatz 1000
h(1000) => k is 871
g(k) => 179
./collatz 1000  0.10s user 0.02s system 68% cpu 0.161 total

% time ./collatz 10000
h(10000) => k is 6171
g(k) => 262
./collatz 10000  0.72s user 0.02s system 81% cpu 0.905 total

% time ./collatz 100000
h(100000) => k is 77031
g(k) => 351
./collatz 100000  7.74s user 0.08s system 90% cpu 8.667 total

これで、Big_int が使われない領域での速さはまともになった。 使われるようになった途端オーダーが跳ね上がるのは、まあご愛嬌ですな。

% [雑談] 朝から暑いなあ……

せっかく OSC に朝から参加できる時間に起きたのに、うだうだやってるうちにすでに 9 時半ですよ。 暑いしいまいち行く気がしねえ……

あー、でもせっかく一年に一度のイベントだし、昼からでも行くかなあ。 北大なんか行かんで、大通りに行きたい気もするが (つーか、もうビアガーデンやってんだっけ?)。

% [OCaml][雑談] 一応、さっきのをネイティブコンパイルすると…

こんな感じ。

% time ./collatz_opt 1000
h(1000) => k is 871
g(k) => 179
./collatz_opt 1000  0.01s user 0.02s system 37% cpu 0.079 total

% time ./collatz_opt 10000
h(10000) => k is 6171
g(k) => 262
./collatz_opt 10000  0.08s user 0.02s system 72% cpu 0.136 total

% time ./collatz_opt 100000
h(100000) => k is 77031
g(k) => 351
./collatz_opt 100000  0.56s user 0.02s system 86% cpu 0.673 total

% time ./collatz_opt 1000000
h(1000000) => k is 837799
g(k) => 525
./collatz_opt 1000000  6.28s user 0.08s system 91% cpu 6.923 total

64 bit のバイトコード版よりも断然速い。(もちろん 64 bit 版をネイティブコンパイルできればなお良いんだろうけど)

% [雑談] OSC 行ってきた

昼すぎに着いて二コマ見て、かったるくなったんで帰ってきた。 見たのは A-3C-4

川合さんの話はおもしろかった。基本的にネタトークというか、技術的な話とかは特に無し。

NEC の人のは、なんつーか返り値に int を使ってるの (100 箇所くらいあったとか) を unsigned int に直したって話があって、パッチを投げたら「なんでこんなのが残ってたんだろう?」みたいな話になったらしいんだけど、それって『誰も触りたくないから放置されてた』ってことじゃないの? と思った(苦笑)。 負数が何に使われてるか (あるいはまったく使われていないか) を隅から隅まで調べなきゃならないなんて地獄だよ。 わしはやりたくないなあ。 つーか ext3 なんていい加減捨てれよ(暴言

% [OCaml][雑談] いちいち名前を付けてしまうクセ

さっきの Collatz ネタの中で、

try
   let tmp = int_of_num n' in
   (true, tmp)
with Failure _ -> (false, -1)

こういう部分があったが、ほんとはここは

try
   (true, int_of_num n')
with Failure _ -> (false, -1)

これで良いはずなんである。 なんだけど、わしの場合ついつい後のことを考えて名前を付けてしまう。 要するに、後で tmp の値を何かで使うかもしれない…と思ってしまうのだね。 結局使わないんだけど。

もう少し長い式なら、それでも意味あるんだろうけど、今回みたいな場合だとあんま意味無いよなあ。 でも無意識にやっちゃってるからしかたない。 わしにはコードを短くする素養は無いようだ。


2006-07-16 [長年日記]

% [OCaml][雑談] せっかくだから最終版を晒しとく (Collatz 最終回)

世間ではまだまだ高速化に血道をあげてる人がいるっぽいけど、わしはもうお腹いっぱい。 だって、富豪的プログラマですからー。 一応ここら辺で、

n/2 から n までだけ調べれば良い。

ってのが証明されてるみたいなんで、それを反映したものを最後に置いとく。 通常版とメモ化版。

% cat collatz.ml
open Num

let g n =
   let rec g' n' count =
      if n' =/ Int 1 then count
      else
         let is_int, int_n =
            try
               (true, int_of_num n')
            with Failure _ -> (false, -1)
         in
         let is_even =
            if is_int
            then int_n mod 2 = 0
            else mod_num n' (Int 2) =/ (Int 0)
         in
         if is_even
         then g' (if is_int
                  then Int (int_n / 2)
                  else n' // (Int 2))
                 (count + 1)
         else g' ((Int 3) */ n' +/ (Int 1)) (count + 1)
   in
   g' (Int n) 1

let h n =
   let limit = n / 2 in
   let rec h' n' ((k, _) as ret) =
      match n' with
      | _ when n' < limit -> k
      | _ ->
           let ret' = (n', g n') in
           let max a b =
              if (snd a) >= (snd b) then a else b
           in
           h' (n' - 2) (max ret ret')
   in
   h' (if n mod 2 = 0 then n - 1 else n) (n, g n)

let main () =
   let arg = int_of_string (Sys.argv.(1)) in
   let result = h arg in
   let result2 = g result in
   Printf.printf "h(%d) => k is %d\ng(k) => %d\n" arg result result2;
   exit 0

let _ = if not !Sys.interactive then main ()
% cat collatz_memo.ml
open Num

module HT = Hashtbl.Make (struct
                             type t = Num.num
                             let equal = eq_num
                             let hash  = Hashtbl.hash
                          end)
let memo = HT.create Sys.max_array_length
let _ = HT.add memo (Int 1) 1

let g n =
   let rec g' n' =
      try
         HT.find memo n'
      with Not_found ->
         let is_int, n_int =
            try
               (true, int_of_num n')
            with Failure _ -> (false, -1)
         in
         let is_even =
            if is_int
            then n_int mod 2 = 0
            else mod_num n' (Int 2) =/ (Int 0)
         in
         let v =
            (if is_even
             then g' (if is_int
                      then Int (n_int / 2)
                      else n' // (Int 2))
             else g' ((Int 3) */ n' +/ (Int 1)))
            + 1
         in
         HT.add memo n' v;
         v
   in
   g' (Int n)

let h n =
   let limit = n / 2 in
   let rec h' n' ((k, _) as ret) =
      match n' with
      | _ when n' < limit -> k
      | _ ->
           let ret' = (n', g n') in
           let max a b =
              if (snd a) >= (snd b) then a else b
           in
           h' (n' - 2) (max ret ret')
   in
   h' (if n mod 2 = 0 then n - 1 else n) (n, g n)

let main () =
   let arg = int_of_string (Sys.argv.(1)) in
   let result = h arg in
   let result2 = g result in
   Printf.printf "h(%d) => k is %d\ng(k) => %d\n" arg result result2;
   Printf.printf "Hashtbl length => %d\n" (HT.length memo);
   exit 0

let _ = if not !Sys.interactive then main ()
% ocamlopt nums.cmxa collatz.ml -o collatz
% ocamlopt nums.cmxa collatz_memo.ml -o collatz_memo

% time ./collatz 1000000
h(1000000) => k is 837799
g(k) => 525
./collatz 1000000  4.81s user 0.07s system 89% cpu 5.439 total

% time ./collatz_memo 1000000
h(1000000) => k is 837799
g(k) => 525
Hashtbl length => 1847221
./collatz_memo 1000000  5.15s user 0.40s system 88% cpu 6.251 total

……なんかメモした方が遅いし...orz

ちなみに通常版は関数 g が末尾再帰になってるが、メモ化版のように末尾再帰ではない形にしても速度は変わらなかった。 感覚的には、こういう単純に末尾再帰にできるパターンだと、スタックを積まない分、末尾再帰の方が多少なりとも速くなりそうな気がしてたんだけど。


2006-07-17 [長年日記]

% [OCaml][雑談] Collatz スレッド版

最後って言っておいて、まだやっててごめんなさい。 いや、ネタに走るのは別に良いじゃない?

% cat collatz_threaded.ml
open Num

module HT = Hashtbl.Make (struct
                             type t = Num.num
                             let equal = Num.eq_num
                             let hash = Hashtbl.hash
                          end)

let memo =
   let obj = object
      val table = HT.create Sys.max_array_length
      val mutex = Mutex.create ()
      method table = table
      method mutex = mutex
   end in
   HT.add obj#table (Int 1) 1;
   obj

let g n =
   let rec g' n' =
      try
         HT.find memo#table n'
      with Not_found ->
         let is_int, n_int =
            try
               (true, int_of_num n')
            with Failure _ -> (false, -1)
         in
         let is_even =
            if is_int
            then n_int mod 2 = 0
            else mod_num n' (Int 2) =/ (Int 0)
         in
         let v =
            (if is_even
             then g' (if is_int
                      then Int (n_int / 2)
                      else n' // (Int 2))
             else g' ((Int 3) */ n' +/ (Int 1)))
            + 1
         in
         Mutex.lock memo#mutex;
         HT.add memo#table n' v;
         Mutex.unlock memo#mutex;
         v
   in
   g' (Int n)

let proc (n, ch) =
   let ev = Event.send ch (g n) in
   Event.sync ev

let h n =
   let rec mk_list count l =
      if count < n / 2 then l
      else
         let next =
            let ch = Event.new_channel () in
            (count,
             Thread.create proc (count, ch),
             ch)
         in
         mk_list (count - 2) (next :: l)
   in
   let n_list = mk_list (if n mod 2 = 0 then n - 1 else n) [] in
   List.fold_left begin fun a b ->
      let n1, step1 = a in
      let n2, _, ch = b in
      let step2 = Event.sync (Event.receive ch) in
      if step1 > step2 then (n1, step1) else (n2, step2)
   end (0, 0) n_list

let main () =
   let arg = int_of_string (Sys.argv.(1)) in
   let k, g_k = h arg in
   Printf.printf "h(%d) => k is %d\ng(k) => %d\n" arg k g_k;
   exit 0

let _ = if not !Sys.interactive then main ()
% ocamlopt -thread unix.cmxa threads.cmxa nums.cmxa collatz_threaded.ml -o collatz_threaded

% time ./collatz_threaded 100
h(100) => k is 97
g(k) => 119
./collatz_threaded 100  0.25s user 0.12s system 78% cpu 0.463 total

% time ./collatz_threaded 1000
h(1000) => k is 871
g(k) => 179
./collatz_threaded 1000  1.15s user 0.22s system 85% cpu 1.608 total

% time ./collatz_threaded 10000
h(10000) => k is 6171
g(k) => 262
./collatz_threaded 10000  8.84s user 1.74s system 87% cpu 12.049 total

すこぶる遅いのは、まあなんつーか仕様。ネタだからね。 ちなみにこれ以上大きな数字でやろうとすると……

% time ./collatz_threaded 100000
Fatal error: exception Sys_error("Thread.create: Resource temporarily unavailable")
./collatz_threaded 100000  19.85s user 5.15s system 79% cpu 31.316 total

こんなん出た(苦笑


2006-07-18 [長年日記]

% [OCaml][雑談] Map 版 Collatz

……あー、なんつーの? ほとんど OCaml が標準で用意してるデータ構造の性能調査みたいなノリっつーかね、Collatz 予想自体はもうどうでも良いんだけど、いろいろ試してみるにはちょうど良いネタなんで、つい。

ってことで、Hashtbl の代わりに Map モジュールを使ったバージョンなんだが。

ちなみに、この前晒した Hashtbl を使ったものは、hash 関数の実装をさぼってるので Big_int の領域に入ると非常に効率がよろしくないのである。 具体的には Hashtbl.hash は Big_int な値に対して常に同じハッシュ値を出してしまうので、結果、Big_int な値については線形探索になってしまうのであった。 だから、Big_int な値に対しても適度にばらけるようなハッシュ関数を使ってやれば、もう少し速くなるんじゃないかと思わなくもないんだけど、めんどくさいしなー……となって、今度は平衡二分木で実装されてる (らしい) Map モジュールを使ってみようという次第。

% cat collatz_memo_map.ml
open Num

module M = Map.Make (struct
                        type t = Num.num
                        let compare = compare_num
                     end)
let memo = ref (M.add (Int 1) 1 M.empty)
let add_memo k v = memo := M.add k v !memo

let g n =
   let rec g' n' =
      try
         M.find n' !memo
      with Not_found ->
         let is_int, n_int =
            try
               (true, int_of_num n')
            with Failure _ -> (false, -1)
         in
         let is_even =
            if is_int
            then n_int mod 2 = 0
            else mod_num n' (Int 2) =/ (Int 0)
         in
         let v =
            (if is_even
             then g' (if is_int
                      then Int (n_int / 2)
                      else n' // (Int 2))
             else g' ((Int 3) */ n' +/ (Int 1)))
            + 1
         in
         add_memo n' v;
         v
   in
   g' (Int n)

let h n =
   let limit = n / 2 in
   let rec h' n' ((k, _) as ret) =
      match n' with
      | _ when n' < limit -> k
      | _ ->
           let ret' = (n', g n') in
           let max a b =
              if (snd a) >= (snd b) then a else b
           in
           h' (n' - 2) (max ret ret')
   in
   h' (if n mod 2 = 0 then n - 1 else n) (n, g n)

let main () =
   let arg = int_of_string (Sys.argv.(1)) in
   let result = h arg in
   let result2 = g result in
   Printf.printf "h(%d) => k is %d\ng(k) => %d\n" arg result result2;
   exit 0

let _ = if not !Sys.interactive then main ()

Map には副作用が無いので、ほんとはもっとちゃんと関数的に書けば良いのかもしれないけど、Hashtbl 版を手直しして使ってるんで安易にリファレンスを使った。

% ocamlopt nums.cmxa collatz_memo_map.ml -o collatz_memo_map

% time ./collatz_memo_map 1000
h(1000) => k is 871
g(k) => 179
./collatz_memo_map 1000  0.02s user 0.02s system 36% cpu 0.086 total

% time ./collatz_memo_map 10000
h(10000) => k is 6171
g(k) => 262
./collatz_memo_map 10000  0.19s user 0.03s system 75% cpu 0.297 total

% time ./collatz_memo_map 100000
h(100000) => k is 77031
g(k) => 351
./collatz_memo_map 100000  1.89s user 0.09s system 88% cpu 2.233 total

% time ./collatz_memo_map 1000000
h(1000000) => k is 837799
g(k) => 525
./collatz_memo_map 1000000  39.95s user 1.40s system 78% cpu 52.848 total

Hashtbl 版は以下のような感じなんで、やっぱ遅いわなあ。 もっともっと Big_int の領域が増えてくると逆転する可能性が無いとは言えないけど、その前にどちらの構造にも限界 (スタックオーバーフローとか) が来そうな気もする。

./collatz_memo 1000  0.16s user 0.10s system 74% cpu 0.349 total
./collatz_memo 10000  0.14s user 0.07s system 83% cpu 0.254 total
./collatz_memo 100000  0.55s user 0.11s system 87% cpu 0.759 total
./collatz_memo 1000000  5.17s user 0.39s system 89% cpu 6.209 total

2006-07-21 [長年日記]

% [Mac] OmniWeb 5.5 beta 1

ようやく出た。

いつの頃からか reddit にログインできなくなってて、それがいまだに何とかなってない以外は、特に問題無く使える。


2006-07-24 [長年日記]

% [SML][OCaml] ランク1多相性 (SML#プロジェクト)

いーなー、これいーなー、OCaml にも欲しーなー。

% [SML][OCaml] 真・多相レコード

MacOSX で動かないから実際に動かしたことなかった SML# であったが、ようやく重い腰を上げて FreeBSD で動かしてみたのである。 ってことで、SML, OCaml, SML# で同じことをやってみる。

% sml
Standard ML of New Jersey v110.58 [built: Sun May 28 16:01:12 2006]
- val a = { hoge = "hoge", fuga = 1 };
val a = {fuga=1,hoge="hoge"} : {fuga:int, hoge:string}
- val b = { hoge = 1, fuga = "fuga" };
val b = {fuga="fuga",hoge=1} : {fuga:string, hoge:int}
- fun f x = #hoge x;
stdIn:2.37-3.17 Error: unresolved flex record
   (can't tell what fields there are besides #hoge)

ショボーン。

% ocaml
        Objective Caml version 3.09.2

# let a = object method hoge = "hoge" method fuga = 1 end;;
val a : < fuga : int; hoge : string > = <obj>
# let b = object method hoge = 1 method fuga = "fuga" end;;
val b : < fuga : string; hoge : int > = <obj>
# let f x = x#hoge;;
val f : < hoge : 'a; .. > -> 'a = <fun>
# f a;;
- : string = "hoge"
# f b;;
- : int = 1

うむ。

% smlsharp
restoring static environment...done
restoring dynamic environment...done

# val a = { hoge = "hoge", fuga = 1 };
val a = { fuga = 1, hoge = "hoge" } : {fuga:int , hoge:string}
# val b = { hoge = 1, fuga = "fuga" };
val b = { fuga = "fuga", hoge = 1 } : {fuga:string , hoge:int}
# fun f x = #hoge x;
val f = fn : ['a,'b#{hoge:'a}.'b  -> 'a]
# f a; 
val it = "hoge" : string
# f b;
val it = 1 : int

おー。 これは使い始めると OCaml の object なんてかったるくて書いてらんなくなりそうだなあ。

今のところ起動時間が異様に長かったり (ghci より長いのはどうかと思う) ネイティブコンパイルができなかったり、OCaml から乗り換える対象になるかって言えばならないとは思うけど、先が楽しみではある。 まあ、α版ってことを考えれば十分遊べるものになってるし、これからいろいろいじってみるとしよう。


2006-07-25 [長年日記]

% [SML][OCaml] オブジェクトよりレコードの方が嬉しい点

って何かなーと考えるに、パターンマッチに使えることじゃないかと思った。 オブジェクトの方が表記が冗長だってのは、個人的にはあまり気にならないんだけど、パターンマッチはわりと切実に感じる部分かなと。

んで、SML# の多相レコードはあくまでもレコードなんで、きっちりパターンマッチに使えて嬉しいのであった。

# fun f { x, ... } = x;
val f = fn : ['a,'b#{x:'a}.'b  -> 'a]

# f { x = 1, y = 1.0 };
val it = 1 : int

# f { x = "hoge", x' = "fuga" };
val it = "hoge" : string

ちなみにこれを素の SML でやると、

- fun f { x, ... } = x;
stdIn:11.3-12.20 Error: unresolved flex record
   (can't tell what fields there are besides #x)

とか言われてダメ。

まあ、上記のような単純な例ならパターンマッチじゃなくても、

# let f obj = obj#x;;
val f : < x : 'a; .. > -> 'a = <fun>
# f (object method x = 1 end);;
- : int = 1
# f (object method x = "hoge" method x' = "fuga" end);;
- : string = "hoge"

こんなでも良いわけだけど、複数のメンバを変数に束縛して使いたいときにはパターンマッチが使えた方がすっきり書けると思うんだよね。 もちろん OCaml でもオブジェクトじゃなくレコードを使えばできるんだけど、OCaml のレコードはいまいち使いづらいから、あらかじめきっちり使いどころが決まってるようなシチュエーションじゃないと使う気にならないんだよな。

% [Mac] アップル、ワイヤレスになった「Mighty Mouse」のニューバージョンを発表 (MYCOMジャーナル)

やっと来たか。 レーザートラッキングまで採用してて、これは買いだろ。

……だが金が無い!!...orz

や、そう言いながら、たぶん買うんだけど……


2006-07-26 [長年日記]

% [雑談] ゲームをしてるとき叫んだセリフを挙げるスレ (日刊スレッドガイド)

>>18 が激しく身に覚えある(笑)。 たぶんスパロボをやる人間の 8 割以上は経験あるんじゃなかろうか。

他には >>130 とかもあるなあ。


2006-07-27 [長年日記]

% [雑談] 「kt」→「こと」みたいな変換

向井さんとこを読んでて思い出したんだけど、以前使ってたケータイ (SHARP の SH-52 だったかな) に似たような機能が付いていた。 あれはひらがなだけじゃなく漢字にも変換するタイプだったけど。 例えば 2,4 (か、た) と入力して変換キーを押すと (こと、事、琴、……) みたいな候補が出るって感じ。

そもそもケータイで文字とか打たない人間なんで、結局あんまり使わなかったけど、おもしろい機能だなーとは思ってた。 って言うか、パソコンで使えるの誰か作らんかなーと思ってたんだが、誰も作ってないんかなあ。 prime みたいに逐次変換するようになってれば、おもしろいと思うんだけど。 あらかじめこれ用にソートした辞書を作っておけば、それほどコストが爆発するようなものにはならないような気もするんだけど、楽観的かしら。

% [雑談] 上記ネタの変換候補

ちょっと誤解を招きそうな例だったんで、少し補足。 あれだと『こと』しか出ないみたいだが、そうじゃなくて…

  • かた
  • かち
  • かつ
  • かて
  • かと
  • きた
  • 以下略

に対する変換候補が出る。 二文字くらいだと候補が多すぎる気もするけど、頻度情報とか保存するようにすれば実用にはなるんじゃね? と思わなくもない。 件のケータイでは、最近使った候補が優先で表示されるようになってたと思う。 あと、あれは主にリソースの問題だと思うけど辞書が貧弱で、思ったような変換ができなかったり残念な部分もあった。

% [game][雑談] もう少しどうにかならんのか PSP は

AC 繋いでるのに「バッテリー残量が足りません」とか言ってファームウェアのアップデートができないってアホじゃねえ? 毎回のようにこれで出鼻を挫かれるんだよな。 そのくせバッテリー満タンでも AC 未接続だと文句言うんだから、どうかしてる。

つか、いずれバッテリーがへたって最終的に使えなくなったら、AC 接続でゲームはできるのにファームウェアは新しいバッテリー買わないかぎりアップデートできないってことか? 死ねばいーのに。 あと、いつの頃からか無線 LAN を使うと充電状態が切れるようになってたり、もうねアホかとバカかと。

% [game] かまいたちの夜 x3

当然買った。 複数の視点から事件を見る構成が燃える。 攻略はめんどくさそうだが(苦笑

前作の純粋な続編なんで前作の知識必須だが、前作、前前作の必要な部分 (メインシナリオ) は一緒に入ってるんで初めての人でも安心。

ともあれ、しばらく眠れない日々が続きそうだ。

本日のツッコミ(全1件) [ツッコミを入れる]

% takano32 [T9ですかー 確かにパソコン用のは見ませんね]


2006-07-28 [長年日記]

% [雑談] ボーダフォン、ポータルサイトの名称を「Yahoo!ケータイ」に (ケータイWatch)

via halchan's diary.

これはひどいw このセンスの無さは何なのか……わしも次の機種変時にはキャリア変更するだろうな。

% [雑談] 完全無料放送「GyaO」でボトムズ全52話配信決定! (ボトムズweb)

via del.icio.us/otsune.

ぬおぉぉぉ。見る。踏んばりながら見る。


2006-07-29 [長年日記]

% [game] かまいたちの夜 x3 完

基本的に『真相編』一本に絞った作りなので小さくまとまった感はあるが、なかなかおもしろかった。 プレイ時間は約 25 時間 (木曜日に始めて土曜の午前でこの時間って……やりすぎ)。 最後のオチは個人的にどうかと思うけど、ともかく 3 人がそれぞれ独自に動きながらも互いに影響しあって真相に向かっていくのは楽しかった。 『街』のノリではあるけど、全員が同じ事件に関わってる分、話が濃密だね。 「つづく」みたいな無駄に話の流れを堰き止めるものも無いし。

細かい部分は何書いてもネタバレになると思うんで、わりと大ざっぱに書くけど、全体的に言って一作目のセルフパロディと言うかオマージュと言うか本歌取りと言うか、そんな感じだったと思う。 いたるところで一作目のシチュエーションを思い出すし。 ストーリー的な知識としては 2 だけやってれば良いと思うんだけど、ほんとの意味で楽しむにはむしろ 1 をやってないといけない感じ。 そういう意味では、1 と 2 が含まれた形でリリースされたのは必然だったんだろうなあ。

ちなみに『真相編』の『完』を見ると『番外編』(ピンクのしおり) が、『番外編』の『完』を見ると『犯人編』(紺色(?)のしおり) が、そして全てのバッドエンドを集めると真相編の後日談 (金のしおり) が追加される。

犯人編のネタがものすごく見覚えあるんだけど、何で見たんだったか思い出せないんだよな。 つくづく自分の記憶力の無さがうらめしい……

おまけでバッドエンドを集めるコツを書いとくと、誰かのシナリオでバッドエンドを迎えると、ほぼ間違いなく他のキャラのシナリオでも対応したバッドエンドが起こってるので、選択肢を選び直す前に回収しておくのが吉。 あと、三回連続で正しい(?)選択肢を選ばないと見れないバッドエンドもある。

推理物としてはわりと簡単な部類だと思うけど、複数の人物の視点から謎が解けていく様子を見るのはとても楽しいので、そういうのが好きな人は、ぜひどうぞ。 小説ではちょっと味わえない類の楽しさだと思う。

……さて、わしは一眠りしたら、せっかく入ってる 1 と 2 もやるんじゃよー(病気です)。

% [雑談][PC] Touch Me Key

この前の変換の話に takano32 さんからツッコミを貰ったんで、「ほー、そういう名前 (T9) があったのか」と思ってちょっと検索してみたら見つけたのが上記ページ。 非常に楽しげ。

関係無いけど、specification のページが微妙におもしろい。

本日のツッコミ(全2件) [ツッコミを入れる]

% あろは [> T9 私が学部時代所属していた大学の研究室でも,ここらへんの話題を扱っていたので,懐かしい気分になりました. ..]

% jijixi [なかなか夢のある話ですね。 > 学習量によらずデータ量は不変 って辺りがシブい。]


トップ 最新 追記

日記ってのは本来、自分で読み返すためにあるもんだよなあ……
もしくは有名人になったら死後に本になったりとかか?

RSS はこちら

jijixi at azito.com