S-JIS[2011-03-21] 変更履歴
まずはコレクション内にInt等の単純な値が入っている場合。
val list = List.range(1, 10000+1)
一番分かりやすいのが、sumメソッドを使って合算する方法。
scala> list.sum res1: Int = 50005000
手続き型のロジックとしては、ループを使って合算していく。
var s = 0 val i = list.iterator while(i.hasNext) s += i.next s
var s = 0 for(n <- list) s += n s
var s = 0 list.foreach{ s += _ } s
foreachの他にも繰り返し処理を行う関数がある。
scala> list.reduceLeft{ _ + _ } res5: Int = 50005000
scala> list.foldLeft(0){ _ + _ } res6: Int = 50005000
再帰的な関数を使って合算する方法。
def f(s: Int, list: List[Int]): Int = { if (list.isEmpty) s else f(s + list.head, list.tail) } f(0, list)
rangeで作ったデータでは、上記のように1万くらいまでならいいが、10万とかを超えると単純な合算では正しい値にならない。
scala> val list = List.range(1, 10*10000+1)
list: List[Int] = List(1, 2, 3, 4, …)
scala> list.sum
res10: Int = 705082704
そこで、Longに変換して合算してみる。
方法 | コーディング | 備考 |
---|---|---|
sum |
scala> list.map(_.toLong).sum res11: Long = 5000050000 |
|
whileループ |
var s = 0L val i = list.iterator while(i.hasNext) s += i.next s |
|
forループ |
var s = 0L for(n <- list) s += n s |
|
foreach |
var s = 0L list.foreach{ s += _ } s |
|
reduceLeft |
list.map(_.toLong).reduceLeft{ _ + _ } |
「list.reduceLeft{ _.toLong + _.toLong } 」
とかは駄目。 |
foldLeft |
list.foldLeft(0L){ _ + _ } list.foldLeft(0L){ (s:Long, n:Int) => s + n } |
|
再帰関数 |
def f(s: Long, list: List[Int]): Long = { if (list.isEmpty) s else f(s + list.head, list.tail) } f(0, list) |
とりあえずここまでの分でベンチマークをとってみた。
/* Int */ benchmark(10, 100){ 合計算出 }.report /* Long */ benchmark(10, 10){ 合計算出 }.report
方法 | Int List.range |
Long List.range |
Int Range |
Long Range |
備考 |
---|---|---|---|---|---|
sum | 121 | 438 | 107 | 313 | Longでは「list.map(_.toLong).sum 」 |
334 | 459 | Longでは「list.iterator.map(_.toLong).sum 」 |
|||
whileループ | 115 | 119 | 115 | 156 | |
forループ | 63 | 71 | 18 | 17 | |
foreach | 76 | 72 | 20 | 18 | |
reduceLeft | 94 | 403 | 84 | 246 | Longでは「list.map(_.toLong).sum 」 |
foldLeft | 86 | 94 | 94 | 116 | |
再帰関数 | 57 | 57 | 863 | 887 | 再帰関数自体はbenchmarkブロックの外で定義。(内側に入れたらStackOverflowErrorが発生した) Rangeの場合、関数の引数はSeq[Int]にした。 |
Listでは再帰関数が速い。
一方、Rangeでは非常に遅い。
→Listはhead・tailが高速
whileループ(イテレーターを使う方式)はあまり速くない。
forループ・foreachでは、Rangeはむちゃくちゃ速い。
sumは、一番分かり易い方式なのに、一番遅いな(苦笑)
reduceLeft・foldLeftよりも遅い…。
→sumメソッドの実装内容
sumでLongに変換する際にmap(_.toLong)を間に入れるとコレクションを作り直すコストがかかるだろうからiteratorを呼ぶのも試してみたが
Listはちょっと速くなったけどRangeは遅くなったね(苦笑)
sumメソッドはTraversableで以下のように定義されている。
def sum [B >: A] (implicit num: Numeric[B]) : B
型に応じてNumericが暗黙に渡されている。
Intの場合だと、scala.math.Numeric.IntIsIntegralというオブジェクトが使われる。
trait IntIsIntegral extends Integral[Int] {
def plus(x: Int, y: Int): Int = x + y
def minus(x: Int, y: Int): Int = x - y
def times(x: Int, y: Int): Int = x * y
def quot(x: Int, y: Int): Int = x / y
def rem(x: Int, y: Int): Int = x % y
def negate(x: Int): Int = -x
def fromInt(x: Int): Int = x …関数zeroはfromInt(0)の呼び出しとなる
def toInt(x: Int): Int = x
def toLong(x: Int): Long = x
def toFloat(x: Int): Float = x
def toDouble(x: Int): Double = x
}
implicit object IntIsIntegral extends IntIsIntegral with Ordering.IntOrdering
で、sumの実体はTraversableOnceにあって、
def sum[B >: A](implicit num: Numeric[B]): B = foldLeft(num.zero)(num.plus)
なんだ、foldLeftを呼んでるだけじゃないか。
なのに自分でfoldLeftを直接呼ぶ方が実行速度が速いとは…なんでだ?
コレクション内のIntはたぶんjava.lang.Integerに置き換えられているので、アンボクシングが発生するという点ではIntIsIntegralでも自前の関数でも同じだと思うのだが…。
コード | benchmark (3回試行) [ミリ秒] |
||
---|---|---|---|
list.sum |
96 | 98 | 100 |
list.foldLeft(IntIsIntegral.zero)(IntIsIntegral.plus) |
80 | 84 | 84 |
list.foldLeft(0)((s,n)=> s + n) |
82 | 80 | 90 |
自分でfoldLeftにIntIsIntegralを指定するとsumより速くなるということは、sumはfoldLeft呼び出しをラップしている形になっている分、遅いということかな?
でもメソッド呼び出し100回分で15ミリ秒くらいの差? そんなに差があるかなぁ?
foldLeftに渡している加算用の関数は、IntIsIntegral.plusでも自前の関数でも有意な差は無い。
さて、ここからが本題。クラスの各フィールドの値を合算する。
例として、以下のようなケースクラスの各フィールドを合算してみる。
case class Sample( val value1: Int, val value2: Int, val value3: Long ) val list = List.range(1, 10000+1).map(n => Sample(1,n,n*5))
手続き脳型。
var sum1 = 0 var sum2 = 0 var sum3 = 0L val i = list.iterator while(i.hasNext) { val c = i.next sum1 += c.value1 sum2 += c.value2 sum3 += c.value3 } (sum1, sum2, sum3) //結果をタプルにしている
var sum1 = 0 var sum2 = 0 var sum3 = 0L for(c <- list) { sum1 += c.value1 sum2 += c.value2 sum3 += c.value3 } (sum1, sum2, sum3)
var sum1 = 0 var sum2 = 0 var sum3 = 0L list.foreach{ c => sum1 += c.value1 sum2 += c.value2 sum3 += c.value3 } (sum1, sum2, sum3)
reduceLeftでは集計用クラスと値が入っているクラスが同じでないといけない。
list.reduceLeft{ (s,c) => Sample(s.value1+c.value1, s.value2+c.value2, s.value3+c.value3) }
foldLeftではタプルを使うことも出来る。
list.foldLeft(Tuple3(0,0,0L)){ (s,c) => (s._1+c.value1, s._2+c.value2, s._3+c.value3) } list.foldLeft(Sample(0,0,0L)){ (s,c) => Sample(s.value1+c.value1, s.value2+c.value2, s.value3+c.value3) }
def f(list:List[Sample], sum1:Int = 0, sum2:Int = 0, sum3:Long = 0L): (Int,Int,Long) = { if(list.isEmpty) { (sum1, sum2, sum3) } else { val c = list.head f(list.tail, sum1+c.value1, sum2+c.value2, sum3+c.value3) } } f(list)
sumメソッドをそのまま単純に使うことは出来ない。
scala> list.sum
<console>:12: error: could not find implicit value for parameter num: Numeric[Sample]
list.sum
^
各フィールドは単純な数値型なので、個別にならsumメソッドが使える。
(list.map(_.value1).sum, list.map(_.value2).sum, list.map(_.value3).sum)
しかし、コーディングの見た目は分かり易いが、同じループを何度も行うのは効率が悪いよなぁ。
(一度しか実行できないコレクションなら、そもそもこの方法は使えない)
そこで、Numericクラスを定義してみる。
sumで使われるのはzero(内部はfromInt(0)の呼び出し)とplusだけ(なので、他は手を抜くことにする^^;)。
implicit object MyNumeric extends scala.math.Numeric[Sample] { def fromInt(x: Int) = Sample(x,x,x) def plus(x: Sample, y:Sample) = Sample(x.value1+y.value1, x.value2+y.value2, x.value3+y.value3) def minus(x: Sample, y:Sample) = throw new UnsupportedOperationException def times(x: Sample, y:Sample) = throw new UnsupportedOperationException def compare(x: Sample, y:Sample) = throw new UnsupportedOperationException def negate(x: Sample) = throw new UnsupportedOperationException def toDouble(x: Sample) = throw new UnsupportedOperationException def toFloat(x: Sample) = throw new UnsupportedOperationException def toLong(x: Sample) = throw new UnsupportedOperationException def toInt(x: Sample) = throw new UnsupportedOperationException } list.sum
ベンチマークをとってみた。
/** List */ List.range (1, 10000+1).map(n => Sample(1,n,n*5)) /** Vector */ Range (1, 10000+1).map(n => Sample(1,n,n*5)) /** Array */ Array.range(1, 10000+1).map(n => Sample(1,n,n*5))
benchmark(10, 100){ 合計算出 }.report
方法 | List | Vector | Array | 備考 | 更新日 | |
---|---|---|---|---|---|---|
sum | 個別 | 1139 | 813 | 752 | ||
Numeric自作 | 98 | 123 | 86 | Numericオブジェクトはループの外で定義。 | ||
whileループ | 96 | 47 | 35 | |||
115 | 8 | akihiroさんの最速ルーチン(sumByFastestWhile)。 | 2011-03-21 | |||
forループ | 78 | 63 | 47 | |||
foreach | 80 | 62 | 47 | |||
reduceLeft | 80 | 100 | 70 | |||
foldLeft | タプル | 181 | 192 | 160 | ||
同クラス | 76 | 112 | 71 | |||
再帰関数 | 55 | 5145 | 論外 | 集計関数はループの外で定義。(list.tailを渡して再帰) | ||
180 | 82 | akihiroさんのsumByRec2。(添字+1を渡して再帰) | 2011-03-21 |
フィールド毎に個別にsumメソッドを実行するのは、(富豪プログラミングを良しとしても)さすがに遅い(苦笑)
foldLeftで計算の中間状態を保持するのにタプルを使うのもちょっと遅い。たぶんボクシングが発生するのだろう。
Listだと再帰関数を使うのが最速だが、VectorやArrayではwhileループが一番速いな^^;
[2011-03-21]
akihiroさんの最速ルーチン(sumByFastestWhile)は、while(true)で無限ループにして、配列を添字でアクセスする方式。
添字をインクリメントしてアクセスしていくとそのうちArrayIndexOutOfBoundsExceptionが発生するので、そこで正常終了する。
配列アクセスには必ず添字のチェックが入るので、ループでは添字チェックを行わないという荒業(笑)
しかしびっくりするほど高速。