技術とか戦略とか

SIerで証券レガシーシステムを8年いじってからSESに転職した普通の文系SEによる技術ブログ。

java:ソートキーが複数存在する場合、一時的なフォーマット変更ではなく独自Comparatorで対応するべき

複数のソートキーが存在するオブジェクトの配列について、固定長のフォーマットに直すことでソートキーを1つにできます。
しかし、フォーマットを直して1つのキーでソートできるようにするよりも、独自Comparatorを定義して複数のキーでソートした方が高速なので、そのようなケースでは独自Comparatorを定義して対応するべきです。
 
単純にフォーマット変更でコストがかかるだけでなく、ソート処理自体も複数のキーでソートした方が高速です。
複数のキーを1つのキーにまとめてソートする場合は必ずキー全体を見る必要がありますが、複数のキーでソートする場合はキーの一部を見るだけでソートできる場合があるので、複数のキーでソートした方が高速になるのだと思います。
 
以下、テスト結果です。
 

ソースコード
・SortTest.java
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);

    // 3つのソートキーによりソートする場合
    long startTime1 = System.currentTimeMillis();
    SortTestComparator comparator = new SortTestComparator();
    Collections.sort(array1, comparator);
    long endTime1 = System.currentTimeMillis();

    // フォーマット変更して1つのソートキーでソートする場合
    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("・3つのソートキーによりソートを実施");
    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
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
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回目)】
[サンプル出力]
(1つ目、123,457つ目、1,000,000つ目を出力)
0,0,0
1,2,3456
9,9,9999

[配列の差異箇所出力]
差異無し。

[処理時間]
・3つのソートキーによりソートを実施
2750 ms
・フォーマット変更を行いソートを実施
19105 ms
 (内、ソート部分だけの時間)
 3827 ms
 
【結果(2回目)】
[サンプル出力]
(1つ目、123,457つ目、1,000,000つ目を出力)
0,0,0
1,2,3456
9,9,9999

[配列の差異箇所出力]
差異無し。

[処理時間]
・3つのソートキーによりソートを実施
1692 ms
・フォーマット変更を行いソートを実施
13627 ms
 (内、ソート部分だけの時間)
 3350 ms
 
【結果(3回目)】
[サンプル出力]
(1つ目、123,457つ目、1,000,000つ目を出力)
0,0,0
1,2,3456
9,9,9999

[配列の差異箇所出力]
差異無し。

[処理時間]
・3つのソートキーによりソートを実施
2177 ms
・フォーマット変更を行いソートを実施
15333 ms
 (内、ソート部分だけの時間)
 3224 ms
 
【結果まとめ】

f:id:akira2kun:20210522193143j:plain