Control.Monad.foldM_ ではなく Data.Vector.foldM_ を使いましょう

Mutable array の prefix sum を余計なメモリを消費せずに計算したい時など、「基本的には mapM_ なんだけど、map してる関数の挙動がそれまでに map し終わった部分の結果に依存して欲しい」ような計算の時、私は foldM_ を使ってたんだけど、これが時々、恐ろしく遅い。例えば

psum :: STUArray s Int Double -> Int -> ST s ()
psum a n = foldM_ f 0 [0 .. n]
    where f x i = do y <- readArray a i
                     let z = x+y
                     readArray a i z
                     return z

なんて書くと、配列の大きさが 100M 要素ぐらいになった時点で既に 11 秒とか掛かったりする。それに対して、手動で最適化した以下のようなコードでは 1.2 秒で済むので、オーダーが丸ひとつ違ってしまう。

opt_psum :: STUArray s Int Double -> Int -> ST s ()
opt_psum a n = go 0 0
    where go x i = when (i <= n) $ do
                     y <- readArray a i
                     let z = x+y
                     writeArray a i z
                     go z (i+1)

原因は foldM_ が left-fold な事による (っぽい)。foldr で定義できる forM_ なんかと違って、foldM_ は リストを絶対に左から右へ消費していかなくてはならないので、旧来の融合変換が適用できない。*1みたい。

で、勿論上記のような手動で最適化したやつを書くのはめんどくさいので、どうすればいいかというと単に Data.Vector を使えば良い。

import qualified Data.Vector as VU
vector_eft_psum :: STUArray s Int Double -> Int -> ST s ()
vector_eft_psum a n = VU.foldM_ f 0 (VU.enumFromTo 0 n)
    where f x i = do y <- readArray a i
                     let z = x+y
                     writeArray a i z
                     return z

これだけで opt_psum とほぼ同じ性能が出る。*2マニュアルによれば enumFromTo は遅いらしいけど、この場合は融合変換できるので enumFromN とあんまり変わらない。

まあ Data.Vector 使えば融合変換が凄いよ、というのは知れ渡ってる事実なんだけど、正直リストの [0..n] という構文の直観的なわかりやすさが捨てがたくて Data.Vector は個人的に敬遠してたんですよ。だけどこれからは foldM_ を使う時は Data.Vector 一択になりそう。

*1:呼び名は忘れたけど Wadler のやつ。"Wadler deforestation" とかでググりたも。

*2:若干のオーバーヘッドはあるが、気にならないレベル。

Ubuntu で Ctrl - Alt - t で terminal が起動するのを無効化する

Ubuntu 12.04 では「システムの設定」(gnome-control-center) から キーボード→ショートカット→独自のショートカット で出てきた t で terminal を起動する動作は無効化できなくなっている。/usr/share/gconf/defaults/mutter-common が同ショートカットを設定していて、それがどういうわけか変更不可能になっている模様。とりあえず mutter-common をアンインストールしたら治った。

この解答集の注意点

診断で表示される問題は、

【教科書NEW CLOWNより】「…」を英訳せよ

という書式で、問題と【】内が別々に選ばれますが、ここでは【】の外の部分だけ (つまり問題文だけ) を見出しとして載せています。

基本的に本気で解くことを想定して作った問題ではなくてネタなので、「正答例=大真面目な解答」と「模範解答=笑える解答・常識的な解答」は異なります。模範解答は主に TOPSY で目についたものを拾っていますが、全部見たわけではないのでもっと面白いのがあれば教えて下さい。

ありそうな質問とその答え

Q. 本当にこんな問題が出てる入試や教科書があるの!?

A. んなわきゃねぇwww こんな問題使ってたらクレーム来るwww

Q. でも、NEW CLOWN って教科書、ウチの学校で使ってたよ。【教科書 NEW CLOWN より】なんて、嘘つき!

A. そ れ は N E W C R O W N だ
マジレスすると、教科書名も問題も捏造です。あくまでネタです。

Q. 本当に回文を回文に翻訳なんてできるの!?

A. 無理無理無理無理! 回文のままってのは無理ゲーです。いや、できる人もいるかも知りませんけども。

Q. この解答が正しい保証は?

A. 個人が遊びで作ってるページにそんなものは存在しません。

Q. 解答自体がよくわかんない

A. ここのコメント欄でも、ツイッターでもいいので具体的に質問してもらえれば答えられるかも知れません。

Q. 文字数厳しいんだけど

A. 仕様です。すまんこってす。

Q. こんなところに問題一覧載せてたら、診断メーカーの方、意味無いだろ。

A. うん…… いや何かもう一通り遊んでもらったから、いっかなぁって思って…(´・ω・`)

「すしやでははははははといたまえといたまえといいたまえ」をえいごにしなさい。(※小学校入試なので問題文は平仮名です☆)

寿司屋では母は母と居たまえと板前と言いたまえ。
「母と居たまえ」が母と板前さんのセリフです。「母は「母と板前と居たまえ」と言いたまえ」でも可。

正答例

At the sushi bar, mother shall say with the chef, "stay with mother."

「言いたまえ」がちょっと古い言い回しなので対応部分を shall にしましたが、わりとどうでもいいです。

「ここのこのはははこのこのこのこのはのはこのこのこのはのもようはきれいだといっていた」をえいごにしなさい。(※小学校入試なので問題文は平仮名です☆)

ここの子の母はこの子のこの木の葉の箱のこの木の葉の模様は綺麗だと言っていた。
最初を「ここの木の葉」と解釈すると、多分真ん中の「この×4」で詰まります。

正答例

最初の「ここ」と「木の葉の箱」をどういう意味で解釈するかと模様のある木の葉の位置をどうするかによりますが、「ここのお宅」「木の葉を入れる箱」「模様のある木の葉は箱にあしらってある」と解釈するなら

This house's kid's mom was saying that the pattern on this foliage on this kid's box for keeping leaves is pretty.

とか。所有格二連発ってたしかあんまり行儀が良くないんですけど、of とか使い出すとわかりにくくなるので却下。

模範解答

@maih1melt 「There are many many Konoha !!!」

Yes, there are so many!

@yuuna_ninetail 漢字って大切だと思いました。

真面目な話、日本語で漢字廃止運動とか自殺行為だと思ってます。