Arrays.sort（Object[]）とArrays.sort（int[]）の時間比較

投稿日: 2019-10-19 2022-10-15
タグ: Core Java, Java, Java Array

1. 概要

このクイックチュートリアルでは、 2つのArrays.sort（Object []）とArrays.sort（int []）の並べ替え操作を比較します。

まず、それぞれの方法を個別に説明します。その後、実行時間を測定するためのパフォーマンステストを作成します。

2. Arrays.sort（Object []）

先に進む前に、 Arrays.sort（）がプリミティブ型と参照型の両方の配列で機能することを覚えておくことが重要です。

Arrays.sort（Object []）は参照タイプを受け入れます。

たとえば、整数オブジェクトの配列があります。

Integer[] numbers = {5, 22, 10, 0};

配列を並べ替えるには、次のように簡単に使用できます。

Arrays.sort(numbers);

これで、numbers配列のすべての要素が昇順で表示されます。

[0, 5, 10, 22]

Arrays.sort（Object []）はTimSortアルゴリズムに基づいており、はO（n log（n））の時間計算量を提供します。要するに、TimSortは挿入ソートおよびMergeSortアルゴリズム。ただし、一部のQuickSort実装のような他の並べ替えアルゴリズムと比較すると、まだ低速です。

3. Arrays.sort（int []）

一方、 Arrays.sort（int []）はプリミティブint配列で機能します。

同様に、プリミティブの int[]配列を定義できます。

int[] primitives = {5, 22, 10, 0};

そして、 Arrays.sort（int []）の別の実装でソートします。今回は、プリミティブの配列を受け入れます。

Arrays.sort(primitives);

この操作の結果は、前の例と変わりません。また、primitives配列のアイテムは次のようになります。

[0, 5, 10, 22]

内部では、デュアルピボットクイックソートアルゴリズムを使用しています。 JDK 10からの内部実装は、通常、従来の1ピボットクイックソートよりも高速です。

このアルゴリズムは、O（n log（n））平均時間計算量を提供します。これは、多くのコレクションが持つべき素晴らしい平均ソート時間です。さらに、完全に配置できるという利点があるため、追加のストレージは必要ありません。

けれど、最悪の場合、その時間計算量はO（n2）です。

4. 時間比較

では、どのアルゴリズムがより高速で、なぜですか？最初にいくつかの理論を実行してから、JMHを使用していくつかの具体的なテストを実行します。

4.1. 定性分析

Arrays.sort（Object []）は通常、いくつかの異なる理由でArrays.sort（int []）と比較して低速です。

1つ目は、さまざまなアルゴリズムです。 QuickSortは多くの場合Timsortよりも高速です。

2つ目は、各メソッドが値を比較する方法です。

Arrays.sort（Object []）はあるオブジェクトを別のオブジェクトと比較する必要があるため、各要素のcompareToメソッドを呼び出す必要があります。少なくとも、これにはメソッドのルックアップと呼び出しのプッシュが必要です。比較操作が実際に何であれ、それに加えてスタックします。

一方で、 Arrays.sort（int []）は、<や>などの基本的な関係演算子を使用できます。 、シングルバイトコード命令です。

4.2. JMHパラメータ

最後に、実際のデータでどの並べ替え方法がより高速に実行されるかを調べてみましょう。そのために、 JMH （Java Microbenchmark Harness）ツールを使用してベンチマークテストを作成します。

したがって、ここでは非常に単純なベンチマークを実行します。包括的ではありませんが、は、 Arrays.sort（int []）と Arrays.sort（ Integer [] ）ソート方法。

ベンチマーククラスでは、構成アノテーションを使用します。

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@Measurement(batchSize = 100000, iterations = 10)
@Warmup(batchSize = 100000, iterations = 10)
public class ArraySortBenchmark {
}

ここでは、1回の操作の平均時間を測定し（ Mode.AverageTime）、結果をミリ秒単位で表示します（ TimeUnit.MILLISECONDS）。さらに、 batchSize パラメーターを使用して、結果の精度を高めるために100,000回の反復を実行するようにJMHに指示しています。

4.3. ベンチマークテスト

テストを実行する前に、並べ替えるデータコンテナを定義する必要があります。

@State(Scope.Thread)
public static class Initialize {
    Integer[] numbers = {-769214442, -1283881723, 1504158300, -1260321086, -1800976432, 1278262737, 
      1863224321, 1895424914, 2062768552, -1051922993, 751605209, -1500919212, 2094856518, 
      -1014488489, -931226326, -1677121986, -2080561705, 562424208, -1233745158, 41308167 };
    int[] primitives = {-769214442, -1283881723, 1504158300, -1260321086, -1800976432, 1278262737, 
      1863224321, 1895424914, 2062768552, -1051922993, 751605209, -1500919212, 2094856518, 
      -1014488489, -931226326, -1677121986, -2080561705, 562424208, -1233745158, 41308167};
}

整数[]番号とint[]プリミティブプリミティブ要素の配列を選択しましょう。 @State アノテーションは、クラスで宣言された変数がベンチマークテストの実行の一部ではないことを示します。ただし、ベンチマークメソッドでそれらを使用できます。

これで、 Arrays.sort（Integer []）の最初のマイクロベンチマークを追加する準備が整いました。

@Benchmark
public Integer[] benchmarkArraysIntegerSort(ArraySortBenchmark.Initialize state) {
    Arrays.sort(state.numbers);
    return state.numbers;
}

次に、 Arrays.sort（int []）の場合：

@Benchmark
public int[] benchmarkArraysIntSort(ArraySortBenchmark.Initialize state) {
    Arrays.sort(state.primitives);
    return state.primitives;
}

4.4. 試験結果

最後に、テストを実行して結果を比較します。

Benchmark                   Mode  Cnt  Score   Error  Units
benchmarkArraysIntSort      avgt   10  1.095 ± 0.022  ms/op
benchmarkArraysIntegerSort  avgt   10  3.858 ± 0.060  ms/op

結果から、 Arrays.sort（int []）メソッドは、おそらく以前に特定した理由により、テストでArrays.sort（Object []）よりもパフォーマンスが優れていることがわかります。

そして、数字が私たちの理論を支持しているように見えても、より良いアイデアを得るためには、より多様な入力でテストを行う必要があります。

また、ここに示す数値は単なるJMHベンチマーク結果であることに注意してください。したがって、常に独自のシステムとランタイムの範囲でテストする必要があります。

4.5. なぜティムソートなのか？

それなら、私たちはおそらく自分自身に質問をするべきです。 QuickSortの方が速い場合は、両方の実装に使用してみませんか？

QuickSortは安定していないを参照してください。そのため、オブジェクトの並べ替えには使用できません。基本的に、2つなら int sは等しいので、相対的な順序が同じであるかどうかは関係ありません。 2 他と違いはありません 2.2。ただし、オブジェクトを使用すると、ある属性で並べ替えてから別の属性で並べ替えることができるため、開始順序が重要になります。

5. 結論

記事上で、 Javaで使用可能な2つのソート方法を比較しました：Arrays.sort（int []）と Arrays.sort（ 整数[] ）。さらに、それらの実装で使用されるソートアルゴリズムについても説明しました。

最後に、ベンチマークパフォーマンステストの助けを借りて、各並べ替えオプションのサンプル実行時間を示しました。

いつものように、この記事の完全なコードは、GitHubでから入手できます。

getdocs

13036