最近Scalaで問題を解いてみたりしているのでTipsをまとめ.Scalaは関数的に書けるしBetter Javaとしても使いやすいのでオススメ.

Online Judge

Scalaが使えるのは今のところまだ少なく,

が対応している.

コンパイルとREPL

ScalaにはREPLがあるので,これを立ち上げて試しながら書いていける(慣れたらいらない).コンパイルはscalacを使うと遅いので,fsc (Fast Scala Compiler)を使う.Zincというincremental compilerもあってこれも速い.

コードテンプレート

scala.Appを継承するとJavaと違ってmainを定義しなくていい.

object Main {
  import java.{util => ju}
  import scala.annotation._
  import scala.collection._
  import scala.collection.{mutable => mu}
  import scala.collection.JavaConverters._
  import scala.math._

  val sc = new ju.Scanner(System.in)

  /* code here */
}

Codeforcesはソースコードチェックの正規表現がなぜかobject定義の前に{}を許さないので,{}を使うimportを書くときはobjectの中に入れてる.

入出力

基本的にはJavaと同じでScannerを使う.複数読み込むときには

val n, m = sc.nextInt()

と短く書ける.このように宣言した場合sc.nextInt()は2回評価される.

配列にn個入力読み込む時は

val arr1 = Array.fill(n)(sc.nextInt())
val arr2 = (0 until n) map (_ => sc.nextInt())
val arr3 = (1 to n) map (_ => sc.nextInt())

とする.a until b[a, b)a to b[a, b]で使い分ける.(ここでは違いはない)

出力はJava標準ライブラリよりもScalaの標準ライブラリが使いやすい.配列などのコレクションはmkString(separator)が便利.

println(n)
printf("%d\n", 0)
println(arr1.mkString(" "))

ループ

特筆すべき点はないが,C++やJavaのようなfor文がなく,whileしかない.そのようなループにはvarwhileを使ったループで代用できる.それよりもコレクションのmapforeachまたは再帰を使って書く.Scalaのfor文はmapflatMapwithFilterを使った文に変換される.

breakcontinueが存在しないので,再帰をうまく書くか,コレクションのindexWherebreakのあるループ代わり使うのが良い.breakableというのもあってこれを使うと細かい制御ができる.

コレクション

Array, List, Map, Setなどが標準ライブラリにあるので適当に使い分ける.Scala標準ライブラリのコレクションの性能特性はここを参照.共通メソッドがたくさんあり,ここにまとめられている.よく使うのはmap, foreach, fold, reduce, groupBy

mutable.Setの罠

Scala 2.9のHashSetはバグがあって遅いので,java.util.HashSetを使う.

val s = (new ju.HashSet[Int]()).asScala

とすることによってScalaのSetのインターフェースになる.(インターフェースを合わせるラッパーがかかるだけなのでasScalaは重くない.(もちろんSetだけじゃなくほかのコレクションでも使える)

関数と再帰

パフォーマンスを追求したい場合は再帰がコレクションメソッドとかよりも速い.Arrayと組み合せるのがいちばん速いがそこまで求められることはあまりない.

annotationをうまく使う

@inline def square(a: Int) = a * a

とするとコンパイラーがインライン展開してくれる

また@tailrecをつけておくと,コンパイラが末尾再帰になっているかチェックしてくれる.

@tailrec
def loop(start: Int, end: Int)(f: Int => Unit) {
  if (start < end) {
    f(start)
    loop(start + 1, end)(f)
  }
}

というのを定義しておくと

loop(a, b) { i => /* code */ }

という感じで呼び出せて,

a until b foreach { i => /* code */ }

と基本的に同値だが,単純なループだけの場合.foreachより2-3倍速い.