Scalaで末尾追加が遅い

他の言語を経験していると、当然のように行ってしまう末尾追加。
Scalaの場合は末尾追加が遅いとさまざまな場所で警告されているが、実際に計測してみたのでメモ。
桁違いとはこのことだった。

末尾追加 vs 先頭追加

※SeqInt のように生成するとListが生成される(コメント欄参照)

結論

先頭追加してreverseしよう

sample.scala

import org.apache.commons.lang3.time.StopWatch

def func = {
	val tail = new StopWatch
	tail.start

	var tailSeq = Seq[Int]()
	for(i <- 0 to 10000){
		tailSeq = tailSeq :+ i // 末尾追加
	}
	
	for(i <- tailSeq){
		i + 1 // 適当に計算
	}

	tail.stop
	println("tail:" + tail.getTime)
        
    val head = new StopWatch
	head.start

	var headSeq = Seq[Int]()
	for(i <- 0 to 10000){
		headSeq = i +: headSeq // 先頭追加
	}
	
	for(i <- headSeq.reverse){
		i + 1 // 適当に計算
	}

	head.stop
	println("head:" + head.getTime)
}

// 結果 ms
tail:1447
head:8