インチキデータ再帰と単位換算

[追記：データ再帰を使ったコードを書こうと思っていたのですが、出来上がったものはデータ再帰に放っていませんでした…とほほ…/追記]
また、データ再帰のことです…
Recursive Monadic Bindingsの論文などを眺めていると、よく出てくるのが電子回路のサンプルです。まだ使ったことはないのですが、どうやらmdoと電子回路の表現は相性が良いようです。

では、電子回路ではよくあって、プログラムではあんまりよくないものは何でしょう？ほかはよくわかりませんが、フィードバックループは電子回路ではよく出てきますね…そもそもループができていなくては電気が流れないので｢回」路になりませんよね…

中学生のころは半田ごてを握ってキットの時計とか作ったりしてましたが、回路を細かいところまで理解するところまでは行きませんでした…まぁ、回路図を見ても体がかゆくならない程度には慣れていますが…フィードバックといって思い出す回路といえば、オペアンプです…アンプというぐらいですから何か増幅するのだろうということしか理解はないのですが、回路図を引っ張ってくると、こんな感じです：

相変わらずヘタクソな図なわけですが、真ん中の三角がオペアンプ、出力(Out)から入力(In)に向かってフィードバックのラインがありますね…

電子回路では頻出するフィードバックループなのですが、プログラムではオペアンプを関数と見立てるとなるほど再帰呼び出しをしているようにも見えなくはないですねぇ…関数の帰り値がまた関数へのパラメタとなってわたっていくわけです…fixの定義を見ているようでもあります：

 fix f = x where x = f x

ただし、いまだにfixは使いこなせません。何しろ関数f::a->aにパラメタをfixの外側から渡す方法がわからないわけです…

今日も懲りずにfixを手なづけようとごにょごにょやっていたのですが、結果としてfixは使っていないのですが、ちょっとだけ面白いものができました。

お題にしたのは割りと単純にメートルとセンチメートルの単位換算をやる関数です。時々アプリのダイアログなんかの中で、入力がいくつかあって、お互いみんな中でつながっていて、どれか一つに値を入れるとほかの値が自動的に決定するみたいなのありますよね…
Excelで数式を使うと入力セルを一つ決めれば似たようなことができるわけですが、ここでは全ての入力が同時に出力としての機能を持つところがひねりです。
メートルからセンチメートルは (* 100) という結線でつながって、更にセンチメートルからメートルが(/100)という結線でつながっているループを形成しているとも言えるようないえないような…？

単位の換算をする関数を

mcm :: (Float, Float) -> (Float -> Float)

というシグネチャにしてみました。ねらいは入力と出力のタプルをデータ再帰でつなげてやることです。fstがメートルの値をsndがセンチメートルの値をそれぞれ担当します。

いくつかトライして無限再帰を経験した後に動くようになったのが次のようなコードです：

module Main
	where

import Debug.Trace

mcm :: (Float, Float) -> (Float, Float)
mcm (m, cm) = trace "mcm" 
	(trace "cm" $ cm / 100, trace "m" m * 100)

toM i = m
	where
		(m, _) = mcm (m, i)

toCm i = cm
	where
		(_, cm) = mcm (i, cm)
		
main = do
	print "toM 100"
	print $ toM 100
	print "toCm 1"
	print $ toCm 1

コードの挙動を確認するためにmcmにはtraceがいっぱい入ってますが、要は：

mcm :: (Float, Float) -> (Float, Float)
mcm (m, cm) = (cm / 100, m * 100)

ということで、メートルとセンチメートルの関係をcm->mとm->cmという2つの違う形で繰り返しただけです。当初の目論見どおりには行かずmcmの中ではデータ再帰が使われていませんが、動いてくれただけで万々歳です。変わりにtoMとtoCmの中でデータ再帰が使われています…

実行結果は以下のとおり：

"toM 100"
mcm
cm
1.0
"toCm 1"
mcm
m
100.0

面白いのはトレースでもわかるように、mcmではm->cmとcm->mの2つの計算が指定されているのにtoMもtoCmもそのどちらか一つしか実行しないことですね…toMやtoCmで＿を使って必要のない値をマスクしていることで実現しています。ここをiに置き換えると無限再帰に陥ります。

データ再帰の振る舞いはなんだか不思議ですね…無限再帰と正常動作の間を行ったりきたりするのでデバッグがちょっと大変ですが…

今日はこの辺で。
ではでは。

fixを無限再帰させないもう一つの方法

引き続きfixのことです…

昨日の文章を書いた後、しつこくRecursive Monadic Bindingsの論文を眺めていました…この論文は主にモナド関数を使ったfixの話なのですが、例のいくつかを眺めていてもfixの使い方が
fix :: ((a -> a) -> a -> a) -> a -> a
ではなく
fix :: (a -> a) -> a
のような感じなのです。うなりながらもちょっとコードをいじくりまわしているうちに(a->a)->aなfixでも無限再帰に陥らない方法があることに気がつきました。
僕が気がついた方法は以下のとおり：

test = fix foo
	where
		foo x = 1
main = print test
=>
 1

またしても、当たり前なのですが、これもまたfixを(a->a)->a的に使ったら必ず無限再帰だと思い込んでいた頭には新鮮でした。ここでも再帰をするかしないかは(a->a)な関数に任されていたのです。

さて、変数というのは実は値を引き出す以外にもう一つできることがありますね…それは値を代入することです…Haskellは純粋関数型なので普通には宣言したときに値が決定してしまうので代入という考え方はあまりしないですよね…でも、実はこんなことができちゃうようです：

test = fix foo
	where
		foo x = let x = 1 in x

main = print test
=>
 1

つまり、Haskellの変数は一度宣言したら値が変えられないのではなくて、一度値が決定したらもう変えられないということなんでしょうか？ひょっとしたらこのコードが動く理由はfixによるところもあるのかもしれません。x = foo xというのは実はxが簡約途中の中間形態でx=1とすることでfoo x = 1 であることが判明してx = 1が簡約の結果として決定するような？

そもそもimmutableな変数で値を宣言時に指定しなくて良いのは関数のパラメタぐらいのものですね…と思ってfixの外で同じことをやってみました：

foz x = let x = 3 in x

main = print $ foz 4
=>
3

ということでfixとは関係なくできることのようです。でも、

foz x = let x = (3 + x) in x

main = print $ foz 4

とやるとコンパイルはできても無限再帰になって終了しません…x = (3 + x)がfixの要領で再帰を起こすんですね…

そして、前回(a->a)->aなfixが使えない理由のもう一つとして書いたことが出入り口がないことでした…でもここまで見てわかるように無限再帰さえ阻止できればちゃんと値は帰ってきますね…それじゃぁ、入り口はどうにかならないでしょうか？

そこで気づいたのがこれです：

foo a = fix (\x -> a + 4)

main = print $ foo 5
=>
9

これで入り口も確保できました。しかしながら僕のここまでの理解では(a->a)->aなfixではここで挙げたサンプルのように再帰をまったく行わないモードか無限再帰で中断するモードのコードのどちらかしかかけませんでした。((a->a) -> a -> a) -> a -> aなfixのときのように再帰を自由自在に操る方法は今のところ見つかってません…

今日はこの辺で…

ではでは。

fixを使うためのヒント

効率化の話はなんだか疲れるので、またデータ再帰の話へ脱線…
id:dachs_hippoさんのfixに関する記事をボーっと読み返していてあることに気づきました…

氏のサンプルのひとつは階乗の計算だったわけですが：

import Data.Function

g :: (Int -> Int) -> Int -> Int
g rec 1 = 1
g rec n = n * (rec $ n - 1)

main = print $ (fix g) 4

ここに出てくる関数gは無理にfixを使わなくても当然かけるわけです…

g :: Int -> Int
g 1 = 1
g n = n * (g n - 1)

main = print $ g 4

この2つを比較して見えてくることは、fixを使ったほうで出てくるgの第一引数recはほとんど関数g自身の別名のような存在だということです…逆に考えれば、fixを使ったコードが書きたければ、まずは普通の再帰呼び出しのパターンでコードを書いて、再帰呼び出しの部分だけ書き換えればよさそげです。

もう一つ気づいたこと、それはfixを使ったコードでもっと単純な例があるということです。

import Data.Function

g :: (Int -> Int) -> Int -> Int
g _ i = i

main = print $ (fix g) 4

まぁ、こうやってさらしてしまうと｢当たり前じゃんか！｣なわけですが、個人的にはfixというとなんだかYコンビネータによる再帰呼び出しが必ず起きているような気がしていたので…実際には、再帰をするかしないかは関数gに完全に任されているわけですね…

もう、何度目かわかりませんが、fixの定義を見てみます：

fix ::  (a -> a) -> a
fix f = x
	where x = f x

ここで定義されている変数xはその宣言部で自分自身を参照しているデータ再帰パターンです。ということはC言語などで出てくる

x = x + 1

のようないんちき数学な式ではなくて、

x = f x

はむしろHaskellのプログラムの内部表現形式であるところのグラフ表現として解釈したほうがよさそうです。つまり、関数fのパラメタと帰り値が同一な変数なわけですから

のようなループを描いているようなイメージです…こうなっていたらfix idなんてやった時点で無限再帰ループ後スタックオーバーフローに陥るのも無理はないような気になってきます。

でも、dachs_hippoさんの話にもあったようにfix::(a->a)->aのaをb->bに置き換えると話が変わってきます。

fix :: ((b -> b) -> b -> b) -> b -> b

のようなイメージでしょうか…なんだか複雑ですが、aの型が単なる値から関数になったことで出入り口のなかったfix fに入り口と出口ができました。

ということで、なんとなくfixを使ったコードはかけるようになってきたような気がするのですが、一体なんでfixを使ったコードを書きたいのかがいまいちわからんです…

WikiPediaのラムダ計算の項を読むと、ラムダ計算の理論にとってのYコンビネータの重要性はラムダ計算では無名関数しかないので再帰呼び出しをする計算を書きたかったらYコンビネータを使うしかないからということのようです…Haskellでは関数に名前をつけることは簡単にできますね…

今読んでいるRecursive Monadic Bindingsの論文を眺めた感じではfix/mfixの有用性の一部はControl.Arrow.loopのようにデータ再帰によるところがあるようです…しかしながら、僕にはfixを使って再帰的データとして定義されていxをうまく利用するコードが思いつきません…

きょうはこのへんで。
ではでは。

Data.List.unionは結構重そう

数独ソルバー効率化第2回です…今回も20％程度の効率化なのですが内容が面白みにかけるのでさらっと…

数独では一つのマスの値が決定したときにそのマスと依存関係にあるマスの制約条件が厳しくなります。時にはそれだけで値が決定してしまうこともあるわけです。
一つのマスについて3種類の依存関係があって、例えば一番左上のマス（０，０）は

x軸：[(0, y) | y <- [1..8] ]
y軸：[(x, 0) | x <- [1..8] ]
3x3: delete (0, 0) [(x, y) | x <- [0..2], y<-[0..2] ]

のマスと依存関係があるのですが、上の3つの式の結果はお互いにダブっている部分があるので、それを取り除くと合計20のマスと依存関係があることがわかります。

今回のソルバーでは依存関係を座標のリストで持っているのですが、同じx座標にあるますの間ではx軸に関しての依存関係は同じデータなので、一つのリストを共有させています。つまりx,y軸そして３ｘ３のワクにに関してリストがそれぞれ9本、合計27本のリストを保持しています。

そして、値を一つ決めるたびにそのマスに依存するマスのリストを作るのですが、上でも述べたようにデータのダブりを取り除く必要があります…（ダブったデータでも動くようにできないかという話もありますが、それは今後の課題ということで。)

そして、重複を取り除くのに使っていたのが次のような関数でした：

uniqs :: [Pos] -> [Pos] -> [Pos] -> [Pos]
uniqs xs ys zs = xs `union` (ys ++ zs)

この関数が約15.5万回呼び出されて実行時間の27% (約2秒）、消費メモリ全体の22%(144Mバイト）を使っています。メモリ消費量に関しては一回あたり972バイトと結構な量です。実行時間は4秒を切っているので実に半分近くの時間をこの関数の中で消費していることになります。

ところで、この関数は最初のバージョンではpropagate関数の一部だったのでプロファイルには出てきていませんでした…前回の効率化のときに一つの関数として独立化したためにプロファイルで見えるようになったわけです。

コードのほうなのですが、Data.List.unionを使っています:

union :: Eq a => [a] -> [a] -> [a]

この関数は2つのリストをとって、その2つの和集合を返すのですが、1つ目のパラメタの中の重複要素は取り除いてくれないという特徴があります。ところで、今回unionをかけているリストなんですが、実はxsとysははじめから重複がないことがわかっています。でもzsはxsともysとも重複要素を持っている可能性があります…ということはzsが空リストのときにunionを使うのは無駄ということですね…というとでuniqsを次のように書き換えてみました：

uniqs :: [Pos] -> [Pos] -> [Pos] -> [Pos]
uniqs [ ] [ ] [ ] = [ ]
uniqs xs [ ] [ ]  = xs
uniqs [ ] ys [ ] = ys
uniqs [ ] [ ] cs = cs
uniqs xs ys [ ] = xs ++ ys
uniqs xs@((x,_):_) [ ] cs           
　　　= xs ++ (filter (\(x', _) -> x' /= x) cs)
uniqs [ ] ys@((_,y):_) cs           
　　　= ys ++ (filter (\(_, y') -> y' /= y) cs)
uniqs xs@((x,_):_) ys@((_,y):_) cs 
　　　= xs ++ ys ++ (filter (\(x',y') -> x' /= x && y' /= y) cs)

uniqsの最後の3つのケースに関してはxsがx軸の値が同じもののリストであること（ysも同様）を利用して効率化を図っています。

なんとも地道な効率化ですが、最初に述べたとおりこの変更で実行時間は3秒を切り、メモリの使用量も620Mバイトから520Mバイトと更に100Mバイト削減できました。あと、この変更をした後プロファイルをとってみるとuniqsのコストがメモリ時間ともにゼロになってしまいます。これはおそらくプロファイラ側の問題なのだろうと思います。

ではでは。

データ再帰という考えと双方向リスト

今日はちょっとコードの効率化の話をいったんお休みして、別の話を書きたいと思います。

以前に書いたControl.Arrow.loopでも実はさりげなく出ていたのですが、Haskellではletとwhere節の部分でちょっと変わったことができます。

Control.Arrow.loopの定義を見てみます：

instance ArrowLoop (->) where
　　loop f b = c where (c,d) = f (b,d)

ちょっと不思議な関数定義なわけなんですが、特に変わっている部分があります。…それは変数dの宣言部分です。

　(c,d) = f (b,d)

loopの説明によると、これの影響で変数dは再帰の全ての段にわたって同じインスタンスが参照されているということらしいです。つまり、whereとletでは定義内での変数の再帰的参照が許されているようです。
おかげで、こんなこともできます。

　a = b
　b = a

まぁ、もちろんどこかでa, bそれぞれに値を与えてやる必要があるわけですが…

ここでちょっと双方向リストについて考えてみたいと思います。リストの各要素が自分の前と後の要素へのポインタを保持しているわけです。型自身の定義としては：

　data DList a = Empty | MkDList a (DList a) (DList a)

見たいなものが妥当なところでしょう…からのリストはEmpty、要素が一つしかないリストは：

　one a = MkDList a Empty Empty

とやればいい。では、要素2つのリストはどうやったらいいでしょう？

　two a1 a2 = MkDList a1 Empty ????

うーん、どうやったら2つのDList型のインスタンスを作ってお互いを参照できるでしょう？ここで、先ほどのwhere節の再帰的参照が生きてきます。

　two a1 a2 = l1
　　where
　　　l1 = MkDList a1 Empty l2
　　　l2 = MkDList a2 l1 Empty

とやればいいわけです…なんだか面白くなってきました…ちなみにこの参照パターンはデータ再帰(data recursion)と呼ばれているようです…僕には直感的に理解できる名前ではなかったですが…

それじゃあ、任意の長さのDListを作る関数:

　dlist :: [a] -> DList a

はどうやったらかけるでしょう？最初に思いついたのはApplicativeを使ったバージョンです：

import Control.Applicative
dlist :: [a] -> DList a
dlist as = dl
　where
　　dls@(dl:dlss) = getZipList $ 
　　　( (ZipList.(map MkDList) ) as) <*> prvs <*> nxts
　　prvs = ZipList $ Empty : dls
　　nxts = ZipList $ dlss ++ [Empty]

これはコンパイルは通るのですが、いざ実行させてみるとメモリーが足りなくなって中断してしまいます…なぜかは良くわかりませんが、おそらくprvsかnxtsの定義か参照に問題があるのでしょう…きれいにかけたと思ったのですが、動かないんじゃぁしょうがありません…

これがダメならと思って思いついたのが、オーソドックスに再帰を使う考えです：

dlist as = _dlist as Empty

_dlist :: [a] -> DList a -> DList a
_dlist [ ] _ = Empty
_dlist (a:as) prv = this
　where
　　this = MkDList a prv nxt
　　nxt = dlist as this

これはうまく動いてくれます。DListをもらってそれをトラバースする関数も書いて見ました：

next :: DList a -> DList a
next Empty = Empty
next (MkDList _ _ n) = n

prev :: DList a -> DList a
prev Empty = Empty
prev (MkDList _ p _) = p

この辺はごくシンプルですね…次にDList版のtakeを書いてみました。双方向なのでtakeNxtとtakePrv
です…

takeNxt :: DList a -> Int -> ([a], DList a)
takeNxt Empty _ = ([ ], Empty)
takeNxt _ 0 = ([ ], Empty)
takeNxt lst@(MkDList a _ nxt) 1 = ([a], lst)
takeNxt lst@(MkDList a _ nxt) i = (a:as, nxt')
　where
　　(as, nxt') = takeNxt nxt (i - 1)

takePrv :: DList a -> Int -> ([a], DList a)
takePrv Empty _ = ([ ], Empty)
takePrv _ 0 = ([ ], Empty)
takePrv lst@(MkDList a prv _) 1 = ([a], lst)
takePrv lst@(MkDList a prv _) i = (a:as, prv')
　where
　　(as, prv') = takePrv prv (i - 1)

ちょっとややこしいですね…これを使えば、

print $ takeNxt 5 $ dlist [1..9]
==> [1, 2, 3, 4, 5]

print $ takePrv 3 $ next $ next $ next $ next $ dlist [1..9]
==> [5, 4, 3]

なんてことになります…ふむふむ。

それじゃぁ、DListでループしているものはどうやったら作れるでしょう？先頭のprevは最後尾、最後尾のnextが先頭になるようにしなくてはいけません…DListのトリッキーなところは、Immutableなので、インスタンスの生成時にリンクを全て設定してやらなくてはいけないことです。

ということは、先頭要素を作るときには最後尾の要素を参照する変数がなくてはいけないことになります…むむむ。と、ここで、最初に出てきたControl.Arrow.loopがどうやら使えそうなことに気づきます…やってみようということで書いてみたのがこれ：

import Control.Arrow

dlistLoop :: [a] -> DList a
dlistLoop as = (loop _dListLoop) (as, Empty, Empty)

_dListLoop (([ ], hd, prv), m) = (hd, prv)

_dListLoop ((a:as, Empty, Empty), m) = (this, m')
　where
　　this = MkDList a m' nxt
　　(nxt, m') = _dListLoop ((as, this, this), m)

_dListLoop ((a:as, hd, prv), m) = (this, m')
　where
　　this = MkDList a prv nxt
　　(nxt, m') = _dListLoop ((as, hd, this), m)

ちょっと解説すると、_dListLoopの入力パラメタhdは最後尾に先頭要素の参照を渡すためのもの、prvは直前の要素を渡すためのものになっています…

実際に使ってみます…

main = do
　print first5
　print prev3
　print next5
　　where
　　　lst = dlistLoop [1..9]
　　　(first5, l5) = takeNxt lst 10 
　　　(prev3, p3) = takePrv l5 3
　　　(next5, n5) = takeNxt p3 5

==>
[1,2,3,4,5,6,7,8,9,1]
[1,9,8]
[8,9,1,2,3]

ということで、1から9までの要素を含む、ループしたリンクリストですから、先頭から要素を10個とると、
[1,2,3,4,5,6,7,8,9,1]となりますし、1のところから後ろ向きに要素を3個とると[1, 9, 8]となりますね…
どうやらちゃんと動いているようです…

C/C++ではリンクリストは双方向でも片方向でも、ループしていてもしていなくても、コードはややこしいですが、ポインタのことさえわかれば書くことはできますね…でもHaskellではループした双方向リンクリストはControl.Arrow.loopのようなちょっと不思議な関数の助けがなくては作れない…まぁ、Mutableなバージョンであればそんなことはないはずですが…

そして、リストと違って、要素の変更の際のコストは常に全体のコピーになるはずです。要素一つを書き換えるためにはそのようそのために新しいDListをアロケートしなくてはいけなくて、ということはそのリストの両側の要素のポインタをアップデートしなくてはいけない…それが回りまわって、DList全体を書き換えることになります。
DListがループしていたとすると、要素を全部リストに取り込んで、データの書き換えをした後、dlistLoopで新しいDListを作り直したほうが話が早そうです…そのためにはループしたDListから全ての要素をとる関数が必要になってきますね…どうやったらかけるでしょう？

getAll lst = _getAll lst lst
_getAll Empty _ = [ ]
_getAll lst@(MkDList a _ nxt) hd
　| lst == hd = [ ]
　| otherwise = a:(_getAll nxt hd)

なんてやってみたのですが、これは無限ループに陥ってしまって終了しません。ｔraceをつけたりしてみた感じでは

　lst == hd

がdeepな比較を行っているために終了しない感じです…むむむ…どうやればよいのでしょう…

今日はこの辺で…
ではでは。

リスト操作のコスト

さて、前回のプロファイルの結果で明らかになった数独ソルバーの最悪のホットスポットはexcludeという関数だったのですが、一体何をやっていたのでしょう…500万回呼び出されて250Mバイトものメモリーを消費していました…

excludeは実は次のような関数でした…

exclude :: (Eq a) => a -> [a] -> [a]
exclude a as = filter (/= a) as

まぁ呼び出し一回あたりのコストにしてみれば毎回約50バイト程度なので実はそんなに派手なことをやっているわけではないのです…でも、この関数はリストをパラメタに取ってそれを加工したものを返しています。リストはImmutableなので入力のリストと違うものを返さなくてはならないときはリストの複製を作らなくてはならないわけです。これがどうやら毎回50バイトのメモリ消費の理由のようです。

そしてfilterをしていますから毎回O(N)のトラバースをしていることになりますね…

具体的な実行イメージをお伝えするためにexcludeが一体何をしていたかを説明します。

今回のコードではパズルのステートは大きく分けて2つのデータ型で保持していました。一つはパズル自身、９ｘ９、合計81個のリストがそれぞれのマスに適用できる可能性のある数字を保持しています。まっさらな数独パズルの場合は81個の[1..9]が並んでいることになります。そして選択をしていくたびにその影響を受けるマスから数字をexcludeしていくわけです。
もう一つのデータ型はマス同士の間の依存関係を表現していました。数独ではそれぞれのますは横軸、縦軸、そして３ｘ３のマスの3種類の依存関係ルールによって関連付けられています。これがまたリストとして保持されています。あるマスの値が決定したときに、この依存関係リストをたどって値の決定をほかのマスに反映させていきます。そして、それが終了した時点で依存関係をリストからexcludeします。

つまり、excludeが今回のコードで扱っているリストは重複データがないという特徴があるわけです。

さて、excludeで使われているfilterなんですが、だいたいこんな感じの関数ですね：

filter :: (Eq a) => (a -> Bool) -> [a] -> [a]
filter _ [ ] = [ ]
filter f (x:xs)
	| f x = x : xs'
	| otherwise = xs'
	where
		xs' = filter f xs

ということで、コードを見ていると、この関数には2つの特徴があることがわかります。一つ目は、filterは与えられたリストを毎回必ず最後までスキャンすることです。これは今回のように取り除きたい値が必ずあって、なおかつ1つしかないとわかっているときには無駄ですね…

そして、もう一つ気づくことは、filterは結果的にリストに何も変更を加えなくても、返り値となるリストは常に入力のリストのコピーであるということです。つまり、filterを呼び出すたびにリストのコピーをやっていると思って間違いなさそうだということです。

リストは一方向リンクリストなわけで、

[1, 2, 3]

は

{Box 1, List *} -> {Box 2, List *} -> {Box 3, List*} -> NULL

といったような感じの内部表現になっているわけです。ここで、BoxはHaskellのLazyさを実現しているBox型のことです…
それでは　(x:xs) = [1, 2, 3]とやったときのxとxsはそれぞれどんなデータを参照することになるのでしょう？
それはおそらく：

x = Box 1, xs = {Box 2, List *} -> {Box 3, List *} -> NULL

といった感じでしょう。

つまり、xを先頭に持つリストx:xs'を作ろうと思ったら、新しくリスト構造体をアロケートしなくてはいけないということです…(：)演算子が1回実行されるたびにリスト構造体が一つアロケートされていると思ったほうが良いということのようです。

まぁ、もちろん、filterも(：)演算子もすべてLazyですから計算結果が全て参照されない限りはリストの要素全てが再生成されるわけではないですね…

fl = filter (/= 2) [1, 2, 3]

とやったら、中身を参照する前のflは

｛Box filter (/=2) [1, 2, 3]}

という内部表現になっているのだろうし、head flとやった後では

{Box 1, List *} -> {Box filter (/=2) [2, 3]}

となっているはずです…

しかしながら、今回のコードではexcludeは同じリストを何度も何度もスキャンして、最終的にはそれぞれのリストの要素が空になるか、あるいは1つになるまで呼び出されます…試行が失敗するときは、そこまで到達しないケースもあるのでしょうが、おそらく、過半数のケースではLazyはあまり助けになっていないのではないかという気がします…この無駄を取り除いてみたらどうなるでしょう？

Preludeを見てみるとdeleteという関数があることに気づきます:

delete :: (Eq a) => a -> [a] -> [a]
delete _ [ ] = [ ]
delete a (x:xs)
	| x == a = xs
	| otherwise = x: delete a xs

といった感じの関数になるかと思うのですが、これはfilterよりも実行速度、メモリ消費の面でも若干効率が良いことがわかります。deleteはリスト内に同じ値が繰り返しある場合は初めの1つしか取り除いてくれないわけですが、そのトレードオフのおかげで、リストの全要素のスキャンは削除しようとしている値が最後にあるか、リスト内に存在しないときに限られています。依然としてワーストケースはO(N)ですが、平均ではO(N/2)で実行してくれますね…
さらに、削除に成功したときはxsをそのまま返してくれるので、リストのコピー生成がある程度抑えられるという利点もあります。
delete 1 [1, 2, 3]
とやったときはリスト構造体はまったくアロケートされないはずですね…リストは先頭の変更に関してはとても効率が良いけれど、変更がリストの後ろのほうになればなるほど効率が低下するということになりますね…

プロファイルがとてもためになる理由の一つはプログラムの実際の挙動に対する理解が深まるところにありますね…実際に動いているところをこうやって見るまではこんなところまで具体的なイメージを持つことはできませんでした…

ということで、excludeをdeleteに置き換えた結果、僕の数独ソルバーは実行速度がほぼ15%アップして約4.5秒だった実行時間が4秒を切り、メモリー消費は約20%減少して、780Mバイトから620Mバイトになりました。実に100Mバイト以上の削減です…昔のハードディスク丸ごとぐらい減っちゃいました…ははは。

きょうはこのへんで。

ではでは。

Haskellのプログラムをプロファイルしてみる。

GHCではプログラムのプロファイルをとってくれる機能があります。
数独ソルバーのパ実行フォーマンスを見るのに使ってみました。

GHCのマニュアルを見れば出ていることなのですが、GHCのプロファイラはいくつかモードがあって、ものによってはメモリの消費情報をグラフ化してくれたりするものもあるようですが、今回は「ふつう」のやつをやってみました。実行速度とメモリの消費を関数ごとに計測してくれます。

プロファイルを行うには2つのステップが必要です。
まずはプログラムを次のオプションを追加してコンパイルします。

• O2 -prof -auto-all -o Main

そして、出来上がった実行ファイルを次のオプションをつけて実行してみます。

1. RTS -p

実行が終了した後に *.profというファイルが生成されています。これがプロファイルの結果の書かれたファイルになります。

プロファイル結果の例はこんな感じです。

Time and Allocation Profiling Report  (Final)

  foo +RTS -p -RTS

total time  =        4.34 secs   (217 ticks @ 20 ms)
total alloc = 812,398,524 bytes  (excl. profiling overheads)


    

    
COST CENTRE　
    
%time
    
%alloc
    
    

    
exclude
    
38.2
    
35.8
    
    

    
propagate
    
33.2
    
26.1
    
    

    
set
    
18.9
    
27.0
    
    

    
excludeM
    
3.7
    
1.3
    
    

    
uniq
    
2.8
    
4.6
    
    

    
tryChoices
    
1.8
    
5.1
    
    

    
onlyOne
    
1.4
    
0.0
    


    

    
 -                     
    
 -             
    
 -      
    
individual
    
 
    
inherited
    
 
    
    

    
COST CENTRE 
    
no.　
    
entries
    
 time　
    
alloc　
    
 time　
    
alloc
    
    

    
MAIN
    
1
    
0
    
0.0
    
0.0
    
100.0
    
100.0
    
    

    
　main
    
196
    
1
    
0.0
    
0.0
    
100.0
    
99.9
    
    

    
　　tryChoices
    
220
    
32444
    
1.8
    
5.1
    
100.0
    
99.9
    
    

    
　　　set
    
222
    
155293
    
18.9
    
27.0
    
97.2
    
94.8
    
    

    
　　　　exclude
    
225
    
437059
    
6.5
    
6.0
    
6.5
    
6.0
    
    

    
　　　　propagate
    
223
    
155293
    
33.2
    
26.1
    
71.9
    
61.9
    
    

    
　　　　　onlyOne
    
229
    
721311
    
0.5
    
0.0
    
0.5
    
0.0
    
    

    
　　　　　excludeM
    
226
    
1302379
    
3.7
    
1.3
    
12.4
    
9.2
    
    

    
　　　　　　exclude
    
227
    
3963625　
    
8.8
    
7.9
    
8.8
    
7.9
    
    

    
　　　　　uniq
    
224
    
155293
    
2.8
    
4.6
    
25.8
    
26.6
    
    

    
　　　　　　exclude
    
228
    
1282200
    
23.0
    
21.9
    
23.0
    
21.9
    
    

    
　　　onlyOne
    
221
    
322671
    
0.9
    
0.0
    
0.9
    
0.0
    
    

    
　　showSudoku
    
215
    
6
    
0.0
    
0.0
    
0.0
    
0.0
    
    

    
　　　showChoice
    
218
    
162
    
0.0
    
0.0
    
0.0
    
0.0
    
    

    
　　　printGrid
    
217
    
162
    
0.0
    
0.0
    
0.0
    
0.0
    
    

    
　CAF
    
190
    
33
    
0.0
    
0.0
    
0.0
    
0.1
    
    

    
　　printGrid
    
219
    
0
    
0.0
    
0.0
    
0.0
    
0.0
    
    

    
　　showSudoku
    
216
    
0
    
0.0
    
0.0
    
0.0
    
0.0
    
    

    
　　initialConstraintsC　
    
213
    
1
    
0.0
    
0.0
    
0.0
    
0.0
    
    

    
　　initialConstraintsY
    
212
    
1
    
0.0
    
0.0
    
0.0
    
0.0
    
    

    
　　initialConstraintsX
    
205
    
1
    
0.0
    
0.0
    
0.0
    
0.0
    
    

    
　　initialBoard
    
203
    
2
    
0.0
    
0.0
    
0.0
    
0.0
    
    

    
　　initialSudoku
    
202
    
1
    
0.0
    
0.0
    
0.0
    
0.0
    
    

    
　　p4
    
201
    
1
    
0.0
    
0.0
    
0.0
    
0.0
    
    

    
　　sample
    
200
    
1
    
0.0
    
0.0
    
0.0
    
0.0
    
    

    
　　allPos
    
199
    
1
    
0.0
    
0.0
    
0.0
    
0.0
    
    

    
　　sampleInput
    
198
    
1
    
0.0
    
0.0
    
0.0
    
0.0
    
    

    
　　main
    
197
    
0
    
0.0
    
0.0
    
0.0
    
0.0
    
    

    
　　　set
    
204
    
18
    
0.0
    
0.0
    
0.0
    
0.0
    
    

    
　　　　exclude
    
208
    
54
    
0.0
    
0.0
    
0.0
    
0.0
    
    

    
　　　　propagate
    
206
    
18
    
0.0
    
0.0
    
0.0
    
0.0
    
    

    
　　　　　onlyOne
    
214
    
327
    
0.0
    
0.0
    
0.0
    
0.0
    
    

    
　　　　　excludeM
    
209
    
327
    
0.0
    
0.0
    
0.0
    
0.0
    
    

    
　　　　　　exclude
    
210
    
2529
    
0.0
    
0.0
    
0.0
    
0.0
    
    

    
　　　　　uniq
    
207
    
18
    
0.0
    
0.0
    
0.0
    
0.0
    
    

    
　　　　　　exclude
    
211
    
327
    
0.0
    
0.0
    
0.0
    
0.0
    
    

    
　CAF
    
169
    
8
    
0.0
    
0.0
    
0.0
    
0.0
    
    

    
　CAF
    
164
    
1
    
0.0
    
0.0
    
0.0
    
0.0
    
    

    
　CAF
    
121
    
4
    
0.0
    
0.0
    
0.0
    
0.0
    
表をブログでちゃんとフォーマットするためにModule欄を取り除きました…

まず、最初の部分で全体でどれくらい時間がかかってどれくらいメモリを消費したかが記録されています。

total time  =        4.34 secs   (217 ticks @ 20 ms)
total alloc = 812,398,524 bytes  (excludes profiling overheads)

これはわりと難度の高いパズルを一つ解くのにかかった時間とメモリです。初期のころのコードでした。4秒ちょっとというのはまぁまぁだとしても、９ｘ９の数独を解くのに 700Mバイト超のメモリーを使うのはなんともいただけませんね…

そして、その次の部分でメモリ、時間ともに特に消費している関数がリストされています。

    

    
COST CENTRE　
    
%time
    
%alloc
    
    

    
exclude
    
38.2
    
35.8
    
    

    
propagate
    
33.2
    
26.1
    
    

    
set
    
18.9
    
27.0
    
    

    
excludeM
    
3.7
    
1.3
    
    

    
uniq
    
2.8
    
4.6
    
    

    
tryChoices
    
1.8
    
5.1
    
    

    
onlyOne
    
1.4
    
0.0
    
    

    

    
これによると、exclude関数は 4 * 0.382 = 1.528 ほぼ１．５秒、そしてメモリはこの関数単体で２５０Mバイト消費していることがわかります。一体何にそんなにメモリを使っているんでしょう…

そして、最後の部分が詳細のリストになります。詳細といっても、関数一つ丸ごとのパフォーマンスしかわからないので、複雑な関数の場合は、分割してみたり、仮説を立てて検証してみたりしないと何がリソース浪費の原因になっているかははっきりしないときもあります…


    

    
 -                     
    
 -             
    
individual
    
 
    
inherited
    
 
    
    

    
COST　CENTRE　
    
entries
    
%time
    
%alloc
    
%time
    
%alloc
    
    

    
MAIN
    
0
    
0.0
    
0.0
    
100.0
    
100.0
    
    

    
　main
    
1
    
0.0
    
0.0
    
100.0
    
99.9
    
    

    
　　tryChoices
    
32444
    
1.8
    
5.1
    
100.0
    
99.9
    
    

    
　　　set
    
155293
    
18.9
    
27.0
    
97.2
    
94.8
    
    

    
　　　　exclude
    
437059
    
6.5
    
6.0
    
6.5
    
6.0
    
    

    
　　　　propagate
    
155293
    
33.2
    
26.1
    
71.9
    
61.9
    
    

    
　　　　　onlyOne
    
721311
    
0.5
    
0.0
    
0.5
    
0.0
    
    

    
　　　　　excludeM　
    
1302379
    
3.7
    
1.3
    
12.4
    
9.2
    
    

    
　　　　　　exclude
    
3963625　
    
8.8
    
7.9
    
8.8
    
7.9
    
    

    
　　　　　uniq
    
155293
    
2.8
    
4.6
    
25.8
    
26.6
    
    

    
　　　　　　exclude
    
1282200
    
23.0
    
21.9
    
23.0
    
21.9
    
    

    
　　　onlyOne
    
322671
    
0.9
    
0.0
    
0.9
    
0.0
    
    

    
　　showSudoku
    
6
    
0.0
    
0.0
    
0.0
    
0.0
    
        :
ここで、entriesの欄はその関数が何回実行されたかを示しています。timeとallocがindividualとinheritedに分けて2回繰り返されているのは、individualがその関数自身の時間とメモリの消費、そしてinheritedがその関数とそこから呼び出される関数全てを含めた時間とメモリの消費を示しています。mainのinheritedが時間、メモリ共に100%になっていることからもわかりますね…

こうやって見ると、excludeはもうとにかくすごい回数呼ばれていますね… excludeMとuniqの両方からかなり呼び出されて合計500万回以上に及びます。ここまで呼ばれてしまうと1回あたりの時間、メモリの消費が少なくてもすぐにすごいことになっちゃいます…いわゆるホットスポットとかインナーループとか言われるやつですね…propagateのほうは回数は excludeの1/33ですが、時間もメモリーもかなり使っています。ここは何か遅い処理が入っているか、関数の中にホットスポットがあるか…

元のリストのほうを見るとCAFとかいうものがリストにあるのが見えますが、これは今のところ僕にはなんだかよくわかっていません。まぁ、マニュアルを見ればいいだけなんでしょうが…

そして、プログラムの効率化(パフォーマンス・チューニング)はこういったプロファイルの結果を見ながらリソース浪費の原因を理解して、改善していくわけです…

次回以降は実際の効率化の話しを書いていきたいと思います。

ではでは。