はじめに
はじめまして。アプリケーションエンジニアをやってる新卒1年目の石田です。
Scalaをメインで書いているのですが、Scalaは基本的にJVM上で動く言語です。なので最近はJavaについても深い洞察が必要になることが多くなりました。
そこで、今回の記事ではScalaでJavaのAPIを使うようなちょっとした小ネタを紹介したいと思います。
Ordered[T]
Scalaにおいて型に順序を付ける場合にはscala.math.Ordering[T]
やscala.math.Ordered[T]
を使う方法があります。
今回はOrdered[T]
の方に着目してみます。
ざっくりいえば、Ordered[T]
は型T
を順序付ける戦略を提供するトレイトであると言えます。
以下の実装を見てみると、抽象メソッドdef compare(that: A): Int
が一つだけあることが確認できます。つまりは、この抽象メソッドcompare
を具象クラスで実装することで、compareTo
と<
,>
,<=
,>=
といった比較演算子を型T
で扱えるようになるということですね。
trait Ordered[A] extends Any with java.lang.Comparable[A] { /** Result of comparing `this` with operand `that`. * * Implement this method to determine how instances of A will be sorted. * * Returns `x` where: * * - `x < 0` when `this < that` * * - `x == 0` when `this == that` * * - `x > 0` when `this > that` * */ def compare(that: A): Int /** Returns true if `this` is less than `that` */ def < (that: A): Boolean = (this compare that) < 0 /** Returns true if `this` is greater than `that`. */ def > (that: A): Boolean = (this compare that) > 0 /** Returns true if `this` is less than or equal to `that`. */ def <= (that: A): Boolean = (this compare that) <= 0 /** Returns true if `this` is greater than or equal to `that`. */ def >= (that: A): Boolean = (this compare that) >= 0 /** Result of comparing `this` with operand `that`. */ def compareTo(that: A): Int = compare(that) }
compareの実装
ではこの抽象メソッドcompare
はどのように実装すれば良いでしょうか。答えは実装のコメントに載っている内容そのままになります。
- this < that なら x (< 0) を返す
- this == that なら x (== 0) を返す
- this > that なら x (> 0) を返す
/** Result of comparing `this` with operand `that`. * * Implement this method to determine how instances of A will be sorted. * * Returns `x` where: * * - `x < 0` when `this < that` * * - `x == 0` when `this == that` * * - `x > 0` when `this > that` * */
順序付けに関連するフィールドが1つしかないScore
というクラスを例に、単純な実装をいくつか見てみましょう。
package sample.operator case class Score(value: Int) extends AnyVal with Ordered[Score] { override def compare(that: Score): Int = if (value < that.value) -1 else if (value > that.value) 1 else 0 }
package sample.compare case class Score(value: Int) extends AnyVal with Ordered[Score] { override def compare(that: Score): Int = value compare that.value }
比較演算子を用いた実装は、compare
の返り値がInt
なので、ぱっと見分かりにくいです。compare
メソッドに対するテストは当然必要ですが、条件に対応する整数値を注意深く返す必要があります。
それ以外はあまり問題にはならなさそうですね。
しかし、今回は順序付けに意味を持つフィールドが一つしかありませんでしたが、これが複数の場合であったならどうでしょうか?
package sample.operator case class Version(major: Int, middle: Int, minor: Int) extends Ordered[Version] { override def compare(that: Version): Int = if (major < that.major) -1 else if (major > that.major) 1 else if (middle < that.middle) -1 else if (middle > that.middle) 1 else if (minor < that.minor) -1 else if (minor > that.minor) 1 else 0 }
package sample.compare case class Version(major: Int, middle: Int, minor: Int) extends Ordered[Version] { override def compare(that: Version): Int = major.compare(that.major) match { case 0 => middle.compare(that.middle) match { case 0 => minor.compare(that.minor) match { case x => x } case x => x } case x => x } }
ちょっと分かりづらくなってきましたね。
コンパレータ構築メソッドを使って定義する
コンパレータ構築メソッド(comparator construction method)とは、JavaのAPIで、java.util.Comparator<T>
を生成するためのstatic
メソッド群のことを指します。
Javaでは、java.lang.Comparable<T>
を実装したクラスT
のprivate static final
フィールドとして、コンパレータ構築メソッドで構築されたjava.util.Comparator<T>
を保持し、クラスT
のpublic int compareTo(T o)
メソッドの実装としてjava.util.Comparator<T>
のint compare(T o1, T o2)
を呼び出すような使い方をします。Javaでの実装については省略します。
ScalaでもJavaと似たような使い方ができます。コンパレータ構築メソッドはjava.util.Comparator
以下に定義されており、使用する時にはimport java.util.Comparator._
という記述を入れれば使えるようになります。static
フィールドはScalaでは提供されていないので、コンパニオンオブジェクトのprivate val
として宣言すればほぼ同様の使い方が可能です。
まずはScore
のコンパレータ構築メソッドを使用したcompare
の実装例をみましょう。
package sample.comparator import java.util.Comparator case class Score(value: Int) extends AnyVal with Ordered[Score] { override def compare(that: Score): Int = Score.COMPARATOR.compare(this, that) } object Score { import java.util.Comparator._ private val COMPARATOR: Comparator[Score] = comparingInt(s => s.value) }
あんまり恩恵はなさそうですね。
では、以下がコンパレータ構築メソッドを使用したcompare
の実装例になります。
package sample.comparator case class Version(major: Int, middle: Int, minor: Int) extends Ordered[Version] { override def compare(that: Version): Int = Version.COMPARATOR.compare(this, that) } object Version { import java.util.Comparator import java.util.Comparator._ private val COMPARATOR: Comparator[Version] = comparingInt((v: Version) => v.major) .thenComparingInt((v: Version) => v.middle) .thenComparingInt(v => v.minor) }
comparing
、comparingInt
、comparingDouble
、comparingLong
などの構築メソッドが先行し、その後ろにthenComparingXXX
といったメソッドがチェーンしています。比較の優先順位が高いものから順に構築メソッドをチェーンすることによって、目的のjava.util.Comparator<T>
を生成することができます。そうして生成されたコンパレータのcompare
を呼び出すだけで型T
の順序付けの定義が可能です。major
、middle
、minor
の順で比較されているのが見て取れると思います。
Benchmark
Javaでは、自己定義したcompare
メソッドが、コンパレータ構築メソッドを使って構築したメソッドよりも劇的に高速になることは往々にして無いそうです。
ではScalaではどのようになるのでしょうか。(予想としては、java.util.Comparator<T>
のcompare
の内部実装ではjava.lang.Integer
での比較を行なっているようなので、ScalaのInt
からのimplicit conversion
が走ったりする気がするので若干遅くなりそうです。)
そこで、sbt-jmhを使ったベンチマークを使った比較を行なってみます。
これまでに出てきた3種類のScore
の実装を用いて、10000個のランダムな0~99の整数をソートするベンチマークを以下に記述しました。(List
のsorted
は、implicit parameter
としてOrdering[T]
を受け取りますが、scala.math.LowPriorityOrderingImplicits
によってスコープ内に存在するOrdered[T]
をOrdering[T]
に暗黙変換するので、Order[T]
を定義しているT
はOrdering[T]
を定義する必要性がありません。)
package sample import org.openjdk.jmh.annotations.{Benchmark, Scope, State} import scala.util.Random @State(Scope.Thread) class ComparatorConstructionMethodBenchmark { val intValues: List[Int] = Stream.from(0). map { _ => Math.abs(Random.nextInt() % 100) }. take(10000). toList val comparatorScores: List[comparator.Score] = intValues map comparator.Score.apply val compareScores : List[compare.Score] = intValues map compare.Score.apply val operatorScores : List[operator.Score] = intValues map operator.Score.apply @Benchmark def case_comparator(): List[comparator.Score] = { comparatorScores.sorted } @Benchmark def case_compare(): List[compare.Score] = { compareScores.sorted } @Benchmark def case_operator(): List[operator.Score] = { operatorScores.sorted } }
実行環境は以下です。
scalaVersion := "2.12.6"
$ system_profiler SPHardwareDataType Hardware: Hardware Overview: Model Name: MacBook Pro Model Identifier: MacBookPro14,1 Processor Name: Intel Core i5 Processor Speed: 2.3 GHz Number of Processors: 1 Total Number of Cores: 2 L2 Cache (per Core): 256 KB L3 Cache: 4 MB Memory: 8 GB
結果は以下のようになります。
[IJ]sbt:sbt-jmh-benchmark> jmh:run -i 20 -wi 20 -f1 -t 1 ... [info] # Run complete. Total time: 00:26:44 [info] REMEMBER: The numbers below are just data. To gain reusable insights, you need to follow up on [info] why the numbers are the way they are. Use profilers (see -prof, -lprof), design factorial [info] experiments, perform baseline and negative tests that provide experimental control, make sure [info] the benchmarking environment is safe on JVM/OS/HW level, ask for reviews from the domain experts. [info] Do not assume the numbers tell you what you want them to tell. [info] Benchmark Mode Cnt Score Error Units [info] ComparatorConstructionMethodBenchmark.case_comparator thrpt 20 535.485 ± 33.028 ops/s [info] ComparatorConstructionMethodBenchmark.case_compare thrpt 20 379.922 ± 19.494 ops/s [info] ComparatorConstructionMethodBenchmark.case_operator thrpt 20 734.289 ± 44.402 ops/s
ローカル環境ではif-else
を使った実装が最速のようですが、その次にコンパレータ構築メソッドを使って構築したコンパレータを使った場合。最も遅かったのはcompare
を使った場合。
となると、分かりやすさを重視してコンパレータ構築メソッドを使うという方法も十分選択肢として入ってくるでしょう。
まとめ
JavaのAPIであるコンパレータ構築メソッドを使って、ScalaでもOrdered[T]
のcompare
を楽に、簡潔に実装することができました。
参考文献
- Bloch, J. and 柴田, 芳. (2018). Effective Java. 3rd ed. 丸善出版.
- Takahashi, M. (2012). Ordered And Ordering. [online] act-act. Available at: https://masayuki038.github.io/blog/2012/07/23/ordered-and-ordering-in-scala/ [Accessed 22 Feb. 2019].
追記(2019/03/11)
ScalaのOrderingにも同様の機能があるという指摘をいただきましたので、こちらについても説明を加えたいと思います(記事執筆時点でScalaでは同様のものが無いという勘違いをしていました)。ScalaではOrdering.by[T, S]
メソッドによって、Ordering[T]
を構築することが可能です。このOrdering[T]
を使って、Ordered[T]
のcompare
を実装することが可能です。
package sample.ordering case class Score(value: Int) extends AnyVal with Ordered[Score] { override def compare(that: Score): Int = Score.ORDERING.compare(this, that) } object Score { implicit val ORDERING: Ordering[Score] = Ordering.by(score => score.value) }
ScalaのOrdering.by[T, S]
メソッドは、Javaのコンパレータ構築メソッドと異なり、型T
を型S
に変換する関数を引数として与え、型S
のOrdering[S]
をimplicit parameter
によって解決することで最終的なOrdering[T]
を構築します。ではVersion
を例に複数個の比較対象がある場合について解説します。
package sample.ordering case class Version(major: Int, middle: Int, minor: Int) extends Ordered[Version] { override def compare(that: Version): Int = Version.ORDERING.compare(this, that) } object Version { implicit val ORDERING: Ordering[Version] = Ordering.by(v => (v.major, v.middle, v.minor)) }
Ordering.by(v => (v.major, v.middle, v.minor))
はVersion => (Int, Int, Int)
の関数と、implicit parameter
であるOrdering[(Int, Int, Int)]
を受け取ります。ここで、Ordering[(Int, Int, Int)]
はscala.math.Ordering
に定義されているimplicit conversion
であるimplicit def Tuple3[T1, T2, T3](implicit ord1: Ordering[T1], ord2: Ordering[T2], ord3: Ordering[T3]) : Ordering[(T1, T2, T3)]
によって解決されます。ここでさらに必要になるOrdering[Int]
もIntOrdering
としてすでにscala.math.Ordering
に定義されているので、Ordering.by(v => (v.major, v.middle, v.minor))
と書くだけで同様のものが定義できます。
Javaのコンパレータ構築メソッドは、ScalaのOrdering.by
とは異なりScalaの標準APIのサポートはありません。ので、ScalaとしてはOrdering.by
を使った方が良さそうです。唯一気になった点は、ScalaのOrdering.by
を使ってOrdering
を構築する場合、Version
のようなケースで、タプルのインスタンスが生成されるのがどの程度影響があるのか?ということです。なので、ほぼ影響は無いと思いますが以下のコードで一応マイクロベンチマークを取ってみます。
package sample import org.openjdk.jmh.annotations.{Benchmark, Scope, State} import scala.util.Random @State(Scope.Thread) class JavaComparatorScalaOrderingBenchmark { def nextVersion(): Int = Math.abs(Random.nextInt() % 10) val versionTuples: List[(Int, Int, Int)] = Stream.from(0). map { _ => (nextVersion(), nextVersion(), nextVersion()) }. take(10000). toList val comparatorVersions: List[comparator.Version] = versionTuples map { case (major, middle, minor) => comparator.Version(major, middle, minor) } val orderingVersions : List[ordering.Version] = versionTuples map { case (major, middle, minor) => ordering.Version(major, middle, minor) } @Benchmark def case_comparator(): List[comparator.Version] = { comparatorVersions.sorted } @Benchmark def case_ordering(): List[ordering.Version] = { orderingVersions.sorted } }
結果は以下のようになります。
[IJ]sbt:sbt-jmh-benchmark> jmh:run -i 20 -wi 20 -f1 -t 1 ... [info] # Run complete. Total time: 00:13:23 [info] REMEMBER: The numbers below are just data. To gain reusable insights, you need to follow up on [info] why the numbers are the way they are. Use profilers (see -prof, -lprof), design factorial [info] experiments, perform baseline and negative tests that provide experimental control, make sure [info] the benchmarking environment is safe on JVM/OS/HW level, ask for reviews from the domain experts. [info] Do not assume the numbers tell you what you want them to tell. [info] Benchmark Mode Cnt Score Error Units [info] JavaComparatorScalaOrderingBenchmark.case_comparator thrpt 20 228.583 ± 9.857 ops/s [info] JavaComparatorScalaOrderingBenchmark.case_ordering thrpt 20 327.559 ± 10.577 ops/s
見事にJavaコンパレータ構築メソッドで構築したComparator
を使用した場合よりも、ScalaのOrdering.by
を使って構築したOrdering
を使用した実装の方がスループットが高いという結果が出ました。(心配は杞憂に終わりました。)