Scala: Trimming Trailing Elements - List, Array and Vector

シーケンスから末尾のゼロ要素を削除する処理の性能測定

 

こちらの投稿が気になったので手元でも実験してみる。 

How do I remove trailing elements in a Scala collection? - Stack Overflow

 

計測コード

時間計測用のトレイトと、トリミング関数 2種類を用意した。

トリミング関数に渡す数列は、ランダムな数列の後ろに一定数の「0」を付け加えたもの。
List, Array, Vector のそれぞれで所要時間を計測する。 

10,000回のループを 3セット実行し、実行時間が最も短かった結果を評価する。

import scala.util.Random

trait TimeIt {
  def timeit(description: String = "", repeat: Int = 3, number: Int = 10000)(proc: => Unit) {
    def loop[A](n: Int)(f: => A) { if (n > 0) { f; loop(n - 1)(f) } }

    val elapsed = List.fill(repeat){
      val start = System.currentTimeMillis
      loop(number)(proc)
      System.currentTimeMillis - start
    }.min
    println(s"${description}: ${elapsed} msec")
  }
}

object TrimArray extends TimeIt {
  def trimA[A](a: Seq[A]) = a.reverse.dropWhile(_ == 0).reverse
  def trimB[A](a: Seq[A]) = a.take(a.lastIndexWhere(_ != 0) + 1)

  def main(args: Array[String]) {
    for (
      randoms <- List(10, 100, 1000);
      zeros <- List(10, 100, 1000)
    ) {
      // Create random sequence.
      val list = List.fill(randoms)(Random.nextInt) ++ List.fill(zeros)(0)
      val array = list.toArray
      val vector = list.toVector

      println(s"randoms: ${randoms}, zeros: ${zeros}")
      timeit("[1] List   -> reverse + dropWhile  "){ trimA(list) }
      timeit("[2] List   -> take + lastIndexWhere"){ trimB(list) }
      timeit("[3] Array  -> reverse + dropWhile  "){ trimA(array) }
      timeit("[4] Array  -> take + lastIndexWhere"){ trimB(array) }
      timeit("[5] Vector -> reverse + dropWhile  "){ trimA(vector) }
      timeit("[6] Vector -> take + lastIndexWhere"){ trimB(vector) }
    }
  }
}

 

実行結果

計測してみると、全体的に take + lastIndexWhere バージョンが明らかに速い結果となった。

ただし、List だけは take 処理で性能劣化が発生するため、末尾のゼロ要素が少なければ reverse バージョンの方が逆転して速くなることもあった。(ex. randoms: 1000, zeros: 10)

また、全体のシーケンスが長ければ長いほど、Vector の強さが際立ってくるのが面白い。

randoms: 10, zeros: 10
[1] List   -> reverse + dropWhile  : 11 msec
[2] List   -> take + lastIndexWhere: 4 msec
[3] Array  -> reverse + dropWhile  : 7 msec
[4] Array  -> take + lastIndexWhere: 3 msec
[5] Vector -> reverse + dropWhile  : 12 msec
[6] Vector -> take + lastIndexWhere: 13 msec
randoms: 10, zeros: 100
[1] List   -> reverse + dropWhile  : 22 msec
[2] List   -> take + lastIndexWhere: 13 msec
[3] Array  -> reverse + dropWhile  : 18 msec
[4] Array  -> take + lastIndexWhere: 6 msec
[5] Vector -> reverse + dropWhile  : 38 msec
[6] Vector -> take + lastIndexWhere: 9 msec
randoms: 10, zeros: 1000
[1] List   -> reverse + dropWhile  : 177 msec
[2] List   -> take + lastIndexWhere: 89 msec
[3] Array  -> reverse + dropWhile  : 93 msec
[4] Array  -> take + lastIndexWhere: 28 msec
[5] Vector -> reverse + dropWhile  : 235 msec
[6] Vector -> take + lastIndexWhere: 54 msec
randoms: 100, zeros: 10
[1] List   -> reverse + dropWhile  : 25 msec
[2] List   -> take + lastIndexWhere: 21 msec
[3] Array  -> reverse + dropWhile  : 45 msec
[4] Array  -> take + lastIndexWhere: 12 msec
[5] Vector -> reverse + dropWhile  : 48 msec
[6] Vector -> take + lastIndexWhere: 4 msec
randoms: 100, zeros: 100
[1] List   -> reverse + dropWhile  : 37 msec
[2] List   -> take + lastIndexWhere: 29 msec
[3] Array  -> reverse + dropWhile  : 53 msec
[4] Array  -> take + lastIndexWhere: 15 msec
[5] Vector -> reverse + dropWhile  : 68 msec
[6] Vector -> take + lastIndexWhere: 9 msec
randoms: 100, zeros: 1000
[1] List   -> reverse + dropWhile  : 187 msec
[2] List   -> take + lastIndexWhere: 108 msec
[3] Array  -> reverse + dropWhile  : 130 msec
[4] Array  -> take + lastIndexWhere: 55 msec
[5] Vector -> reverse + dropWhile  : 276 msec
[6] Vector -> take + lastIndexWhere: 59 msec
randoms: 1000, zeros: 10
[1] List   -> reverse + dropWhile  : 235 msec
[2] List   -> take + lastIndexWhere: 244 msec
[3] Array  -> reverse + dropWhile  : 525 msec
[4] Array  -> take + lastIndexWhere: 156 msec
[5] Vector -> reverse + dropWhile  : 385 msec
[6] Vector -> take + lastIndexWhere: 4 msec
randoms: 1000, zeros: 100
[1] List   -> reverse + dropWhile  : 303 msec
[2] List   -> take + lastIndexWhere: 240 msec
[3] Array  -> reverse + dropWhile  : 503 msec
[4] Array  -> take + lastIndexWhere: 152 msec
[5] Vector -> reverse + dropWhile  : 435 msec
[6] Vector -> take + lastIndexWhere: 11 msec
randoms: 1000, zeros: 1000
[1] List   -> reverse + dropWhile  : 406 msec
[2] List   -> take + lastIndexWhere: 314 msec
[3] Array  -> reverse + dropWhile  : 559 msec
[4] Array  -> take + lastIndexWhere: 170 msec
[5] Vector -> reverse + dropWhile  : 659 msec
[6] Vector -> take + lastIndexWhere: 101 msec