比較法の定義
自作クラスをソート
次は、TreeSet をつかってソートしてみましょう。
ポイントは、
- 自作クラスのソート順ってどうやって決めるの？
です。
先に利用側プログラム UseSampleP1 を載せますが、解説はあとで。
public class UseSampleP1 {
public static void main(String[] args){
/* TreeSet で実験0 */
TreeSet<MyPoint> pset0 =
new TreeSet<MyPoint>(new MyPointComp0()); /* RecordComp0 は比較器 */
addRecordSamples(pset0); /* 要素を詰める */
System.out.println("pset0: " + pset0); /* 表示 */
...
/* Collections.sort を利用してみる */
ArrayList<MyPoint> list = new ArrayList<MyPoint>();
addRecordSamples(list);
list.sort(new MyPointComp0()); /* 実験０と同じ比較器を利用 */
System.out.println("list: " + list); /* 表示 */
}
public static void addRecordSamples(Collection<MyPoint> rcol) {
rcol.add(new MyPoint(3,4));
rcol.add(new MyPoint(2,18));
rcol.add(new MyPoint(9,3));
rcol.add(new MyPoint(2,18));
rcol.add(new MyPoint(2,10));
}
}
比較法の定義
さて、TreeSet をつかって MyPoint クラスをソートしようとすると、比較器(Comparator)を定義しなくてはなりません。
単に
TreeSet<MyPoint> pset0 = new TreeSet<MyPoint>();
とかしていると、
Exception in thread "main" java.lang.ClassCastException: kobeU.cs.samplesCol.MyPoint cannot be cast to java.lang.Comparable
at java.util.TreeMap.put(TreeMap.java:542)
at java.util.TreeSet.add(TreeSet.java:238)
at kobeU.cs.samplesCol.UseSampleP1.addRecordSamples(UseSampleP1.java:38)
at kobeU.cs.samplesCol.UseSampleP1.main(UseSampleP1.java:15)
とかいって、rcol.add(new MyPoint(3,4)); (Collection<T> col に、要素を足しているところ）で怒られています。
まあそりゃそうですよね。rcol の実体である TreeSet の立場になって考えたら、
- 「MyPoint渡しておくから、適当にソートしておいて」
とか言われている訳です。「ソート順教えろよ！！」ってものです。
Comparator 定義
比較の方法を定義するためのインタフェイス java.util.Comparator<T> というのがあります。
そいつを定義してあげます。 T というのは型パラメータで、ある型（具体的には Integer や MyPoint などの任意のクラス）を表すために使います。
例えば、Comparator<T> の場合、任意のクラス T に対して、
int compare(T o1, T o2):o1 < o2なら負の整数値を、o1 > o2なら正の整数値を、同じなら0を返す
というメソッドを備えなくては（皆さんが作成しないと）いけません。
Integer用の比較器Comparator<Integer>ならint compare(Integer, Integer)を作らなくてはいけないし、MyPoint用の比較器Comparator<MyPoint>ならint compare(MyPoint, MyPoint)を作らなくてはいけない
というわけです。
てなわけで、Comparator<MyPoint> を実装した MyPointComp0 を作成してみましょう。
public class MyPointComp0 implements Comparator<MyPoint> {
public int compare(MyPoint o1, MyPoint o2) {
int sum1 = o1.sum();
int sum2 = o2.sum();
if(sum1!=sum2) return Integer.compare(sum2, sum1);
return Integer.compare(o2.y, o1.y);
}
}
この比較器では、x+y の値が大きい順に、x+y の値が同じ場合は、yの大きい順に、x,yともに共通なら同じ要素とみなすこととします。 compare(all2,all1) や compare(o2.x, o1.x) のように、 compare(o1, o2)と並びが逆なのは、今回は大きい順に並べたいからです。
TreeSet で利用
で、TreeSet に渡します。TreeSet は、ソート機能をもった集合(Set)です。
TreeSet<MyPoint> pset0 =
new TreeSet<MyPoint>(new MyPointComp0()); /* RecordComp0 は比較器 */
addRecordSamples(pset0); /* 要素を詰める */
System.out.println("pset0: " + pset0); /* 表示 */
実行結果：
pset0: [(x: 2, y: 18), (x: 2, y: 10), (x: 9, y: 3), (x: 3, y: 4)]
注意したいのは、本来二つあった (x: 2, y: 18) が一つになっている点です。
Set は、要素の重複を省きます。その際、Comparator が 0を返すものは同一のものと 判定します。
List で利用
「Set は要素の重複省くからウザい」とか、「常時ソートして欲しくない。指定したタイミングでソートしてほしい」ってときは、java.util.List に
void sort(Comparator)メソッド
があります。
あるいは、Collection に関する util を集めた java.util.Collections というクラスが
static void sort(List,Comparator)メソッド
を持っているので、こちらでも OK。ちなみにこのCollections クラスは色々メソッドを持っているので、一度眺めてみると面白いかと。
/* Collections.sort を利用してみる */
ArrayList<MyPoint> list = new ArrayList<MyPoint>();
addRecordSamples(list);
list.sort(new MyPointComp0()); /* 実験０と同じ比較器を利用 */
// Collections.sort(list, new MyPointComp0()); こちらでもOK
System.out.println("list: " + list); /* 表示 */
実行結果
list: [(x: 2, y: 18), (x: 2, y: 18), (x: 2, y: 10), (x: 9, y: 3), (x: 3, y: 4)]
要素は減ってないですよね。 あと、sort のアルゴリズムは、安定であることが保証されています。
さまざまな記述法
anonymous inner class
(スキップ可)
プログラム表記の仕方として、anonymous inner class というものがあります。 別ファイルにクラスを書くのではなく、メソッド中などに名無しのクラス定義をいきなり書いちゃう方法です。
記法がややこしいので、自分でかけなくてもいいです。ただ、GUI などで良く見かける記法なので、知っておくといいでしょう。
以下は、x, y の辞書式降順の比較器定義の例です。
/* TreeSet で実験1 */
TreeSet<MyPoint> pset1 =
new TreeSet<MyPoint>(new Comparator<MyPoint>() {
/* 比較器定義をその場で書く方法 */
public int compare(MyPoint o1, MyPoint o2) {
int sum1 = o1.sum(), sum2 = o2.sum();
if(sum1!=sum2) return Integer.compare(sum2, sum1);
return Integer.compare(o2.y, o1.y);
}
});
addRecordSamples(pset1); /* 要素をつめて */
System.out.println("pset1: " + pset1); /* 表示 */
あと、inner class の特徴として、以下のような特徴もあります。
- それを囲む class のフィールドにアクセスできる
- それを囲むメソッドの final 変数(初期化後、更新が行われない変数)にアクセスできる
lambda 式
anonymous クラスですが、なんとなく記述が大変ですよね。 メソッド一つしかないのに、インタフェイス定義するなんて、面倒というか。
で、Java8 から lambda 式というものが登場しました。 当該メソッドの中身だけを書けば OK という感じです。
/* lambda expression をつかった表記 */
TreeSet<MyPoint> pset2 =
new TreeSet<MyPoint>((MyPoint o1, MyPoint o2) -> {
int sum1 = o1.sum(), sum2 = o2.sum();
if(sum1!=sum2) return Integer.compare(sum2, sum1);
return Integer.compare(o2.y, o1.y);
});
addRecordSamples(pset2); /* 要素をつめて */
System.out.println("pset2: " + pset2); /* 表示 */
実際には、Java の lambda expression の値は、「関数へのポインタ」ではなく、 「関数内で利用される外側の変数の値情報」も含んだ、オブジェクトっぽいものになります。 このあたりは、こちらで解説します。
Integer の時は？ (Comparable)
では、なぜ Integer は怒られなかったのか？
逆に、MyPoint がどのように怒られていたところをみてみましょう。
Exception in thread "main" java.lang.ClassCastException: kobeU.cs.samplesCol.MyPoint cannot be cast to java.lang.Comparable
意訳：MyPointは、Comparable に型変換(cast)できないじゃん。
Integer は、以下のインタフェイスを実装しているから怒られなかったんです。
- インタフェイス
Comparable: 比較可能なことを示すインタフェイス。クラスTがComparable<T>を実装する、つまり、compareTo(T o)メソッドを持つので、o1.compareTo(o2)呼び出しによる比較が可能。
つまり、Integer は、Comparable<Integer> を実装しているので、比較が出来た訳です。同様に、String, Double なども大丈夫です。表記が似ているけど、Comparable と Comparator は違うものなので、注意してください。
自作クラスも Comparable にできます。MyPoint implements Comparable<MyPoint> とし、compareTo(MyPoint) メソッドを定義するだけです。ただ、この方法では、その都度比較の方法を差し替えるといった芸当はできません。
ソートに関する Tips
TreeSet を用いたソートの方法を紹介しましたけど、他の方法もいろいろあります。
配列に関するソート
- 配列に関する util を集めた java.util.Arrays というクラスがある。
- 例えば int 配列なら static method である
sort(int[])でソート可能 - Comparable 要素の配列をソートする場合は、
sort(Object[])でOK - 一般Object要素の配列をソートする場合は、
sort(T,Comparator<T>)を利用
- java.util.Map
<T1,T2>というのは、T1 keyに対して、T2 valueを割り当てた、値の組を表現したもの。key の重複は許されない。 - java.util.TreeMap は、
Mapの一種で、keyに対してソートする機能があります。