まずは引用：
続いてやってみた。お題はこちら。
お題：ある金額になるコインの組み合わせ - No Programming, No Life
あまり芸のない総当たりだけど、こんなんでいいのかな。
object CoinAssort { def search(coinList: List[Int], sum: Int, curAssort: List[Int] = Nil): List[List[Int]] = { val preCoin = curAssort.lastOption.getOrElse(0) coinList.filter(coin => coin >= preCoin && coin <= sum).flatMap(coin => { sum - coin match { case 0 => List(curAssort :+ coin) case n => search(coinList, n, curAssort :+ coin) } }) } } /** * 以下テスト */ class CoinAssortTest { import org.junit.Assert._ import org.junit.Test @Test def coinAssortTest = { val res = CoinAssort.search(List(1, 5, 10, 50, 100, 500), 10) assertTrue(res.exists(_ == List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1))) assertTrue(res.exists(_ == List(1, 1, 1, 1, 1, 5))) assertTrue(res.exists(_ == List(5, 5))) assertTrue(res.exists(_ == List(10))) // 合計値の異なる組み合わせが混ざってないこと for (a <- res) assertEquals(10, a.sum) // 重複がないこと assertEquals(res.size, res.map(_.sorted).distinct.size) } }…(中略)…
(8/17追記) スタック溢れ対策（失敗）版上記コードでは、樹形探索の各ノードで単純に再帰呼出しをしているので、金額が1000円くらいになると再帰が深くなって容易にスタックオーバーフローを起こしてしまいます（32bit環境の場合）。
ということで対策版。修正ポイントは以下になります。
コインの組合せ情報のコンテナAssortを作成し、このコンテナの型によって探索状態を持たせる
末尾再帰となるように、個々のノードで再帰するのではなく、状態判断と組合せパターンの分岐のみ行って、組合せのリストをまるごと継続渡しで再帰関数に渡す。…が、ヒープの消費量が異常に大きくなってしまい、スタック溢れの代わりにOutOfMemoryErrorになります。たぶん組合せリストそのものが肥大化するのと、再帰の段数が増えるごとに新リストを生成して、参照が切れないまま維持されるのが原因でしょう。さてどうしたもんか。
object CoinAssort2 { sealed trait Assort // Assort: コイン組み合わせパターンのコンテナ case class Over extends Assort // 金額オーバー（破棄） case class Fixed(l: List[Int]) extends Assort // 確定済み case class Cont(l: List[Int], shorted: Int) extends Assort // 探索途中 object Assort { def apply(sum: Int, coin: Int, l: List[Int] = Nil) = sum - coin match { case 0 => Fixed(l :+ coin) case n if (n > 0) => Cont(l :+ coin, n) case _ => Over() } } def search(coinList: List[Int], sum: Int): List[List[Int]] = { val coins = coinList.filter(_ <= sum) def _search(curAssorts: List[Assort]): List[Assort] = { val res = curAssorts.flatMap(_ match { case Cont(l, shorted) => { val preCoin = l.lastOption.getOrElse(0) coins.filter(c => c >= preCoin && c <= shorted) .flatMap(Assort(shorted, _, l) match { case Over() => Nil case x => List(x) }) } case assort => List(assort) }) if (res.forall(_.isInstanceOf[Fixed])) res else _search(res) // 再帰 } val initAssorts = coins.map(Assort(sum, _)) _search(initAssorts).flatMap(_ match { case Fixed(l) => List(l) case _ => Nil }) } }(以下略)
「ある金額になるコインの組み合わせ」をScalaで
というわけで、問題は解けたものの、探索が深くなった場合のスタック溢れ or OufOfMemoryErrorに悩んでおられたようです。最終的には、継続をキューに突っ込むことで解決されたようですが、実際のところ、スタック溢れ or OutOfMemoryErrorを解消すればいいだけなら、それほど凝ったことをする必要はありません*1。鍵はStreamです。
の前に、コードを読んでいて気になった点について少し。Listを使ったコードで、
curAssort :+ coin
のように、:+演算子を使っている箇所が見受けられます。:+演算子はListクラス(正確にはGenSeqLike)に定義されているメソッドで、Listの末尾に要素を追加した新しいListを生成して返します。
ここで、Listクラスに対する:+演算子の使用は二つの問題があります。まず、一つ目は、関数型言語一般のList型というのは、先頭に対する要素の追加は定数時間で可能な一方、末尾に対する要素の追加は要素数nに対して線形時間かかってしまう、ということです。二つ目は、:+演算子を使用する度に、Listの要素数に比例したサイズのヒープが新たに必要になるという点です。
これらは別に難しい話ではなく、Listというのが、単にimmutableな単方向連結リストだからです。イメージとしては、List型のデータは以下のような構造になっています。
1 ^ | |------|------| |------|------| |-----| | head | tail | ---> | head | tail | ---> ... | Nil | |------|------| |------|------| |-----|
ここで、:+演算子を利用して、新しい要素を末尾に追加したListを生成しようとすると、tailを要素数分たぐる時間が必要になります。また、Listはimmutableなデータであるため、Nilの直前のセルのtailを書き換えて、新しいセルを指すようにして終わり、というわけにはいかず、Listの要素数分のセルを新たに生成する必要があります。
Listがごく短いものだったり、:+演算子が適用される回数が少ない場合はこれらの点は問題になりませんが、今回の問題のように、Listの要素数が増える場合には、:+演算子を利用せず、Listの先頭に要素を追加した新しいListを返す::演算子を使うのが良いでしょう。Listの要素順が問題になる場合でも、必要になった時点でList#reverseを使って要素を逆順にする方が効率的です。
これは、Scalaに限った話ではなく、関数型言語でリストと呼ばれるデータ構造の基本的な話で、MLなどのリストでも同様の問題は発生します。
さて、もう一つの問題は、金額の合計値が大きくなるにつれて、List[Int]のパターン数が急速に増大するのに対して(CoinAssort.search(List(1, 5, 10, 50, 100, 500), 1000)で248908通り)、List[ List[Int] ]型を使っている事です。Listは、使われる/使われないに関わらず、あらかじめ全要素が評価されますから、Listの要素数が急速に増大するような場合にListを使うのはメモリ効率・実行効率の両方の観点からあまり好ましくありません。
というわけで、要素の評価が遅延されるデータ構造であるStreamを使って、以下のように書き換えてみました。
object CoinAssort { def search(coinList: List[Int], sum: Int): Stream[List[Int]] = { val coinStream = coinList.toStream def searchInner(sum: Int, curAssort: List[Int] = Nil): Stream[List[Int]] = { val preCoin = curAssort.headOption.getOrElse(0) coinStream.filter(coin => coin >= preCoin && coin <= sum).flatMap{coin => sum - coin match { case 0 => Stream((coin :: curAssort) reverse) case n => searchInner(n, coin :: curAssort) } } } searchInner(sum) } def main(args: Array[String]) { var res = CoinAssort.search(List(1, 5, 10, 50, 100, 500), 1000) var count = 0 while(res != Stream.empty) { println(res.head.length) count += 1 if(count % 1000 == 0) { System.out.println("count:" + count) } res = res.tail } println(count) } }
このコードでは、-Xms16m -Xmx16mでJVMを実行してもOutOfMemoryErrorは発生しませんでした。
ちなみに、Streamから要素を取り出すときに、whileループを使ってStreamを指す変数res自体をStream#tailで更新している点に注意してください。これは、resがStreamの先頭要素を指しっぱなしにした場合、不要になった要素(ゴミ)がいつまでもGCで解放できなくなるのを回避するための措置です。
本来ならば、whileループを使わずとも、
val res = Coins.search(List(1, 5, 10, 50, 100, 500, 1000).iterator res.foreach{coins => ... }
のようにして、iteratorに変換すれば良いのですが、Stream#iteratorが返すStreamIteratorの実装にバグがあって、StreamIteratorがStreamの先頭要素を指し続けるようになっているため、この方法は現在は使えません*2。
