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

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

関数プログラミング 珠玉のアルゴリズムデザイン

こちらの本のコードをScalaに置き換えていっているシリーズの第３弾ですが、内容の解説が難解すぎてScalaのコードがオマケみたいな感じになってきているのは、きっと気のせいです。(^^;

では、はりきって第３章行ってみましょう〜。

鞍型探索の改良

この章は、突然グループディスカッション形式で進みます。

Anne, Jack, Mary, Theoの四人と教師のディスカッションを追っていく形式なのですが、リアルタイムでこんなディスカッションされたらついていけない。(^^;

今回のお題ですが、とある関数 f(x,y) とその答えとなるzがあったとして、fとzを渡されると、その答えを返すペア(x,y)のリストを返す関数 invert を作るというものです。

invert :: f -> z -> [(x,y)]

こんな感じの定義かな？

但しfは「狭義単調増加関数」になっている必要があります。この条件がないと、無限に答えがあって終わらないですね。(^^;

素朴な回答

早速Jackが答えを出します。

invert f z = [(x,y) | x <- [0..z], y <- [0..z], f (x,y) == z]

ちょっと動かしてみます。

ghci> invert f 10
[(0,10),(1,9),(2,8),(3,7),(4,6),(5,5),(6,4),(7,3),(8,2),(9,1),(10,0)]

良さそうですね。

それでは、Scalaにします。

def invert(f: (Int,Int) => Int, z: Int): List[(Int, Int)] = { 
  for {
    x <- (0 to z)
    y <- (0 to z)
    if f(x,y) == z
  }yield {(x,y)}
}.toList

リスト内包表記がないので、野暮ったい感じが否めません。また、Rangeをforで使うと、戻り型がVectorになるので、toListしてます。

scala> examples.ss3.Invert.invert(f, 10)
res0: List[(Int, Int)] = List((0,10), (1,9), (2,8), (3,7), (4,6), (5,5), (6,4), (7,3), (8,2), (9,1), (10,0))

同様の結果を得ることが出来ました。

このコードを実行した際の比較回数と正答のイメージを散布図で示してみました。「f (x,y) = x * 3 + y * 2」とした時の分布です。

この解法だとfを(z+1)²回評価する必要があります。単純な２重ループなので当然ですが。

何とか評価回数を少なくしようというのが今回のテーマで、4人+教師は、あれやこれやの発想でこれを実践していきます。

こう言うとスチャラカ冒険隊みたいですが、その様子はまさに神がかっており、僕のような雑兵からは別世界に見えます。まるで、人造人間を目の当たりにしたクリリンのような心境です。(^^;

半分にする

さっそく、Theoが評価回数を半分にします。

invert2 f z = [(x,y) | x <- [0..z], y <- [0..z-x], f (x,y) == z]

yのジェネレータが、z-xとなっているため、徐々に最大値が減っていきます。

グラフにするとわかりやすく半分になってますね。

なお、この先特に断りがなければ、下記のパラメータで実行しています。

f (x,y) = X * 3 + Y *2
z = 20

上記のコードをScalaに直したものです。

def invert2(f: (Int,Int) => Int, z: Int): List[(Int, Int)] = { 
  for {
    x <- (0 to z)
    y <- (0 to z-x)
    if f(x,y) == z
  }yield {(x,y)}
}.toList

Scalaでも、同様にz-xとするだけで半分になります。お得ですね。

さらなる改善

Anneの提案は、さらなる改善を目指します。

ピンポイントにf (x,y) = zとなる近辺を探索するfindを定義し、効率よくzを割り出します。

invert3 :: ((Int,Int) -> Int) -> Int -> [(Int,Int)]
invert3 f z = find (0,z) f z
  where
    find (u,v) f z
      | u > z || v < 0 = []
      | z' < z         = find (u+1,v) f z
      | z' == z        = (u,v) : find (u+1,v-1) f z
      | z' > z         = find (u, v-1) f z
        where z' = f (u,v)

いきなり難易度がアップした気がしますが、きっと気のせいです。(^^;

グラフにしてみると、一直線にy=10となるポイントを目指しています。

そこから、xを増加→yを減少を繰り返すことで、ほぼ無駄なく対象となる組を削りだしています。

比較回数がだいぶ少なくなっているのがわかると思います。

Scalaだとこんな感じです。

type Fun = ((Int,Int)) => Int

def invert3(f: Fun, z: Int): List[(Int, Int)] = { 
  def find(pair:(Int,Int), f: Fun, z: Int): List[(Int,Int)] = {
    val z2 = f(pair)
    val (u,v) = pair
    if (u > z || v < 0) List.empty
    else if (z2 < z) find((u+1,v), f, z)
    else if (z2 == z) pair :: find((u+1,v-1), f, z)
    else find((u,v-1), f, z)
  }
  find((0,z), f, z)
}

タプルを引数で受けるときにパタンマッチで分解できれば良いのですが、別途「(u,v) = pair」とする必要があります。

あとは引数のガードが無いので、if 〜 else if 〜 else になっているところがイマイチですね。もっとスッキリした書き方があるかもしれません。

ちなみにcaseには、ガードがあるようなのですが、特にスッキリした感じはしませんでした。

ifを連鎖させる場合、最後にelseが無いとif式の戻りがUnitになってしまうので注意が必要です。そのため、Haskell版と最後の条件が多少変わっていますが、意味的には同じなはずなので、これでいいかなと。(^^;

もう一工夫

invert3をもう一工夫することで、更に比較回数を減らすことに挑戦します。

invert4 :: ((Int,Int) -> Int) -> Int -> [(Int,Int)]
invert4 f z = find (0,m) f z
  where
    find (u,v) f z
      | u > n || v < 0 = []
      | z' < z         = find (u+1,v) f z
      | z' == z        = (u,v) : find (u+1,v-1) f z
      | z' > z         = find (u, v-1) f z
        where z' = f (u,v)
    m  = bsearch (\y -> f (0,y)) (-1,z+1) z
    n  = bsearch (\x -> f (x,0)) (-1,z+1) z

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

さらに複雑になりましたが、最初のxとyを割り出す際にバイナリサーチを使い、線形時間を対数時間にしています。

グラフで見ると、X=0のラインとY=0のラインにまばらな点が見えますが、よく見ると範囲を半分にしながら最初の点を割り出しているのがわかると思います。

Scalaのコードです。

def invert4(f: Fun, z: Int): List[(Int, Int)] = { 
  @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 find(pair:(Int,Int), f: Fun, z: Int): List[(Int,Int)] = {
    val z2 = f(pair)
    val (u,v) = pair
    val n = bsearch(x => f((x,0)), (-1, z+1), z) 
    if (u > n || v < 0) List.empty
    else if (z2 < z) find((u+1,v), f, z)
    else if (z2 == z) pair :: find((u+1,v-1), f, z)
    else find((u,v-1), f, z)
  }
  val m = bsearch(y => f((0,y)), (-1, z+1), z) 
  find((0,m), f, z)
}

invert3と同じで、pairの分解とif 〜 elseで構成されています。

前半おしまい

ふー。ここまでで、この章の前半は終わりです。疲れました。

本章では、ここから更に分割統治法を試し始めるのですが、フリーザ様にやっとダメージを与えたと思ったら第２形態に変形された気分です。

気持ちが折れたので、一旦今回はここで終わります。

ここまでのコードの完全版は、下記のGithubリポジトリにて管理されています(なんとテスト付き)。

qtamaki/pearls · GitHub

余談ですが、今回のグラフを作るために関数の呼び出し履歴を取りながら実行するバージョンも作りました(Haskell)。

こちらは、Eitherを使ったりStateを使ったりして、かなり苦労しました。

こちらのコードの解説も別の機会にしたいと思います。