リスト操作のコスト

Haskell Optimization Profile

さて、前回のプロファイルの結果で明らかになった数独ソルバーの最悪のホットスポットは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バイト以上の削減です…昔のハードディスク丸ごとぐらい減っちゃいました…ははは。

きょうはこのへんで。

ではでは。