Using the Java Comparator Construction Method in Scala

はじめに

はじめまして。アプリケーションエンジニアをやってる新卒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を使ったベンチマークを使った比較を行なってみます。

github.com

これまでに出てきた３種類の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を使用した実装の方がスループットが高いという結果が出ました。（心配は杞憂に終わりました。）