「ある金額になるコインの組み合わせ」をScalaで
続いてやってみた。お題はこちら。
お題：ある金額になるコインの組み合わせ - 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) } }
そういえば、Eclipse indigo + Scalaプラグインの最新版だと、JUnitライブラリのimportを最上位スコープに出さなくとも、Run Asからテスト実行できるようになってますね。こりゃいいや。
(8/17追記) スタック溢れ対策（失敗）版
上記コードでは、樹形探索の各ノードで単純に再帰呼出しをしているので、金額が1000円くらいになると再帰が深くなって容易にスタックオーバーフローを起こしてしまいます（32bit環境の場合）。
ということで対策版。修正ポイントは以下になります。
- コインの組合せ情報のコンテナAssortを作成し、このコンテナの型によって探索状態を持たせる
- 末尾再帰となるように、個々のノードで再帰するのではなく、状態判断と組合せパターンの分岐のみ行って、組合せのリストをまるごと継続渡しで再帰関数に渡す。
…が、ヒープの消費量が異常に大きくなってしまい、スタック溢れの代わりにOutOfMemoryErrorになります。たぶん組合せリストそのものが肥大化するのと、再帰の段数が増えるごとに新リストを生成して、参照が切れないまま維持されるのが原因でしょう。さてどうしたもんか。
(8/20)
このコードを添削して頂き、Listに :+ を繰り返すのは非常に効率が悪いこと、Streamで巨大なリストの評価を遅延させることができることをご指摘頂きました。ありがとうございます。
勝手に添削：「「ある金額になるコインの組み合わせ」をScalaで」 - kmizuの日記
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 }) } }
(8/18追記) スタック溢れ対策（Actor使用）版
無理に末尾再帰にすると、継続の肥大化が避けられないので諦めました。
再帰の際に関数呼び出しを使うからスタックを消費するのであって、それさえなければ樹形再帰でも問題ないはず。ということで、最低限の継続情報をキューに放り込み、放り込まれた順番に処理して、分岐したらその分をまたキューに放り込み…という形を考えてみました。ついでに、Actorを使って並行処理させてみます。
他にも、無節操にListを使っていたのを、一部Arrayに切り替えたりしています。
object CoinAssort3 { type Assort = Array[Int] object Assort { def apply() = Array[Int]() } case class Cont(assort: Assort, shorted: Int) // 組合せ探索の継続情報コンテナ def search(coinList: List[Int], sum: Int): List[Assort] = { // 確定済情報を格納する可変バッファ import scala.collection.mutable.{ArrayBuffer, SynchronizedBuffer} val fixedBuf = new ArrayBuffer[Assort] with SynchronizedBuffer[Assort] // 再帰処理を行うActor import scala.actors.Actor val _search = new Actor() { def act() = loop { react { case c: Cont => checkNode(c) case None => exit case _ => } } private def checkNode(cont: Cont) = { val (assort, shorted) = (cont.assort, cont.shorted) val preCoin = assort.lastOption.getOrElse(0) coinList.filter(x => x >= preCoin && x <= shorted) .foreach(coin => shorted - coin match { case 0 => fixedBuf += (assort :+ coin) case n if (n > 0) => this ! Cont(assort :+ coin, n) // 再帰 case _ => }) } } _search.start _search ! Cont(Assort(), sum) while(_search.getState == Actor.State.Runnable){ Thread.`yield` } _search ! None fixedBuf.toList } }
FizzBuzz(Nパターン)をScalaで
お題：FizzBuzz(Nパターン) - No Programming, No Life
こちらのお題にScalaで挑戦。手続き脳が頑固で苦戦しました。
object FizzBuzzN { def main(args : Array[String]) : Unit = { fizzBuzzN(List(3, "Fizz", 5, "Buzz", 7, "Hoge"),100).foreach(s => println(s)) } def fizzBuzzN(rule : List[_], count : Int) : List[String] = { def conv(c : String, x : Int, pr : List[_]) : String = { pr match { case n::s::pt => if (x % n.toString.toInt == 0) conv(c + s.toString, x, pt) else conv(c, x, pt) case _ => if (c == "") x.toString else c } } (1 to count).toList.map(x => conv("", x, rule)) } }
(8/16 追記)
toString.toInt とか汚いので少し書きなおし
object FizzBuzzN { def main(args: Array[String]): Unit = { fizzBuzzN(List(3, "Fizz", 5, "Buzz", 7, "Hoge"), 100).foreach(println(_)) } def fizzBuzzN(rule: List[_], count: Int): List[String] = { def conv(c: String, x: Int, pr: List[_]): String = pr match { case (n: Int) :: (s: String) :: pt if (x % n == 0) => conv(c + s, x, pt) case n :: s :: pt => conv(c, x, pt) case _ => if (c == "") x.toString else c } (1 to count).toList.map(conv("", _, rule)) } }
try-with-resourcesを試してみる
少し時間ができたので、↓の記事を参考にJava7のtry-with-resourcesを試してみました。
Java7 体当たり／try-with-resources Statement - 日々常々
まあ他の言語からするとアレですが、Java6以前から比較すると地味にありがたい拡張ですね。特にcloseのチェック例外を無視できるのが嬉しい。なぜかリソース系クラスのcloseメソッドはチェック例外持ちが多いので、closeの例外処理が不要でも、finallyブロック内にtryをネストしなきゃいかんというのは気分の悪いものでした。
実行順が気になる
ところで、tryブロック内で例外がthrowされた場合、リソースがクローズされた後にcatchブロックが実行されます。従来であれば、closeはたいていfinallyブロックに記述されたので、catchブロックが実行されたあとにリソースがクローズされていました。
JDBCを使ったDB更新処理では、例外が発生するとcatchブロックの中でrollbackする実装をよく見かけますが、java.sql.Connectionをtry-with-resourcesに管理させた場合は。catchブロックでConnection#rollback()を呼んでも、すでにそのConnectionはクローズされている、ということになります。
Connection conn; try (conn = dataSource.getConnection()) { // DBを読んだり書いたり〜 conn.commit(); } catch (Exception e) { conn.rollback(); // ここでは、connはクローズ済みなので例外がthrowされる！ }
まあ、JDBCの仕様上、close時に内部でrollbackされる約束になっているので、rollbackだけなら書かなければいいだけですが、システムによっては、DB上のログテーブルにエラー情報を書け、なんてケースもあるので、そういう場合は注意が必要です。そもそもDB処理で例外が発生した先でDBへ書き込めなんて、そんな実装は窓から投げ捨てるべき
まあ、大した話ではありませんが、実装パターンが若干変わってくるので、コピペテンプレ実装に慣れきっている向きは、気に留めておいたほうがいいかも知れません。
おまけ
try() の中に書けるリソースオブジェクトは、今回新設されたAutoCloseable型でなければいけません*1が、古いライブラリでも、void close() メソッドさえ持っていれば使えるようにラッパクラスを書いてみました。需要があるか微妙ですが。
import java.lang.reflect.*; public class ACWrapper<T> implements AutoCloseable { private final T resource; private final Method closeMethod; public ACWrapper(T resource) { try { closeMethod = resource.getClass().getMethod("close"); } catch (Exception e) { throw new IllegalArgumentException("close-method not found.", e); } this.resource = resource; } @Override public void close() throws Exception { closeMethod.invoke(resource); } public T getResource() { return resource; } }
こんな感じで使います。
try (ACWrapper<OldResource> acw = new ACWrapper<OldResource>(new OldResource())) { OldResource res = acw.getResource(); // OldResourceを使った処理 }
やっぱ型推論ほしいな…
(8/2 追記)
Java7では型引数を取るクラスのインスタンス生成・初期化の際、右辺の型引数を省略できることを忘れていました。上記の使用例のtry()の行は以下のように書けます。
try (ACWrapper<OldResource> acw = new ACWrapper<>(new OldResource())) {
ちなみにACWrapperのあとの「<>」をつけないとWarnが出ます。…それくらい補完してよ
ScalaでJUnitテストケースを書く
とりあえず、Scala用のテストフレームワークは使わず、素のJUnitを使った例。
Eclipseから使う場合、JUnit関連クラスのimportはクラススコープの外側に書いておかないと、右クリックからテスト実行できないようです。
あと、Scala2.8からアノテーションのパラメータの書き方が変わったようで、Javaと同じような記述ができるようになりました。（2.8で、前と同じ書き方をするとコンパイルエラーになります）
import org.junit.{ Test, After, Before } import org.junit.Assert._ class SampleTest { @Before def befor = { // 前処理 } @Test(timeout=500) //@Test{val timeout=500} //Scala2.7以前ではこう書く def testHoge = { Thread.sleep(300) assertEquals(1, 1) } @After def after = { // 後処理 } }
Scalaの文字列処理とかパターンマッチングの便利さを考えると、JavaのテストケースもScalaで書いたほうが楽かもしれない。
Monadについて
勉強中。あとでまとめる。
(2010/09/06)ざっくりまとめ
オブジェクト指向・手続き型脳味噌で理解したモナド(の概念の一部)
- モナドは、副作用の範囲を封じ込めるコンテナとして見ることができる
- 高階関数を受け取り、モナドの中身に適用して、その結果をまたモナドに詰めて返す
- 関数Aをモナドに渡し、その戻り値に関数Bを渡し、その戻り値に関数Cを渡し…と連鎖させることで、A→B→Cの評価順を確定することができる
モナドの中身を取り出すのは、Scalaではunit、Haskellではreturn←これは完全に間違い。- 値を受け取り、その値を格納したモナドのインスタンスを生成する関数を持つ(
Scalaではmap、HaskellではunitScalaではコンストラクタ、Haskellではreturn) - 関数を連鎖させた際にモナドの多重化を防ぐための仕組みが用意されている(ScalaではflatMap、Haskellではbind)
- モナドで使用する高階関数は、モナドの中身を受け取って、モナドを返す
- Scalaのfor文は、ListモナドとflatMapに展開される。
参考資料
All About Monads http://www.sampou.org/haskell/a-a-monads/html/index.html
「モナドは象だ」の翻訳まとめ - {Fight the Future => じゅくのblog} http://d.hatena.ne.jp/jyukutyo/20081111/1226392144
EclipseのJavaプロジェクトや動的WebプロジェクトでScalaソースを混在させる
「EclipseでのScala+Webアプリ開発 」の件で、とりあえずScalaコードを混ぜ込んでもビルドされるようになったので、方法の簡単に書いておきます。ただしちゃんと検証できてないので真似する際は自己責任で。
- Scala IDE for Eclipse (Scala Plugin)をインストールしておく。
- Eclipseを終了させ、対象プロジェクトのフォルダにある .project ファイルを開く。
- buildSpec要素内にある、javabuilderの設定を scalabuilderに置き換える
<!-- javabuilderをコメントアウト <buildCommand> <name>org.eclipse.jdt.core.javabuilder</name> <arguments> </arguments> </buildCommand> --> <!-- 以下追記 --> <buildCommand> <name>org.scala-ide.sdt.core.scalabuilder</name> <arguments> </arguments> </buildCommand> - nature要素内に、scalanatureの設定を追加する。
<natures> <nature>org.eclipse.jem.workbench.JavaEMFNature</nature> <nature>org.eclipse.wst.common.modulecore.ModuleCoreNature</nature> <nature>org.eclipse.wst.common.project.facet.core.nature</nature> <nature>org.eclipse.jdt.core.javanature</nature> <nature>org.eclipse.wst.jsdt.core.jsNature</nature> <nature>org.scala-ide.sdt.core.scalanature</nature> <!-- 追記 --> </natures> - Eclipseを起動する
scalabuilderは、Javaソースを見つけると処理をjavacに渡してくれるようなので、javabuilderはコメントアウトでOKです。
機能のテンプレ化に関する考察
大規模システムのフレームワークとか作っていると、まずは「機能の標準化」というお題目で、画面の流れのモデルケースを作り（例：検索→一覧→選択して編集→DB更新→検索画面へ戻る）、個別機能の設計ではこのモデルケースに極力準拠してもらいつつ、実装作業が始まる前にモデルケースの実装例をテンプレとして提示する、ということをよくやります。
ただ、これを素直にやっちゃうと、テンプレをコピペした機能が何十と出来上がっちゃって、標準そのもののバグや仕様変更があると莫大な修正工数がかかる、ということになりがちです。
テンプレをコピペさせるくらいなら、フレームワークのAPIに封じて、個別に書く部分（画面やSQL、独自の論理チェックなど）を極小化することを考えたほうがよいのは、ちょっと考えればわかることですね。
この辺を突き詰めたのがSpring Rooだったりするわけですが、本ブログでは、一歩下がって、「プロジェクト毎モデルケースのフレームワーク化」を容易にし、かつカスタマイズ柔軟性を確保する方向で考えてみます。ScalaにおけるTraitのしくみがうまく使えそうな予感。
