Scalaのリストに要素を追加するときの処理時間について

コップ本を読んでいたらScalaのリストに要素を追加する処理に関する注意点が載っていました．

どういうものかというと:+より::でリストに要素を追加し，その後Listをreverseさせろというものでした．

よく分からんので試してみる．

以下，テストするために書いたコード

object Main extends App{
  // 普通の再帰
  // これだと10000で落ちる
  /*
  def addFirst(list: List[Int]): List[Int] =
    list match{
      case (head :: Nil) => List(head)
      case (head :: tail) => list.head :: addFirst(list.tail)
      case _ => list
    }
  def addLast(list: List[Int]): List[Int] =
    list match{
      case (head :: Nil) => List(head)
      case (head :: tail) =>  addFirst(list.tail) :+ list.head
      case _ => list
    }
  */

  // 末尾再帰
  def addFirst(list: List[Int], ansList: List[Int] = List.empty[Int]): List[Int] =
    if(list.size == 0) ansList
    else addFirst(list.tail, list.head :: ansList)

  def addLast(list: List[Int], ansList: List[Int] = List.empty[Int]): List[Int] =
    if(list.size == 0) ansList
    else addLast(list.tail, ansList :+ list.head)

  // 適宜長さを調節したリストを作成する
  val list = (0 until 10000).toList

  // 先頭に要素を追加していく場合
  val startFirst = System.currentTimeMillis
  addFirst(list).reverse
  println((System.currentTimeMillis - startFirst) + "msec")

  // 末尾に要素を追加していく場合
  val startLast = System.currentTimeMillis
  addLast(list)
  println((System.currentTimeMillis - startLast) + "msec")
}

結果

要素数	先頭	末尾
1,000	14ms	26ms
10,000	138ms	749ms
100,000	20866ms	114019ms

要素数が100,000で大幅に差をつけて先頭から入れる処理が勝ちました．

感想

:+，あんまり使う機会少なそう・・・