Help us understand the problem. What is going on with this article?

Scalaのコレクション選び

結論。公式ドキュメント読みましょう。以上。

あれ?性能悪くない?

前回までの記事の通り、自分はSpark上でのグラフ風処理を実装してるわけですが、なんか処理が全然終わらない。
ただ終わらないだけじゃなく、local[8]でぶん回してる(ちなみにCPUは12コアだ)のに2コア分くらいしか働いてない。
デバッガで追っかけてみると、特定のデータ(グラフ的に言うと特定の「頂点」)の処理をずーっとやってて、他は待ちになっているようだ。

この処理では、別の頂点から受信したメッセージを、頂点に適用(計算)して、次の頂点へのメッセージを作る、ということをやってるのだけど、どうやら隣接頂点がむっちゃ多かったらしく、メッセージの構築処理をずーっとやってるようだった。

送信元が100頂点、送信先が100頂点、だと単純にメッセージ数が100×100みたいなことになっていたのだ。

にしてもいくら何でも遅くないか?というのが出発点であった。
ついでにいうと、メモリもバンバン食ってて常にGCが走ってるようなそんな感じもただよっていた。

原因はListの結合だった

Scalaには標準でこれでもか、ってほどの数のコレクションクラスが用意されているのだけど、大きく分けて「ミュータブル族」と「イミュータブル族」に分類され、公式な推奨は後者である1。いや、後述するようにどちらが良い悪いではなくて使いどころなのだけど、イミュータブルで済むところはイミュータブルで設計すべきというのが、多分Scalaに限らずプログラミング界隈でのトレンドであろう。
ということで特に何も考えずにイミュータブルなListを使っていたのだが、、、これが間違い。

var result = List[Int]()
for (i <- 0 until 10000) {
  result = result :+ i
}

こんなことをしてはいけません。
これは1万回ものListインスタンスを作っては捨て(GCに回される)を繰り返してることにほかならないので、それだけでもメモリとCPU時間の無駄な上、

(公式)COLLECTIONS|性能特性

見るとわかるように、Listの末尾に要素を追加するのは線形時間がかかるのだ!
ひどい!

よって、末尾への追加が定数時間で済むものを使って解決しましたよ、というお話。こんな感じですね。

import scala.collection.mutable.ListBuffuer

val result = ListBuffuer.empty[Int]
for (i <- 0 until 10000) {
  result += i
}

イミュータブルなコレクションでも末尾への要素追加が定数時間のものもあります(Queueとか)のでそっちを使うのもありですが、インスタンスは毎回作るのでやっぱもったいないなってことでミュータブルなコレクションを選択した。

考察 そもそもイミュータブルは銀の弾丸ではない

そゆこと。何も考えずにイミュータブルなList使ったやつが言うなって?

イミュータブルが好まれ、ミュータブルが避けられるべき理由はいくらでも文献があるので詳しくはそちらを読んでほしいが、いついかなるときでもイミュータブルが正しいわけではない。
そもそも最初の例では、イミュータブルなListをvarなresultに格納しており、resultをどんどん書き換えていくのだから、イミュータブルである意味が全くない。
ミュータブルが避けられるべきなのは、別の誰か(別のスレッドだったり、参照渡しで呼んだ関数だったり)によって書き換えられてしまう可能性があるシーンだけなので、例のように閉じたスコープで使う分にはなんら問題ない。外に出ていくとき、例えば関数の引数、戻り値をイミュータブルにしておけば大抵はそれで充分だろう。

まとめ

公式ドキュメント読みましょう。
特に性能特性は必ず読んで頭に叩き込んでおくべき(だった・・・)


  1. 故にList等のイミュータブルなコレクションはデフォルトでインポートされているが、ミュータブルなコレクションは明にインポートが必要だ。 

ayatty
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away