複数のソートキーが存在するオブジェクトの配列について、固定長のフォーマットに直すことでソートキーを１つにできます。
しかし、フォーマットを直して１つのキーでソートできるようにするよりも、独自Comparatorを定義して複数のキーでソートした方が高速なので、そのようなケースでは独自Comparatorを定義して対応するべきです。
単純にフォーマット変更でコストがかかるだけでなく、ソート処理自体も複数のキーでソートした方が高速です。
複数のキーを１つのキーにまとめてソートする場合は必ずキー全体を見る必要がありますが、複数のキーでソートする場合はキーの一部を見るだけでソートできる場合があるので、複数のキーでソートした方が高速になるのだと思います。
以下、テスト結果です。
【ソースコード】
・SortTest.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
import java.util.ArrayList; import java.util.Collections; public class SortTest { public static void main(String［］ args) { // ソート対象のArrayListの作成 // 一意な10,000,000個のデータを作成 // それをランダムにソートする ArrayList＜SortTestRecord＞ array1 = new ArrayList＜＞(); for (int i = 0; i < 1000000; i++) { array1.add(new SortTestRecord((i / 100000) % 10, (i / 10000) % 10, (i / 1) % 10000)); } Collections.shuffle(array1); ArrayList＜SortTestRecord＞ array2 = new ArrayList＜＞(array1); // ３つのソートキーによりソートする場合 long startTime1 = System.currentTimeMillis(); SortTestComparator comparator = new SortTestComparator(); Collections.sort(array1, comparator); long endTime1 = System.currentTimeMillis(); // フォーマット変更して１つのソートキーでソートする場合 long startTime2 = System.currentTimeMillis(); ArrayList＜String＞ array2tmp = new ArrayList＜＞(); for (int i = 0; i ＜ array2.size(); i++) { array2tmp.add(String.format("%02d", array2.get(i).getSortkey1()) + String.format("%03d", array2.get(i).getSortkey2()) + String.format("%05d", array2.get(i).getSortkey3())); } long startTime2inside = System.currentTimeMillis(); Collections.sort(array2tmp); long endTime2inside = System.currentTimeMillis(); array2 = new ArrayList＜＞(); for (int i = 0; i ＜ array2tmp.size(); i++) { array2.add(new SortTestRecord( Integer.parseInt(array2tmp.get(i).substring(0,2)), Integer.parseInt(array2tmp.get(i).substring(2,5)), Integer.parseInt(array2tmp.get(i).substring(5,10)))); } long endTime2 = System.currentTimeMillis(); // 結果確認 System.out.println("［サンプル出力］"); System.out.println("（1つ目、123,457つ目、1,000,000つ目を出力）"); array1.get(0).print(); array1.get(123456).print(); array1.get(999999).print(); System.out.println(); System.out.println("［配列の差異箇所出力］"); int diffCount = 0; for (int i = 0; i ＜ 1000000; i++) { if (array1.get(i).getSortkey1() != array2.get(i).getSortkey1() || array1.get(i).getSortkey2() != array2.get(i).getSortkey2() || array1.get(i).getSortkey3() != array2.get(i).getSortkey3()) { System.out.println((i + 1) + "つ目の要素の内容を出力"); array1.get(i).print(); array2.get(i).print(); diffCount++; } } if (diffCount == 0) { System.out.println("差異無し。"); } System.out.println(); System.out.println("［処理時間］"); System.out.println("・３つのソートキーによりソートを実施"); System.out.println((endTime1 - startTime1) + " ms"); System.out.println("・フォーマット変更を行いソートを実施"); System.out.println((endTime2 - startTime2) + " ms"); System.out.println(" （内、ソート部分だけの時間）"); System.out.println(" " + (endTime2inside - startTime2inside) + " ms"); } } |
・SortTestRecord.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
public class SortTestRecord { private int sortkey1 = 0; private int sortkey2 = 0; private int sortkey3 = 0; // コンストラクタ SortTestRecord(int sortkey1, int sortkey2, int sortkey3) { this.sortkey1 = sortkey1; this.sortkey2 = sortkey2; this.sortkey3 = sortkey3; } // getter public int getSortkey1() { return this.sortkey1; } // getter public int getSortkey2() { return this.sortkey2; } // getter public int getSortkey3() { return this.sortkey3; } // プリント用クラス public void print() { System.out.println(sortkey1 + "," + sortkey2 + "," + sortkey3); } } |
・SortTestComparator.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
import java.util.Comparator; public class SortTestComparator implements Comparator＜SortTestRecord＞ { @Override public int compare(SortTestRecord o1, SortTestRecord o2) { if (o1.getSortkey1() ＜ o2.getSortkey1()){ return -1; } else if (o1.getSortkey1() ＞ o2.getSortkey1()){ return 1; } else if (o1.getSortkey2() ＜ o2.getSortkey2()){ return -1; } else if (o1.getSortkey2() ＞ o2.getSortkey2()){ return 1; } else { return o1.getSortkey3() - o2.getSortkey3(); } } } |
【結果（１回目）】
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
［サンプル出力］ （1つ目、123,457つ目、1,000,000つ目を出力） 0,0,0 1,2,3456 9,9,9999 ［配列の差異箇所出力］ 差異無し。 ［処理時間］ ・３つのソートキーによりソートを実施 2750 ms ・フォーマット変更を行いソートを実施 19105 ms （内、ソート部分だけの時間） 3827 ms |
【結果（２回目）】
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
［サンプル出力］ （1つ目、123,457つ目、1,000,000つ目を出力） 0,0,0 1,2,3456 9,9,9999 ［配列の差異箇所出力］ 差異無し。 ［処理時間］ ・３つのソートキーによりソートを実施 1692 ms ・フォーマット変更を行いソートを実施 13627 ms （内、ソート部分だけの時間） 3350 ms |
【結果（３回目）】
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
［サンプル出力］ （1つ目、123,457つ目、1,000,000つ目を出力） 0,0,0 1,2,3456 9,9,9999 ［配列の差異箇所出力］ 差異無し。 ［処理時間］ ・３つのソートキーによりソートを実施 2177 ms ・フォーマット変更を行いソートを実施 15333 ms （内、ソート部分だけの時間） 3224 ms |
【結果まとめ】
いかがでしたでしょうか。
昔に固定長フォーマットに直してまとめてソートするという手法を実務で見かけたので試してみましたが、この手法はやめた方が良さそうなことがわかりました。
ソート処理自体も複数のキーでソートした方が高速だというのは意外でした。
コメント