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

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

さて、時間が開いてしまいましたが、第４章行きたいと思います。

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

作者: Richard bird,山下伸夫
出版社/メーカー: オーム社
発売日: 2014/11/12
メディア: 単行本（ソフトカバー）
この商品を含むブログ (1件) を見る

この本のコードをScalaに置き換えていっているシリーズの第4弾です。

選択問題

タイトルからしてやヴぁいですが、内容は二つの集合を合わせた時にk番目に小さい要素を取り出すというものです。選択公理は関係なかったですね(ほっ)。

前提をまとめます。

集合Xと集合Yは互いに素な有限集合
XとYの和集合の大きさはkより大きい
XYともに整列されたリストと配列について考える

詳しくは、本を読んでもらうとして、リストであればO(|X|+|Y|)ステップの計算時間になって、配列であればO(log|X|+log|Y|)ステップまで低減できるとのことです。

考え方

一番単純な方法はXY両方のリストの先頭から順に探索することで、答えを探します。

smallest :: Ord a => Int -> ([a],[a]) -> a
smallest k (xs, ys) = union (xs,ys) !! k

union (xs,[]) = xs
union ([],ys) = ys
union (x:xs, y:ys) | x < y = x : union (xs, y:ys)
                   | x < y = y : union (x:xs, ys)

Scalaで実装します。

def smallest[A:Ordering](k: Int, pair: (List[A],List[A])):A = {
  def union(pair:(List[A], List[A])): List[A] = {
    pair match {
      case (xs, Nil) => xs
      case (Nil, ys) => ys
      case (x::xs, y::ys) => if (implicitly[Ordering[A]].lt(x,y)) x :: union (xs, y::ys)
                             else y :: union (x::xs, ys)
    }
  }
  union(pair)(k)
}

簡単ですね。

分割統治

しかし、こんな方法でこの本が満足するはずがありません(log|X|になってないし)。

ここから伝家の宝刀分割統治が始まります。

まず、手始めにXとYをこのように分割して考えます。

xs ++ [a] ++ ys, us ++ [b] ++ vs

これは何かというと、両方の集合ととある点aとbでそれぞれ分割するということです。

ただし、aとbはa<bとなるように選択します(実際にはa>bが双対なので適当に選択してロジックを入れ替えます)。

こうして分割されたリストは、以下の様な感じになります。

ごちゃごちゃしていますが、色々冷静に考えるとkが、|xs ++ [a] ++ us|より小さければ、zone2(ys2)の可能性は無いと断定できるということです。

もし、kが|xs ++ [a] ++ us|より大きかった場合、逆にこんな感じになって、zone2(us1)の可能性はなくなります。

このように、2分割では無いですが、4分割して、そのうちの1つづつ削っていくイメージで答えに迫っていくというロジックになります。

コードは、こんな感じです。

smallest :: Ord a => Int -> ([a],[a]) -> a
smallest k ([],ws) = ws !! k
smallest k (zs,[]) = zs !! k
smallest k (zs,ws) =
  case (a < b,k <= p + q) of
    (True,True)   -> smallest k (zs,us)
    (True,False)  -> smallest (k-p-1) (ys,ws)
    (False,True)  -> smallest k (xs,ws)
    (False,False) -> smallest (k-q-1) (zs,vs)
  where p = (length zs) `div` 2
        q = (length ws) `div` 2
        (xs,a:ys) = splitAt p zs
        (us,b:vs) = splitAt q ws

かなり複雑になりましたね。(^^;

Scalaにします。

def smallest[A: Ordering](k: Int, pair: (List[A],List[A])):A = {
  pair match {
    case (Nil, ws) => ws(k)
    case (zs, Nil) => zs(k)
    case (zs, ws) =>
      val p = zs.length / 2
      val q = ws.length / 2
      val (xs,a::ys) = zs.splitAt(p)
      val (us,b::vs) = ws.splitAt(q)
      (implicitly[Ordering[A]].lt(a,b), k <= p + q) match {
        case (true,true)   => smallest(k, (zs,us))
        case (true,false)  => smallest(k-p-1, (ys,ws))
        case (false,true)  => smallest(k, (xs,ws))
        case (false,false) => smallest(k-q-1, (zs, vs))
      }
  }
}

可読性は・・・変わらないですね。

このバージョンでも、リストを走査する(!!)が線形時間となるため効率は良くなりません。

配列を使うと定数時間の(!)を使えるため、効率が対数時間に改善されます。

smallest' :: Ord a => Int -> (Array Int a, Array Int a) -> a
smallest' k (xa,ya) = search k (0, m + 1) (0, n + 1)
  where
    (0,m) = bounds xa
    (0,n) = bounds ya
    search k (lx, rx) (ly, ry)
      | lx == rx = ya ! (k + ly)
      | ly == ry = xa ! (k + lx)
  | otherwise =
      case (xa ! mx < ya ! my, k <= mx - lx + my - ly) of
        (True,True)   -> search k (lx,rx) (ly,my)
        (True,False)  -> search (k - (mx - lx) - 1) (mx + 1, rx) (ly, ry)
        (False,True)  -> search k (lx, mx) (ly, ry)
        (False,False) -> search (k - (my - ly) - 1) (lx,rx) (my + 1, ry)
      where mx = (lx + rx) `div` 2
            my = (ly + ry) `div` 2

更に複雑化したような。変わらないような。(^^;

Scala化します。

def search[A: Ordering](pair: (Vector[A],Vector[A]), k:Int, pairX:(Int,Int), pairY:(Int,Int)): A = {
  val (xa,ya) = pair
  val (lx,rx) = pairX
  val (ly,ry) = pairY
  val mx = (lx + rx) / 2
  val my = (ly + ry) / 2
  if (lx == rx) ya(k + ly)
  else if (ly == ry) xa(k + lx)
  else (implicitly[Ordering[A]].lt(xa(mx), ya(my)), k <= mx - lx + my - ly) match {
    case (true, true)    => search(pair, k, (lx,rx), (ly,my))
    case (true, false)   => search(pair, k - (mx - lx) - 1, (mx + 1, rx), (ly, ry))
    case (false, true)   => search(pair, k, (lx, mx), (ly, ry))
    case (false , false) => search(pair, k - (my - ly) - 1, (lx,rx), (my + 1, ry))
  }
}

def smallest2[A: Ordering](k: Int, pair: (Vector[A],Vector[A])):A = {
  val (xa,ya) = pair
  search(pair, k, (0, xa.length), (0, ya.length))
}

やっぱり、複雑です。

序文を引用すると「最後に出来たプログラムが珠玉なのではなく、最後のプログラムを導いた運算こそが珠玉なのである」との事なので、プログラム事態には価値は無いです(言い過ぎ)。

というか、それを言われてしまうとこの記事自体が・・・・。(^^;