S-JIS[2011-03-21] 変更履歴

Scala 合算実験

Scalaコレクション内の値を合算する方法を考えてみる。


Intのコレクションを単純に合算する

まずはコレクション内にInt等の単純な値が入っている場合。

val list = List.range(1, 10000+1)

sumメソッド

一番分かりやすいのが、sumメソッドを使って合算する方法。

scala> list.sum
res1: Int = 50005000

whileループ

手続き型のロジックとしては、ループを使って合算していく。

var s = 0
val i = list.iterator
while(i.hasNext) s += i.next
s
var s = 0
for(n <- list) s += n
s

foreachによる書き換え

for式はforeachに置き換えられる

var s = 0
list.foreach{ s += _ }
s

reduceLeft・foldLeft

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)

IntのコレクションをLongで合算する

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メソッドの実装内容

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でも自前の関数でも同じだと思うのだが…。

List.range(1,10000)に対するbenchmark(10,100)
コード 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))

whileループ

手続き脳型。

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)

foreach

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・foldLeft

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メソッド

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が発生するので、そこで正常終了する。
配列アクセスには必ず添字のチェックが入るので、ループでは添字チェックを行わないという荒業(笑)
しかしびっくりするほど高速。


Scala実験へ戻る / Scala目次へ戻る / 技術メモへ戻る
メールの送信先:ひしだま