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のコストがメモリ時間ともにゼロになってしまいます。これはおそらくプロファイラ側の問題なのだろうと思います。

ではでは。