ベンチマーク
Scala で処理時間を計測する Benchmark trait があったので
試しに 1から100万の整数要素を持つリストの各要素を合計する計算処理の時間を、
末尾再帰関数、forループ、whileループ、List の sum で計測してみた。
Benchmark の runBenchmarkメソッドは引数の times で計測の回数を指定し、
計測回数分の計測結果が入った List[Long]をかえしてくれる。計測結果の時間の単位はミリ秒。
Benchmark には multiplier フィールドがあり 1回の計測で計測対象の処理を
何回実行するかを指定できる。デフォルト値は 1 が指定されている。
ここで multiplier はデフォルト値 1 のままで実行。times はデフォルト引数で 10 回を指定。
import scala.annotation.tailrec import scala.testing.Benchmark object Test { def main(args: Array[String]) = { val list = (1 to 1000000).toList test("Test1", sum(list.head, list.tail)) test("Test2", sum2(list)) test("Test3", sum3(list)) test("Test4", list.sum) } final def test(name: String, f: => Any, times: Int = 10) = { val result = new Benchmark { def run() = f }.runBenchmark(times) println(name + ": " + (result.sum / result.size) + " " + result) } @tailrec final def sum(acc: Int, list: List[Int]): Int = { if (list.isEmpty) acc else sum(acc + list.head, list.tail) } final def sum2(list: List[Int]): Int = { var cnt = 0; for (i <- list) { cnt += i } cnt } final def sum3(list: List[Int]): Int = { var cnt = 0; var tmp = list while (!tmp.isEmpty) { cnt += tmp.head tmp = tmp.tail } cnt } }
[実行結果]
処理10回の計測テストを4回やってみた。
結果は10回の計測結果の平均値と各10回の計測結果のリストの内容を表示。
Test1:末尾再帰 Test2:for Test3:while Test4:list.sum
最適化された末尾再帰関数と while ループは、ほぼ同じくらいで最も早く、
以外にも Scala の List に元からある list.sum が一番遅かった。
for は while よりは遅く list.sum よりは早かった。
$ scala -version Scala code runner version 2.9.1 -- Copyright 2002-2011, LAMP/EPFL $ scala Test Test1: 44 List(33, 51, 26, 44, 46, 44, 45, 64, 44, 44) Test2: 53 List(57, 53, 53, 53, 53, 53, 53, 53, 52, 53) Test3: 42 List(31, 47, 25, 44, 45, 44, 45, 48, 45, 48) Test4: 72 List(59, 101, 50, 73, 73, 74, 73, 73, 76, 73) $ scala Test Test1: 41 List(32, 48, 25, 44, 44, 44, 44, 44, 44, 47) Test2: 56 List(58, 53, 55, 53, 54, 53, 79, 53, 53, 54) Test3: 45 List(31, 50, 25, 71, 45, 46, 47, 45, 47, 45) Test4: 71 List(83, 71, 42, 76, 76, 78, 76, 78, 66, 66) $ scala Test Test1: 41 List(32, 48, 25, 45, 44, 44, 44, 44, 45, 45) Test2: 52 List(55, 53, 52, 53, 53, 52, 53, 52, 52, 52) Test3: 41 List(31, 49, 24, 45, 44, 44, 45, 45, 45, 44) Test4: 64 List(53, 70, 41, 65, 77, 65, 73, 66, 66, 66)
Benchmark.scala の runBenchmarkメソッドの実装をみてみると
計測の開始時の時刻と終了時の時刻を Platform.currentTime *1 で計測
1回の計測後にPlatform.collectGarbage *2 を呼び出している。
Platform object の各メソッドには @inline アノテーションが指定されていたが、
これは C の inline と同じようなものかな ?
..snip.. def runBenchmark(noTimes: Int): List[Long] = for (i <- List.range(1, noTimes + 1)) yield { setUp val startTime = Platform.currentTime var i = 0; while (i < multiplier) { run() i += 1 } val stopTime = Platform.currentTime tearDown Platform.collectGarbage stopTime - startTime } ..snip..
[参考]
hishidamaさんの Scala Benchmark ページ
再帰
関数型言語では、副作用のないプログラムを行うため繰り返し処理はループではなく再帰を使用。
ただ、Scala で限定的に使用するループで副作用(変数の更新)があっても特に問題なさそうだが、やはりできるだけ副作用のない再帰を使いたい。
再帰のサンプルは，リスト要素の整数値を合算する再帰関数
リストのパターンマッチで Nil(空)の場合は加算する要素がないので、acc をそのまま返す。
パターンマッチでリストのhead(先頭要素) と tail(先頭以外の要素のリスト) の形式になる場合は
acc にリストの先頭要素を足した値とtail部分を引数として自分自身を再帰呼び出ししている。
import scala.annotation.tailrec object Test1 { @tailrec def sum(acc: Int, list: List[Int]): Int = { print(acc + " ") list match { case Nil => acc case e :: es => sum(acc + e, es) } } def main(args: Array[String]) = { val list = List(1, 2, 3, 4, 5, 6, 7) val result = sum(list.head, list.tail) println("result: " + result) } }
sumメソッドの引数 acc は、アキュムレータと呼ばれ、再帰関数の途中の計算結果の値を保持する。
アキュムレータを使用するのは関数の最後で再帰的に自分自身を呼び出して末尾再帰にするため。
末尾再帰はコンパイル時に最適化されて命令型コードと同等の形に変換される。
なので、リストの要素数が増えてもスタックオーバーフローは発生しない。
Scala 2.8 から再帰関数に @tailrec アノテーションをつけると末尾再帰でない場合に
コンパイルエラーにしてくれる。
実行結果
$ scala Test1 1 3 6 10 15 21 28 result: 28
次は、アキュムレータを使用していない末尾再帰でない例
sumメソッドの再帰呼び出し部分は、e + sum(es) になっているため
再帰呼び出しが最後ではなく再帰呼出し後に e と加算処理を行う。
import scala.annotation.tailrec object Test2 { @tailrec def sum(list: List[Int]): Int = { list match { case Nil => 0 case e :: es => e + sum(es) } } def main(args: Array[String]) = { val list = List(1, 2, 3, 4, 5, 6, 7) val result = sum(list) println("result: " + result) } }
@tailrec アノテーションを付けているのでコンパイルするとsumメソッドが
末尾再帰でないためコンパイルエラーになる。
@tailrec アノテーションをとっておくとコンパイルは通り
リストの要素数がある程度少なければ動作するが、リストの要素数が
増えるとスタックオーバーフロー(java.lang.StackOverflowError)が発生する。
$ scalac test2.scala
test2.scala:8: error: could not optimize @tailrec annotated method sum: it contains a recursive call not in tail position
case e :: es => e + sum(es)
^list のチェックは .. match { case .. => .. } 式のパターンマッチを使用。
case Nil は空のリストのケースで、case e :: es *1 は e が list.head で es が list.tail になりリストが先頭要素とそれ以外の要素のリストの形式になる場合をあらわしている。
list match {
case Nil => acc
case e :: es => sum(acc + e, es)
}
は
if (list.isEmpty) acc else sum(acc + list.head, list.tail)
と同じ処理になる。
上の if .. else .. 式に書き換えた Test1 オブジェクト
import scala.annotation.tailrec object Test1 { @tailrec def sum(acc: Int, list: List[Int]): Int = { print(acc + " ") if (list.isEmpty) acc else sum(acc + list.head, list.tail) } def main(args: Array[String]) = { val list = List(1, 2, 3, 4, 5, 6, 7) val result = sum(list.head, list.tail) println("result: " + result) } }
関数型言語を採用する時の壁
副作用のない処理、パターンマッチ、ケースクラス、ファーストクラス関数、高階関数、クロージャ、カリー化、関数部分適用、末尾再帰、アクター、並列処理、型推論.. それぞれが関連しあって簡潔なコードが書けて、副作用によるバグも減少できるメリットがあるのですが、現場では、なかなか関数型言語へ移行できない壁があったりします。
ネックになるところは
関数型言語導入のとっかかりとして
というような感じで徐々に現場で認知してもらって、
関数型言語へフェードインできると良いのですが..
そして、関数型言語の勉強をちまちまと継続
暗黙の引数 (implicit parameters)
引数の型に合わせた暗黙の値を指定しておくと、関数(メソッド)呼び出し時の引数を省略できる。
関数定義の引数リストで引数名の前に implicit を付けると暗黙の引数が適用される。
引数を省略しないときは関数呼び出し時の指定値がそのまま渡される。
implicit は引数リスト内の先頭の引数以外には指定できないが、これは個別の引数への指定ではなく
引数リスト全体に適用されている。
デフォルト引数によく似ているが、デフォルト引数は、関数の定義でデフォルト値を指定する
のに対して暗黙の引数は呼び出し元で引き数の暗黙の値を定義する。
例では、一般的な Int と Long にマッチさせる暗黙の引数を定義しているが、通常は個別に型を
作って偶然の型の一致が起こらないようにするのが良さそうである。
scala> def foo(a: Int, implicit b: Long): Long = a * b <console>:1: error: identifier expected but 'implicit' found. def foo(a: Int, implicit b: Int) = a * b ^ scala> def foo(implicit a: Int, b: Long): Long = a * b foo: (implicit a: Int, implicit b: Long)Long scala> implicit val defValue = 10 defValue: Int = 10 scala> implicit val defLValue = 20L defLValue: Long = 20 scala> foo res1: Long = 200 scala> foo(3, 4) res2: Long = 12
複数の引数リストをとる関数の最後尾の引数リスト以外に暗黙の引数は適用できない。
scala> def bar(a: Short)(implicit b: Long, c: Int): Long = a + b * c bar: (a: Short)(implicit b: Long, implicit c: Int)Long scala> bar(5) res3: Long = 205 scala> def foo2(implicit a: Int)(b: Int): Int = a * b <console>:1: error: '=' expected but '(' found. def foo2(implicit a: Int)(b: Int): Int = a * b ^ scala> def foo3(a: Int)(implicit b: Long)(c: Short): Long = a * b + c <console>:1: error: '=' expected but '(' found. def foo3(a: Int)(implicit b: Long)(c: Short): Long = a * b + c ^ scala> def foo4(implicit a: Int)(implicit b: Long): Long = a * b <console>:1: error: '=' expected but '(' found. def foo4(implicit a: Int)(implicit b: Long): Long = a * b ^
呼び出した関数で適用した暗黙の引数の型の implicit val 定義が
スコープ内になければエラーになる。
scala> def bar2(a: Int)(implicit b: Long, c: Short): Long = a + b * c bar7: (a: Int)(implicit b: Long, implicit c: Short)Long scala> bar2(7) <console>:11: error: could not find implicit value for parameter c: Short bar2(7) scala> implicit val defSValue: Short = 5 defSValue: Short = 5 scala> bar2(7) res8: Long = 107
呼び出した関数で適用した暗黙の引数の型のimplicit val の定義がスコープ内で
2つ以上ある場合もエラーになる。
scala> implicit val defs2: Short = 3 defs2: Short = 3 scala> bar2(7) <console>:13: error: ambiguous implicit values: both value defSValue in object $iw of type => Short and value defs2 in object $iw of type => Short match expected type Short bar2(7) ^
あるスコープで、型に定義している暗黙の値を確認するには Predef の implicitly[型] メソッドを使う。
scala> implicitly[Int] res10: Int = 10 scala> implicitly[Long] res11: Long = 20
Predef の implicitly の 定義
def implicitly[T](implicit e: T): T = e
桜満開ですが、明日は雨
最近、早起きできていなかったので、ひさびさに早起きした。
仕事は少しだけ中だるみ状態。
Scala の勉強をぼちぼちと進めているので、仕事で実用的に使える機会を
なんとかつくりたいがなかなか難しい。
あっ、こんな時間、出勤しなくては..
あと、関数型プログラミングでなにがうれしいのかということを
整理するのに、Scala のメリットというか、関数型プログラミングのメリットについて
以下まとまっていそうだったので貼りました。
かなり以前にかかれた少し小難しい論文で
「なぜ関数プログラミングは重要か」
というのもありました。
Stream
Listとほぼ同じで、違いは実際に要素が指定されるまで作成が遅延される。
要素が無限に続くリストや要素数を事前に決められないリストとして表現できる。
Stream.cons は List の :: と同じように 先頭要素とリスト(Stream)を連結する。
cons は Streamコンパニオンオブジェクトのオブジェクト。
scala> def from(start: Int): Stream[Int] = Stream.cons(start, from(start + 1)) foo: (start: Int)Stream[Int] scala> from(1).take(3).foreach(println) 1 2 3
最初に要素を指定して作成することもできる。*1
contains で要素の有無を確認できるが、無限リストの状態では、まだ追加していない要素を contains すると結果が返されないのでやってはダメ*2。放置すると OutOfMemoryError が発生。
scala> val bar = Stream(3, 4, 5) bar: scala.collection.immutable.Stream[Int] = Stream(3, ?) scala> bar(1) res2: Int = 4 scala> bar(2) res3: Int = 5 scala> bar.contains(3) res4: Boolean = true scala> bar.contains(2) res5: Boolean = false scala> val bar2 = from(5) bar6: Stream[Int] = Stream(5, ?) scala> bar2.contains(0) Exception in thread "main" java.lang.OutOfMemoryError: Java heap space at java.util.Arrays.copyOf(Arrays.java:2882) at java.lang.AbstractStringBuilder.expandCapacity(AbstractStringBuilder.java:100) ..snip..
Stream.cons は、Streamコンパニオンオブジェクトの #:: オブジェクトを使って書くことも可能
scala> Stream.cons(1, Stream.cons(2, Stream.empty)).print 1, 2, empty scala> (1 #:: 2 #:: Stream.empty).print 1, 2, empty
遅延評価
名前渡し引数(by-name parameter)
名前渡し引数は、メソッド内で引数の名前が実際に使用される時に評価される。
引数が複数回参照される場合は、参照される度に評価される。
引数の型の前に => を付ける。(引数名: => 型)
Scala は通常は、値渡し(関数を呼び出す前に引数が評価される)
scala> def foo(f: => Unit) = { print("head "); f; println(" tail") } foo: (f: => Unit)Unit scala> foo(print("foobar")) head foobar tail scala> def foo2(f: => Int) = { print("head "); print(f); println(" tail") } foo2: (f: => Int)Unit scala> val a = 3 a: Int = 3 scala> val bar = (b: Int) => { print(b); b * 2 } bar: (Int) => Int = <function1> scala> foo2(bar(a)) head 36 tail scala> foo2(a) head 3 tail
lazy val
val で宣言するフィールドまたはローカル変数の val の前に lazy を指定すると
実際に変数が使用される時に初めて評価されて初期化される。
scala> lazy val x1 = { println("init x1"); 1 } x1: Int = <lazy> scala> val x2 = { println("init x2"); 2 } init x2 x2: Int = 2 scala> x1 init x1 res5: Int = 1 scala> x1 res6: Int = 1
実際に必要となった時に初めて評価されて変数の初期化は1度しか行われない。
