Javaの「自然順序付け」とは

背景

JavaのAPIを読んでいると「自然順序付け」という単語が頻繁に出てくるので
自然順序付けについて調べたことをメモ。

自然順序付けとは

オブジェクトをソートする際、
オブジェクト同士の大小を比較し順序を決める必要があるが、
自作クラスだとコンパイラはそれをどう順序付けしてよいか判断できない。

例えば、以下のようなCharaクラスをソートしたいとする。

// 自然順序付けされていないキャラ
class Chara {
	final public int hp;
	final public String name;

	public Chara(int hp, String name) {
		this.hp = hp;
		this.name = name;
	}
}

Charaは体力hpと名前nameを持つ。
これを「体力hpの小さい順に並び替えたい」とプログラマが考えていたとして、
どこにも書いてないのでコンパイラは順序付けのやり方を知りようがない。

そのような場合に、
例えばComparableインタフェースを実装することで
そのクラスに全体順序付けを強制できる。
そしてこの順序付けを「自然順序付け」という。

例

ソートする際のやり方として、例えば以下の2つがある。

• Comparatorでクラスの外から順序付けを決める
• Comparableによりクラス内で順序付けのやり方を決めておく（自然順序付け）
  これらの例を見ていく。

Comparatorによるソート

Comparatorは、Arrays.sortなどのソートメソッドに渡すことでソート順を制御するのに使える。
まずは以下のように、compareをオーバーライドして順序を指定する。

// HPを元に昇順にする
class HpOrder implements Comparator<Chara> {
	@Override
	public int compare(Chara c1, Chara c2) {
		return c1.hp - c2.hp;
	}
}

compareは以下のように値を返せばよい：

• 最初の引数が2番目の引数より小さい場合、負の整数
• 両方が等しい場合、0
• 最初の引数が2番目の引数より大きい場合、正の整数

その他にも細かい制約があるがドキュメントを参照のこと。

実際にソートする際は、sortの引数にComparatorを渡してやればよい。

public static void main(String[] args) {
	// 初期化
	var charaList = new ArrayList<Chara>();
	charaList.add(new Chara(100, "hero"));
	charaList.add(new Chara(200, "knight"));
	charaList.add(new Chara(50, "monk"));
	charaList.forEach(c -> System.out.println(c.name + " : " + c.hp));
	// hero : 100
	// knight : 200
	// monk : 50

	// ソート
	charaList.sort(new HpOrder());
	charaList.forEach(c -> System.out.println(c.name + " : " + c.hp));
	// monk : 50
	// hero : 100
	// knight : 200
}

Comparableによるクラスの自然順序付けでのソート

Comparableインタフェースを実装することで、
クラスに全体順序付けを強制できる。

今回は以下のようにCharaをフィールドに持つHpOrderedCharaというクラスを作成する。

// 自然順序が「体力が小さい順」のキャラ
class HpOrderedChara implements Comparable<HpOrderedChara> {
	final private Chara chara;

	public HpOrderedChara(Chara chara) {
		this.chara = chara;
	}

	@Override
	public int compareTo(HpOrderedChara hpOrderedChara) {
		return this.getHp() - hpOrderedChara.getHp();
	}

	public String getName() {
		return chara.name;
	}

	public int getHp() {
		return chara.hp;
	}
}

HpOrderedCharaはComparableを実装しており、
compareToをオーバーライドする必要がある。

compareToの値の返し方はcompareとほとんど同じ：

• このオブジェクトが指定されたオブジェクトより小さい場合、負の整数
• 等しい場合、0
• このオブジェクトが指定されたオブジェクトより小さい場合、正の整数

その他細かい制約はドキュメントを参照のこと。

実際にソートする際は、sortの引数にComparator.naturalOrderを渡してやればよい。
Comparator.naturalOrderは自然順序でComparableオブジェクトを比較するコンパレータを返す。

public static void main(String[] args) {
	var charaList = new ArrayList<Chara>();
	charaList.add(new Chara(100, "hero"));
	charaList.add(new Chara(200, "knight"));
	charaList.add(new Chara(50, "monk"));

	// charaListを元にhpOrderedCharaListを初期化
	var hpOrderedCharaList = new ArrayList<HpOrderedChara>();
	charaList.forEach(chara -> hpOrderedCharaList.add(new HpOrderedChara(chara)));
	hpOrderedCharaList.forEach(c -> System.out.println(c.getName() + " : " + c.getHp()));
	// hero : 100
	// knight : 200
	// monk : 50

	// ソート
	hpOrderedCharaList.sort(Comparator.naturalOrder());
	hpOrderedCharaList.forEach(c -> System.out.println(c.getName() + " : " + c.getHp()));
	// monk : 50
	// hero : 100
	// knight : 200
}

なお、今回は自然順序付けしているので
sortにnullを渡すこともできる。

hpOrderedCharaList.sort(null);

ドキュメントには以下のように書いてある。

指定されたコンパレータがnullの場合は、リストの全要素でComparableインタフェースを実装し、要素の自然順序を使用する必要があります。

参考

Comparable (Java Platform SE 8 ) (oracle.com)
Comparator (Java Platform SE 8 ) (oracle.com)
ArrayList (Java Platform SE 8 ) (oracle.com)
java - what does arrayListName.sort(null) do? - Stack Overflow