JKになりたい

何か書きたいことを書きます。主にWeb方面の技術系記事が多いかも。

トップ > Scala > Scalaコストメモ

Scalaコストメモ

Scala

自分のコードのボトルネックを探すための検証。個人的にメモった結果を貼ってるだけです＞＜＞＜＞

10万回繰り返す時間を100回計測し集計しています。

とりあえず時間測定のために、簡単な計測関数を作っておきます。

def printExecutionTime(proc: => Unit) = {
    val start = System.currentTimeMillis
    proc
    System.currentTimeMillis - start
}

（参照: Scalaで処理時間を計測 - a-sanの日記)

traitをnewする

簡単なcase classとtraitを用意

case class User(name: String)
trait A {
    val users: Seq[User]
}

以下計測コード

for{ _ <- 1 to 100}yield {
  val t = printExecutionTime {
    for {_ <- 1 to 100000} yield {
      new A {
        override val users: Seq[User] = Seq.empty
      }
    }
  }
  times += t
}
val sum = times.sum
val mean = sum / 100.0
val variance = times.map(v => Math.pow(v - mean, 2)).sum / 100.0
println(s"合計:$sum ms")
println(s"平均:$mean ms")
println(s"分散:$variance")

（結果）

合計:480 ms

平均:4.8 ms

分散:10.920000000000023

因みにSeq.empty[User]と型を明示しても差はないです。

事前にemptySeqを作っておくと、Seqインスタンス生成コストが発生しないので当然はやくなります。

val emptySeq = Seq.empty[User]

for {....} yield {
    new A {
    override val users: Seq[User] = emptySeq
    }
}

合計:243 ms

平均:2.43 ms

分散:11.745100000000015

参照を渡すだけなので、Seqインスタンスのサイズによって速度に影響がでることはありません。

val longUsers = Seq.fill(1000)(User("sample"))

for {....} yield {
    new A {
    override val users: Seq[User] = longUsers
    }
}

合計:255 ms

平均:2.55 ms

分散:10.407500000000006

classをnewする

class B(users: Seq[User])

new B(users = Seq.empty)

合計:457 ms

平均:4.57 ms

分散:32.42509999999994

new B(users = longUsers)

合計:203 ms

平均:2.03 ms

分散:10.70909999999997

traitのインスタンス化と大差なさそうです

SeqのlengthとIndexedSeqのlength

longUsers.length

Seqのとき

val longUsers = Seq.fill(1000)(User("sample"))

合計:24732 ms

平均:247.32 ms

分散:171.07760000000005

IndexedSeqのとき

val longUsers = IndexedSeq.fill(1000)(User("sample"))

合計:194 ms

平均:1.94 ms

分散:7.196400000000003

IndexedSeqのlengthは計算量O(1)ですが、Seq（List）はO(n)です。

SeqのlengthとIndexedSeqのランダムアクセス

longUsers(10)
longUsers(20)
longUsers(30)

Seqのとき 合計:992 ms 平均:9.92 ms 分散:12.473599999999994

IndexedSeqのとき

合計:232 ms

平均:2.32 ms

分散:10.397599999999994

IndexedSeqのランダムアクセスは計算量O(1)ですが、Seq（List）はO(n)です。 逆にheadとかtailはSeqの方がはやいです。

Seqインスタンス生成

Seq.fill(1000)(User("sample"))

10万回はきつかったので、1000回にしてます。

合計:2681 ms

平均:26.81 ms

分散:132.4138999999999

大きなオブジェクトをインスタンス化するのはしんどいですね。

Seqインスタンス生成ー＞シャッフル

10万回はきつかったので、1000回にしてます。

シャフルのコストはO(n)です。

random.shuffle(Seq.fill(1000)(User("sample")))

合計:6584 ms

平均:65.84 ms

分散:589.0543999999986

IndexedSeq to List

10万回はきつかったので、1000回にしてます。

longUsers.toList

合計:3329 ms

平均:33.29 ms

分散:80.40589999999993

List to IndexedSeq

longUsersSeq.toIndexedSeq

合計:580 ms

平均:5.8 ms

分散:16.120000000000033

toListの方がコストが高い

SeqのSlice

10万回に戻してます。

longUsers.slice(500,520)

Seq

合計:14837 ms

平均:148.37 ms

分散:472.6131

IndexedSeq

合計:2904 ms

平均:29.04 ms

分散:494.5183999999998

sliceもindexedSeqの方が速い。500にランダムアクセスしてそこからO(n)の計算量