Scala Listの落とし穴

ScalaでハマったCollectionの話．

ScalaのCollectionは基本的にImmutableなのでCollectionに新しい値を追加するときは，
追加したい要素が追加された新しい(newされた)Collectionインスタンスが返ってくると考えたほうがいい．

さらに，ScalaのListは一方方向リストでポンタは常に先頭を指しているようなので，末尾に要素を追加すると非常に遅い．

Listに要素を追加する際に，+:=で，先頭に要素を追加するサンプルコード．

package edu.kzk.scala_sample.basic.collection

import scala.util.Random

object ListSample {

    def main(args: Array[String]) {
        
        // List生成
        val l = List("a", "b", "c");
        println("List", l);
        
        // 要素の追加
        var list = List[Int]();
        //var list = MutableList[Int](); // mutableだとaddした時に，newして返すので遅い
        //var list = LinkedList[Int](); // _.mutable.LinkedListは+:=が見つからなかったが遅い．
        //var list = ListBuffer[Int](); // ListBufferもaddでnewしているので遅い．
        Random.setSeed(10L);
        var stime = System.currentTimeMillis();
        for(a <- Range(0, 30000)) {
            // 先頭に追加していったほうが確実に早い
            //list = Random.nextInt(10) +: list; 
          list +:= Random.nextInt(10); 
            if (a % 10000 == 0)
                println(a);
        }
        println(list.size);
        var etime = System.currentTimeMillis();
        printf("total time: %d [s]\n", (etime - stime)/1000);
        println(list.take(100));

    }
}