useLegacyMergeSortフラグの設定
Java7以降のデフォルトのソートアルゴリズムがTimSortというものに変更されたのだが、以下の問題がある。
- Comparatorの返す値に一貫性が無いと「java.lang.IllegalArgumentException: Comparison method violates its general contract!」例外が発生する。
- TimSort自体が、ある条件ではバグっているという話がある。
元のアルゴリズムに戻す
巨大なプログラムのあちこちでComparatorを作っており、おそらくこの制約を破っているものもあるのだろうが、とにかく今まで通りのコードでソートはうまく行っていたのである。以前の動作に戻したい。
以前のアルゴリズムに戻すには、システムプロパティ「java.util.Arrays.useLegacyMergeSort」をtrueにする。いつもの通り、VMオプションとしてもよいし、プログラム起動時にSystem.setPropertyにて設定してもよい。
VMオプションの場合
-Djava.util.Arrays.useLegacyMergeSort=true
とする。
System.setPropertyの場合
System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");
とする。ただし、Arraysクラスがロードされる以前でなければいけない。Arraysクラスがロードされた後で行っても効果はない。
戻されたことを確認する
方法１
Javaのバージョンによってはこの方法は使えないかもしれないが、Java8では以下の方法で確認できる。
public static void main(String[]args) throws Exception {
System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");
Class<?>clazz = Class.forName("java.util.Arrays$LegacyMergeSort");
Field field = clazz.getDeclaredField("userRequested");
field.setAccessible(true);
System.out.println("" + field.get(null));
}
java.util.Arrays$LegacyMergeSort#userRequestedというフィールドがtrueになったことを確認できる。このフラグによってArrays内部でアルゴリズムの切り替えを行っている。
方法2
以下のコードで表示されるスタックトレース中に「java.util.Arrays.legacyMergeSort」という文字列が現れれば切り替わっている。切り替わっていない場合は「java.util.TimSort.sort」という表示になる。
public static void main(String[]args) throws Exception {
System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");
Arrays.sort(new Object[] { 1, 2 }, (a, b)-> { throw new RuntimeException(); });
}