「関数プログラミング珠玉のアルゴリズムデザイン」をScalaで実装してみる第３章その２

さて、前回の続きです。

「関数プログラミング珠玉のアルゴリズムデザイン」をScalaで実装してみる第３章その１ - セカイノカタチ

この章では、f (x,y) == z を満たす(x,y)を全て挙げる関数の設計について話題にしています。

一つの解き方として、鞍型探索というものの説明を追いかけました。

鞍型探索とは、表の左上を基点にじわじわxとyを増加しながら答えを探るやり方で、最適解が出たところで一件落着！と、思いきやMaryが「分割統治でやるとどうなるでしょう？」と話を蒸し返したところで、心折れて一旦終了しました。

分割統治による解法

Maryの提案はこうです。

下記の図のように、表の中心点で、f (p,q)を調べ、(z>),(z==),(z<)の場合で、矩形をごっそり削ることができるため、これを再帰的に繰り返すことによって、効率よく解を求められるのではないかという発想のようです。

ここから4人は、この方法の評価回数を見積もり始めます。

２ページ半に渡り計算をした結果、Maryが「Jackの分割統治法は本当は必要ではないと思います。」と言い放ちます(Mary鬼だな。ってかお前が言い出しっぺだろ！？)。

そして突然、「各行で二分探索すればいいじゃん」という身も蓋もないシンプルな解法を思いつきます。(^^;

コードを示します。

bsearch g (a,b) z
  | a + 1 == b = a
  | g m <= z   = bsearch g (m,b) z
  | otherwise  = bsearch g (a,m) z
    where m = (a + b) `div` 2

invert5 :: ((Int,Int) -> Int) -> Int -> [(Int,Int)]
invert5 f z = find (0,m) (n,0) f z
  where
    m  = bsearch (\y -> f (0,y)) (-1,z+1) z
    n  = bsearch (\x -> f (x,0)) (-1,z+1) z
    find (u,v) (r,s) f z
      | u > r || v < s = []
      | v - s <= r - u = rfind (bsearch (\x -> f (x,q)) (u - 1, r + 1) z)
      | otherwise      = cfind (bsearch (\y -> f (p,y)) (s - 1, v + 1) z)
      where
        p = (u + r) `div` 2
        q = (v + s) `div` 2
        rfind p = (if f (p,q) == z then (p,q) : find (u,v) (p - 1, q + 1) f z
                   else find (u,v) (p, q + 1) f z) ++ find (p + 1, q - 1) (r,s) f z
        cfind q = find (u,v) (p - 1, q + 1) f z ++
                  (if f (p,q) == z then (p,q) : find (p + 1, q - 1) (r,s) f z
                   else find (p + 1, q) (r,s) f z)

考え方がシンプルな割に、コードはえらく複雑ですね。(^^;;

実行結果を表にすると、確かになんとなく二分探索している感じがしますね。

なお、二分探索には、前回作成したbsearchをそのまま流用しています。

Scalaにしてみる

Scalaのコードに直します。

と言っても、単純に置き換えただけです。

@tailrec
def bsearch(g: Int => Int, pair: (Int, Int), z: Int): Int = {
  val (a, b) = pair
  val m = (a + b) / 2
  if (a + 1 == b) a
  else if (g(m) <= z) bsearch(g, (m, b), z)
  else bsearch(g, (a, m), z)
}

def invert5(f: Fun, z: Int): List[(Int, Int)] = {
  def find(pair1: (Int, Int), pair2: (Int, Int), f: Fun, z: Int): List[(Int, Int)] = {
    val (u, v) = pair1
    val (r, s) = pair2
    val p = (u + r) / 2
    val q = (v + s) / 2
    def rfind(p: Int): List[(Int, Int)] =
      (if (f((p, q)) == z) (p, q) :: find((u, v), (p - 1, q + 1), f, z)
      else find((u, v), (p, q + 1), f, z)) ++ find((p + 1, q - 1), (r, s), f, z)
    def cfind(q: Int): List[(Int, Int)] =
      find((u, v), (p - 1, q + 1), f, z) ++
        (if (f((p, q)) == z) (p, q) :: find((p + 1, q - 1), (r, s), f, z)
        else find((p + 1, q), (r, s), f, z))
    if (u > r || v < s) List.empty
    else if (v - s <= r - u) rfind(bsearch(x => f((x, q)), (u - 1, r + 1), z))
    else cfind(bsearch(y => f((p, y)), (s - 1, v + 1), z))
  }
  val m = bsearch(y => f((0, y)), (-1, z + 1), z)
  val n = bsearch(x => f((x, 0)), (-1, z + 1), z)
  find((0, m), (n, 0), f, z)
}

再帰がtailrecになっていないので、規模が大きいとスタックがアレして落ちるかもしれません(おぃ)。(^^;

最後にベンチマークが載っていて、分割統治の方が速いことが多いようです(必ず速いわけではない)。