動的にコレクションやMapを作る場合

動的にMapを作る

関数の中で色々制御（型変換、要素を追加する or 追加しない etc）しながら新たにコレクションやMapを作りたい場合、

(1 to 1000).foldLeft(immutable.Map.empty[Int, Int]) ((map, v) => if (v % 2 == 0) map else map + (v -> v))

のような書き方をすることがあるんですが、immutable な Map を作りまくる形になるのでやっぱり重いです。

上記のようなロジックを使っているプログラムで、immutable であることより、パフォーマンスを優先したかったので、

val arr = new mutable.ArrayBuffer[Pair[Int, Int]]
(1 to 1000).foreach(v => if (v % 2 == 0) arr += (v -> v))
arr.toMap

のようにしたところ、かなり早くなりました。（上記のサンプルだと要素数が少なすぎて微妙かもしれない）

ベンチをとってみる風

せっかくなので、ちょーざっくりですがベンチをとってみました。上記のサンプルと同様の10000件のデータ（1 to 10000）を使って20回試行したものの平均です。単位は msec です。specs2のテストとして書いて実行しました。

immutable.Map/110.85            => immutable.MapをfoldLeftで map + (v -> v)
mutable.Map/70.35               => mutable.Mapにforeachで map += (v -> v)
mutable.Map.foldLeft/73.2       => mutable.MapにfoldLeftで map += (v -> v)
mutable.ArrayBuffer/62.3        => mutable.ArrayBufferにforeachで arr+= (v -> v)
mutable.ArrayBuffer.toMap/99.8  => 上記 ＋ toMap

実際に上記を適用したコードでは、1000msec → 200msec ぐらいの変化があったんですが、他の箇所にも手を入れたことによる結果かも。immutable.Mapとmutable.ArrayBuffer.toMapに思ったほど差がない。でもArrayBuffer早いですね。

ただ、sbt "test-only ***"で実行したとき、１回目だけ以下のような値になりました。（２回目以降は誤差 1msec くらいに収まる）

実行することでJITの最適化が効いたから？（よくわかってない）

immutable.Map/70.9
mutable.Map/79.45
mutable.Map.foldLeft/78.05
mutable.ArrayBuffer/59.35
mutable.ArrayBuffer.toMap/68.7

ベンチとしては色々中途半端でごめんなさい。

参考：http://d.hatena.ne.jp/chimerast/20110304/1299237142

比較対象のコレクションがmutable.ArrayBufferになっているのはこちらの記事を参考にさせていただきつつ、私のケースでパフォーマンスを求めたときに一番適しているのがmutable.ArrayBufferだと判断したためです。これとは別にMapだけでも少しベンチは取りましたがListMap以外は似たり寄ったりでした。ListMapは飛び抜けて重かったです。