Javaソートで遭遇したピット
問題の説明
開発者が明らかに問題のあるソートコードを書きました.大体次のようになります.
このソートには問題がありますが、どのようにテストデータを変更しても、ソート結果は正しい(テストデータ量が小さい)ので、上のコードの出力結果は以下の通りです.jdkは1.7です.
しかし、生産上は問題があります.
ぶんせき
Collections.sortは、最終的にArrays.sortを呼び出し、1.7でArrays.sortが変更されました.
Java.util.Arrays.useLegacyMergeSortというパラメータが構成されている場合は、古いLegacyMergeSortを実行します.そうでない場合は、新しいTimSortを実行します.
私たちはコードに次の言葉を加えて、出力結果は乱順で、これは予想に合っています.
生産上のJVMのパラメータをチェックしてみると、やはりこのパラメータが加わっています.
しかし、なぜTimSortの結果が正しいのでしょうか.TimSortのコードを分析し続け、特殊な処理があることを発見しました.
つまり配列が32未満の場合、この中に入り、集計されません.では、まず32より大きい状況をテストしてみましょう.
今回はやっぱり転覆しました.
なぜ32未満の場合にソートに成功したのかをコードで見てみましょう.
まず,我々の比較関数は,本当に小さい場合または等しい場合にのみ−1を返し,残りの場合には0を返し,より大きい場合も0を返した.
たとえば
2つの値
結果
一つ一つ
-1
一二
-1
三二
0
四四
-1
三一
0
簡略化のため、以下はアラビア数字で代用します.
211423を例にとると、
最初のステップは、厳密に増加または減少する最大長を見つけ、昇順であれば処理せず、降順であればreverseです.
211423は処理後112 423となり、最大減算長は3となり(1と1を比較した結果-1となるため、厳密な減算としても扱われる)、211はreverseによって112となる
次に、4番目の位置から、その位置を見つけて、データを移動して、各数字に適切な位置を見つけて、具体的なコードは以下の通りです.
112423の移動手順は、次のとおりです.
1回目:112 4 23、左側に適当な4の位置を見つけ、結果は1124 23
2回目:1124 2 3、左側に2つの適切な位置を見つけて、結果112243
3回目:112243、左に3つの適当な位置を見つけて、結果は11234で、終わります
関数全体で,c.compare(pivot,a[mid])<0のみを用いたが,0以上と0以上の場合は用いられなかったが,我々の比較関数はちょうど0未満を返す場合に正しいので,この関数数の実行結果に影響を及ぼさないという問題を発見した.つまり、本当に小さいときは-1を返し、小さいときは0や1を返し、この関数には影響しません.だからこそ、この関数は安定したソートです.
しかしcountRunAndMakeAscendingという関数には>=0が用いられている.この場合,配列の先頭がインクリメントである場合,>=0を用いる.
入力が1234123であると仮定し、前の2と1を比較すると結果は0、3と2も0、4と3も0、1と4は−1であるため、最大インクリメントシーケンスは1234であり、reverseを用いずに次の関数に渡される入力は1234 123であり、結果は3回挿入され、結果も正しい.
まとめ
以上の解析から,jdk 1.7では配列が32要素未満であり,添加対が小さい比較はいずれも−1であり,その他は0であるため,アルゴリズム自体の特性のため,結果は正しいと結論した.しかし32を超えると、間違っていて、セグメントが順番に並んでいるのが見えます.これは、集計時に比較結果が0で、集計が行われていないためです.
実はsortのComparatorは穴があって、すべての状況を周到に考慮しなければならなくて、しかも以下の特性を満たす必要があります:
1)自己反転性:x,yの比較結果とy,xの比較結果は逆である.2)伝達性:x>y,y>z,x>z.3)対称性:x=yの場合,x,zの比較結果とy,zの比較結果は同じである.
上のComparatorが正しい場合は、このように書くべきで、すべての状況を列挙して、もちろんいくつかの条件で簡略化することもできますが、簡略化の結果は上の結果で、十分なテストが必要です.
開発者が明らかに問題のあるソートコードを書きました.大体次のようになります.
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
public class Test {
public static void main(String[] args) throws InterruptedException {
// ： List Map， Map name
HashMap a = new HashMap();
a.put("name", " ");
HashMap b = new HashMap();
b.put("name", " ");
HashMap c = new HashMap();
c.put("name", " ");
HashMap d = new HashMap();
d.put("name", " ");
HashMap e = new HashMap();
e.put("name", " ");
HashMap f = new HashMap();
f.put("name", " ");
ArrayList> list = new ArrayList<>();
list.add(a);
list.add(b);
list.add(c);
list.add(d);
list.add(e);
list.add(f);
// ： ， -1 0，
Collections.sort(list, new Comparator>() {
@Override
public int compare(HashMap o1, HashMap o2) {
String n1 = o1.get("name");
String n2 = o2.get("name");
if (n1.equals(" ")) {
return -1;
}
if (n1.equals(" ") && !n2.equals(" ")) {
return -1;
}
if (n1.equals(" ") && !" ".contains(n2)) {
return -1;
}
if (n1.equals(" ") && !" ".contains(n2)) {
return -1;
}
return 0;
}
});
for(HashMap x : list) {
System.out.print(x.get("name"));
}
}
}
このソートには問題がありますが、どのようにテストデータを変更しても、ソート結果は正しい(テストデータ量が小さい)ので、上のコードの出力結果は以下の通りです.jdkは1.7です.
しかし、生産上は問題があります.
ぶんせき
Collections.sortは、最終的にArrays.sortを呼び出し、1.7でArrays.sortが変更されました.
public static void sort(T[] a, Comparator super T> c) {
if (c == null) {
sort(a);
} else {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a, c);
else
TimSort.sort(a, 0, a.length, c, null, 0, 0);
}
} Java.util.Arrays.useLegacyMergeSortというパラメータが構成されている場合は、古いLegacyMergeSortを実行します.そうでない場合は、新しいTimSortを実行します.
私たちはコードに次の言葉を加えて、出力結果は乱順で、これは予想に合っています.
System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");生産上のJVMのパラメータをチェックしてみると、やはりこのパラメータが加わっています.
しかし、なぜTimSortの結果が正しいのでしょうか.TimSortのコードを分析し続け、特殊な処理があることを発見しました.
// If array is small, do a "mini-TimSort" with no merges
if (nRemaining < MIN_MERGE) { //MIN_MERGE 32
int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
binarySort(a, lo, hi, lo + initRunLen, c);
return;
}つまり配列が32未満の場合、この中に入り、集計されません.では、まず32より大きい状況をテストしてみましょう.
public class Test {
public static void main(String[] args) throws InterruptedException {
ArrayList> list = new ArrayList<>();
String[] xx = {" "," "," "," "};
for(int i = 0; i < 35; i++) {
HashMap x = new HashMap();
x.put("name", xx[(i+17)%4]);
list.add(x);
}
Collections.sort(list, new Comparator>() {
@Override
public int compare(HashMap o1, HashMap o2) {
String n1 = o1.get("name");
String n2 = o2.get("name");
if (n1.equals(" ")) {
return -1;
}
if (n1.equals(" ") && !n2.equals(" ")) {
return -1;
}
if (n1.equals(" ") && !" ".contains(n2)) {
return -1;
}
if (n1.equals(" ") && !" ".contains(n2)) {
return -1;
}
return 0;
}
});
for(HashMap x : list) {
System.out.print(x.get("name"));
}
}
} 今回はやっぱり転覆しました.
なぜ32未満の場合にソートに成功したのかをコードで見てみましょう.
まず,我々の比較関数は,本当に小さい場合または等しい場合にのみ−1を返し,残りの場合には0を返し,より大きい場合も0を返した.
たとえば
2つの値
結果
一つ一つ
-1
一二
-1
三二
0
四四
-1
三一
0
簡略化のため、以下はアラビア数字で代用します.
211423を例にとると、
if (nRemaining < MIN_MERGE) {
int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
binarySort(a, lo, hi, lo + initRunLen, c);
return;
}最初のステップは、厳密に増加または減少する最大長を見つけ、昇順であれば処理せず、降順であればreverseです.
211423は処理後112 423となり、最大減算長は3となり(1と1を比較した結果-1となるため、厳密な減算としても扱われる)、211はreverseによって112となる
private static int countRunAndMakeAscending(T[] a, int lo, int hi,
Comparator super T> c) {
assert lo < hi;
int runHi = lo + 1;
if (runHi == hi)
return 1;
// Find end of run, and reverse range if descending
if (c.compare(a[runHi++], a[lo]) < 0) { // Descending
while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0)
runHi++;
reverseRange(a, lo, runHi);
} else { // Ascending
while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0)
runHi++;
}
return runHi - lo;
} 次に、4番目の位置から、その位置を見つけて、データを移動して、各数字に適切な位置を見つけて、具体的なコードは以下の通りです.
private static void binarySort(T[] a, int lo, int hi, int start,
Comparator super T> c) {
assert lo <= start && start <= hi;
if (start == lo)
start++;
for ( ; start < hi; start++) {
T pivot = a[start];
// Set left (and right) to the index where a[start] (pivot) belongs
int left = lo;
int right = start;
assert left <= right;
/*
* Invariants:
* pivot >= all in [lo, left).
* pivot < all in [right, start).
*/
while (left < right) {
int mid = (left + right) >>> 1;
if (c.compare(pivot, a[mid]) < 0)
right = mid;
else
left = mid + 1;
}
assert left == right;
int n = start - left; // The number of elements to move
// Switch is just an optimization for arraycopy in default case
switch (n) {
case 2: a[left + 2] = a[left + 1];
case 1: a[left + 1] = a[left];
break;
default: System.arraycopy(a, left, a, left + 1, n);
}
a[left] = pivot;
}
} 112423の移動手順は、次のとおりです.
1回目:112 4 23、左側に適当な4の位置を見つけ、結果は1124 23
2回目:1124 2 3、左側に2つの適切な位置を見つけて、結果112243
3回目:112243、左に3つの適当な位置を見つけて、結果は11234で、終わります
関数全体で,c.compare(pivot,a[mid])<0のみを用いたが,0以上と0以上の場合は用いられなかったが,我々の比較関数はちょうど0未満を返す場合に正しいので,この関数数の実行結果に影響を及ぼさないという問題を発見した.つまり、本当に小さいときは-1を返し、小さいときは0や1を返し、この関数には影響しません.だからこそ、この関数は安定したソートです.
しかしcountRunAndMakeAscendingという関数には>=0が用いられている.この場合,配列の先頭がインクリメントである場合,>=0を用いる.
private static int countRunAndMakeAscending(T[] a, int lo, int hi,
Comparator super T> c) {
assert lo < hi;
int runHi = lo + 1;
if (runHi == hi)
return 1;
// Find end of run, and reverse range if descending
if (c.compare(a[runHi++], a[lo]) < 0) { // Descending
while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0)
runHi++;
reverseRange(a, lo, runHi);
} else { // Ascending
while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0)
runHi++;
}
return runHi - lo;
} 入力が1234123であると仮定し、前の2と1を比較すると結果は0、3と2も0、4と3も0、1と4は−1であるため、最大インクリメントシーケンスは1234であり、reverseを用いずに次の関数に渡される入力は1234 123であり、結果は3回挿入され、結果も正しい.
まとめ
以上の解析から,jdk 1.7では配列が32要素未満であり,添加対が小さい比較はいずれも−1であり,その他は0であるため,アルゴリズム自体の特性のため,結果は正しいと結論した.しかし32を超えると、間違っていて、セグメントが順番に並んでいるのが見えます.これは、集計時に比較結果が0で、集計が行われていないためです.
実はsortのComparatorは穴があって、すべての状況を周到に考慮しなければならなくて、しかも以下の特性を満たす必要があります:
1)自己反転性:x,yの比較結果とy,xの比較結果は逆である.2)伝達性:x>y,y>z,x>z.3)対称性:x=yの場合,x,zの比較結果とy,zの比較結果は同じである.
上のComparatorが正しい場合は、このように書くべきで、すべての状況を列挙して、もちろんいくつかの条件で簡略化することもできますが、簡略化の結果は上の結果で、十分なテストが必要です.
Collections.sort(list, new Comparator>() {
@Override
public int compare(HashMap o1, HashMap o2) {
String n1 = o1.get("name");
String n2 = o2.get("name");
if (n1.equals(" ") && n2.equals(" ")) {
return 0;
}
if (n1.equals(" ") && n2.equals(" ")) {
return -1;
}
if (n1.equals(" ") && n2.equals(" ")) {
return -1;
}
if (n1.equals(" ") && n2.equals(" ")) {
return -1;
}
if (n1.equals(" ") && n2.equals(" ")) {
return 1;
}
......
}
});