S-JIS[2011-07-16/2017-01-24] 変更履歴

Scala ソート実験

JavaでListのソートを行う場合はComparatorを使ったりして少々面倒（見た目も長い）だが、Scalaだと楽。

Java：java.util.Listをソート

List<String>を大文字小文字無視でソートするサブルーチンを作ってみる。

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

// JDK1.5（Java8ならラムダ式を使ってもっとシンプルに書ける）
public static List<String> sortIgnoreCase(List<String> list) {
	List<String> r = new ArrayList<String>(list);
	Collections.sort(r, new Comparator<String>() {
		@Override
		public int compare(String o1, String o2) {
			return o1.compareToIgnoreCase(o2);
		}
	});
	return r;
}

ソートするにはCollections.sort()を使う。
sort()は破壊的操作（つまり引数のListの中を変更する）なので、ArrayListにコピーしてそれをソートするようにした。
sort()の第2引数に比較条件を渡す。ここでComparatorを実装する必要がある。

呼び出す側の例

	List<String> list = new ArrayList<String>();
	list.add("z");
	list.add("a");
	list.add("c");
	list.add("B");

	List<String> r = sortIgnoreCase(list);

	System.out.println(list); //ソート前
	System.out.println(r);    //ソート後

実行結果：

[z, a, c, B]
[a, B, c, z]

Scala：java.util.Listをソート

まずは、Javaで書いたソート処理をそのままScalaに移植してみる。
（java.util.Listを扱う）

//Scala独自のListというクラスがあるので、間違えないようにJListという名前に変えている
import java.util.{ ArrayList, Collections, Comparator, List => JList }

def sortIgnoreCase1(list: JList[String]): JList[String] = {
  val r = new ArrayList[String](list)
  Collections.sort(r, new Comparator[String] {
    override def compare(o1: String, o2: String): Int = o1.compareToIgnoreCase(o2)
  })
  r
}

Scalaでは、メソッド本体の末尾の式の値がメソッドの戻り値になる（returnを書かない）。
メソッドに式が1つしか無い場合は波括弧を省略できる。

呼び出す側の例

  val list = new ArrayList[String]
  list.add("z")
  list.add("a")
  list.add("c")
  list.add("B")

  val r = sortIgnoreCase1(list)

  println(list)
  println(r)

Scalaでは、引数なしのコンストラクターを呼び出すときは丸括弧を省略できる。

実行結果：

[z, a, c, B]
[a, B, c, z]

ScalaのListをソート

ScalaにもListクラスがあるので、それをソートしてみる。

なお、ScalaのListはJavaのLinkedListに相当し、JavaのListはScalaのSeqに相当する。
ScalaではSeqやListはよく使うコレクションなので、インポートせずに使用できる。

def sortIgnoreCase2(list: List[String]): List[String] = {
  list.sortWith((o1, o2) => o1.compareToIgnoreCase(o2) < 0)
}

list.sortWith((o1, o2) =>
  o1.compareToIgnoreCase(o2) < 0
)

list.sortWith(
  _.compareToIgnoreCase(_) < 0
)

list.sortWith(
  _.toUpperCase < _.toUpperCase
)

list.sortBy(_.toUpperCase)

list.sorted(new Ordering[String] {
  def compare(x: String, y: String): Int = {
    x.compareToIgnoreCase(y)
  }
})

今回の例では、toUpperCaseで変換して比較（sortBy）するよりも、compareToIgnoreCase()で比較（sortWith）する方が高速だと思う。
しかしJavaBeans内の特定項目でソートしたいような場合は、sortByが便利。
また、Stringの変換をせずにソートする場合、「list.sorted」だけで（Orderingを指定しなくても）ソートできる。

呼び出す側の例

  val list = List("z", "a", "c", "B")

  val r = sortIgnoreCase2(list)

  println(list)
  println(r)

ScalaのListやSeqには、初期値を指定する初期化方法がある。
これはコンストラクター呼び出しではないので、newは付けない。（Listオブジェクトのapplyメソッド呼び出し）

実行結果：

List(z, a, c, B)
List(a, B, c, z)

java.util.ListをScalaのListとしてソート

JavaのListをScalaのListに変換、また逆にScalaのListをJavaのListに変換することが出来るので、それを使ってソートしてみる。

import java.util.{ List => JList }
import scala.collection.JavaConverters._

def sortIgnoreCase3(jlist: JList[String]): JList[String] = {
  val list = jlist.asScala
  val r = list.sortWith(_.compareToIgnoreCase(_) < 0)
  r.asJava
}

呼び出す側の例

  val list = new java.util.ArrayList[String]
  list.add("z")
  list.add("a")
  list.add("c")
  list.add("B")

  val r = sortIgnoreCase3(list)

  println(list)
  println(r)
  println(r.getClass)

実行結果：

[z, a, c, B]
[a, B, c, z]
class scala.collection.JavaConversions$MutableBufferWrapper

asJavaで変換された実体は、java.util.ArrayList等ではなく、Scala側のラッパークラス。

複数フィールドをキーとするソート

Scalaで（ケースクラス等の）複数のフィールドをキーとしてソートする例。[2017-01-19]

以下のようなデータで、key1, key2, key3でソートすることを考えてみる。

case class Record(key1: String, key2: String, key3: Int, value: String)

val seq = Seq(
  Record("abc", "zzz", 123, "a"), Record("abc", "def", 456, "b"), Record("abc", "zzz", 789, "c"),
  Record("def", "zzz", 123, "d"), Record("def", "abc", 456, "e"))

SeqのsortWithメソッドやsortedメソッドに比較関数を渡せば、自由にソートできる。

import scala.math.Ordering

val s = seq.sortWith((x, y) =>
  x.key1.compareTo(y.key1) match {
    case 0 =>
      x.key2.compareTo(y.key2) match {
        case 0 => x.key3.compareTo(y.key3) < 0
        case c => c < 0
      }
    case c => c < 0
  })

val s = seq.sorted(Ordering.fromLessThan[Record]((x, y) =>
  x.key1.compareTo(y.key1) match {
    case 0 =>
      x.key2.compareTo(y.key2) match {
        case 0 => x.key3.compareTo(y.key3) < 0
        case c => c < 0
      }
    case c => c < 0
  }))

val s = seq.sorted(new Ordering[Record] {
  def compare(x: Record, y: Record): Int =
    x.key1.compareTo(y.key1) match {
      case 0 =>
        x.key2.compareTo(y.key2) match {
          case 0 => x.key3.compareTo(y.key3)
          case c => c
        }
      case c => c
    }
})

ただ、多層的にmatch（ifでもいいけど）を書かなければいけないのがちょっと面倒。

Java8のComparatorでは、複数のComparatorを合成して1つのComparatorを作ることが出来る。

ComparatorからOrderingを作ることは出来るので、Comparatorで合成してOrderingに変換するという方法が考えられる。

import java.util.Comparator
import scala.math.Ordering

val ord = new Ordering[Record] {
  val c1 = new Comparator[Record] { def compare(x: Record, y: Record) = x.key1.compareTo(y.key1) }
  val c2 = new Comparator[Record] { def compare(x: Record, y: Record) = x.key2.compareTo(y.key2) }
  val c3 = new Comparator[Record] { def compare(x: Record, y: Record) = x.key3.compareTo(y.key3) }
  val c = c1.thenComparing(c2).thenComparing(c3)

  def compare(x: Record, y: Record) = c.compare(x, y)
}
val s = seq.sorted(ord)

OrderingにはComparatorを元にOrderingを作るメソッドもある。

val c1 = new Comparator[Record] { def compare(x: Record, y: Record) = x.key1.compareTo(y.key1) }
val c2 = new Comparator[Record] { def compare(x: Record, y: Record) = x.key2.compareTo(y.key2) }
val c3 = new Comparator[Record] { def compare(x: Record, y: Record) = x.key3.compareTo(y.key3) }
val c = c1.thenComparing(c2).thenComparing(c3)
val s1 = seq.sorted(Ordering.comparatorToOrdering(c))

ちなみに、Comparatorインスタンスをimplicitにしておけば、sortedメソッドの引数を省略できる。 （ComparatorからOrderingへの暗黙変換メソッドが用意されている為）
しかし一見して繋がりがよく分からなくなるので、やらない方がいいと思う。

val c1 = new Comparator[Record] { def compare(x: Record, y: Record) = x.key1.compareTo(y.key1) }
val c2 = new Comparator[Record] { def compare(x: Record, y: Record) = x.key2.compareTo(y.key2) }
val c3 = new Comparator[Record] { def compare(x: Record, y: Record) = x.key3.compareTo(y.key3) }
implicit val c = c1.thenComparing(c2).thenComparing(c3)
val s2 = seq.sorted

OrderingにComparatorのthenComparingのような合成方法があればいいのに…と思ったら、OrderingはComparatorを継承しているので、（Java8以降を使っていれば）thenComparingをそのまま使える。[2017-01-23]
ただしthenComparingの戻り型はComparatorなので、Orderingに変換する必要はある。

val o1 = Ordering.by((in: Record) => in.key1)
val o2 = Ordering.by((in: Record) => in.key2)
val o3 = Ordering.by((in: Record) => in.key3)
val c = o1.thenComparing(o2).thenComparing(o3)
val s = seq.sorted(Ordering.comparatorToOrdering(c))

しかし一番簡単なのは、キーのタプルを作る方法。

val s = seq.sortBy(r => (r.key1, r.key2, r.key3))

→逆順ソート
→nullソート

逆順ソート

キーのタプルを作る方法は一番簡単だが、特定のキーだけ降順にするにはどうすればよいか？[2017-01-19]
キーがInt等の数値であれば「-r.key3」のようにマイナス値にすればいいが、Stringではそうはいかない。

「逆順のOrdering」を作るクラス（下記のReverseクラス）を用意すれば、Stringでも（Intでも）対応できる。

case class Reverse[T](t: T)
implicit def reverseOrdering[T: Ordering]: Ordering[Reverse[T]] = Ordering[T].reverse.on(_.t)

val s = seq.sortBy(r => (Reverse(r.key1), Reverse(r.key2), Reverse(r.key3)))

参考： scala-languageフォーラムのWhats a good way to sort a List in Scala using more than one sort key, e.g. primary, secondary?

個別のOrderingを合成する方法であれば、特別なクラスを用意しなくても実現できる。[2017-01-23]

val o1 = Ordering.by((in: Record) => in.key1).reverse
val o2 = Ordering.by((in: Record) => in.key2).reverse
val o3 = Ordering.by((in: Record) => in.key3).reverse
val c = o1.thenComparing(o2).thenComparing(o3)
val s = seq.sorted(Ordering.comparatorToOrdering(c))

キーにnullを含むソート

キーのタプルを作る方法は、キーの値がnullだとNullPointerExceptionが発生する。[2017-01-21]

Java8のComparatorには「nullがある場合用のComparator」を作るnullsFirst, nullsLastがあるので、Comparatorを使ってソートする方式なら、それがそのまま使える。
が、逆順ソートでReverseクラスを用意する方法を参考に、以下のようなクラスを作ればnullに対応できる。

package com.example

object OrderingUtil {
  case class Reverse[T](t: T)
  implicit def reverseOrdering[T: Ordering]: Ordering[Reverse[T]] = Ordering[T].reverse.on(_.t)

  case class NullsFirst[T](t: T)
  implicit def nullsFirstOrdering[T](implicit ord: Ordering[T]): Ordering[NullsFirst[T]] = new Ordering[NullsFirst[T]] {
    def compare(x: NullsFirst[T], y: NullsFirst[T]) = (x.t, y.t) match {
      case (null, null) => 0
      case (null, _)    => -1
      case (_, null)    => 1
      case (x, y)       => ord.compare(x, y)
    }
  }

  case class NullsLast[T](t: T)
  implicit def nullsLastOrdering[T](implicit ord: Ordering[T]): Ordering[NullsLast[T]] = new Ordering[NullsLast[T]] {
    def compare(x: NullsLast[T], y: NullsLast[T]) = (x.t, y.t) match {
      case (null, null) => 0
      case (null, _)    => 1
      case (_, null)    => -1
      case (x, y)       => ord.compare(x, y)
    }
  }
}

  import com.example.OrderingUtil._

  val f = seq.sortBy(r => (NullsFirst(r.key1), NullsFirst(r.key2), NullsFirst(r.key3)))
  val l = seq.sortBy(r => (NullsLast(r.key1), NullsLast(r.key2), NullsLast(r.key3)))
  val r = seq.sortBy(r => (Reverse(NullsFirst(r.key1)), Reverse(NullsFirst(r.key2)), Reverse(NullsFirst(r.key3))))

Optionを使えばNullsFirstと同等のソートになる。[2017-01-24]
これなら、特別なクラスや暗黙変換を用意する必要は無い。

  val o = seq.sortBy(r => (Option(r.key1), Option(r.key2), Option(r.key3)))

個別のOrderingを作る場合は以下のような感じ。

val o1 = Ordering.by((in: Record) => Option(in.key1))
val o2 = Ordering.by((in: Record) => Option(in.key2))
val o3 = Ordering.by((in: Record) => Option(in.key3))
val c = o1.thenComparing(o2).thenComparing(o3)
val s = seq.sorted(Ordering.comparatorToOrdering(c))

ちなみに、Optionに対してReverseを適用してもNullsLastにはならない。nullだけ見るとnullが後ろに来るようになるが、null以外同士も逆順になってしまう為。