Arrays.sort(Object [])とArrays.sort(int [])の時間比較

1. 概要

このクイックチュートリアルでは、* 2つの_Arrays.sort(Object [])_と_Arrays.sort(int [])_ link:/java-sorting[sorting]操作を比較します*。
最初に、各メソッドを個別に説明します。 その後、パフォーマンステストを作成して、実行時間を測定します。

*2. Arrays.sort(Object []) *

先に進む前に、** _ https://www.baeldung.com/java-util-arrays [Arrays.sort()] _ **がプリミティブ型と参照型の両方の配列で機能することに留意することが重要です。
  • _Arrays.sort(Object [])_は参照型を受け入れます*。

    たとえば、__ Integer __objectsの配列があります。
Integer[] numbers = {5, 22, 10, 0};
配列をソートするには、単純に次を使用できます。
Arrays.sort(numbers);
現在、numbers配列にはすべての要素が昇順で含まれています。
[0, 5, 10, 22]
__Arrays.sort(Object [])__はTimSortアルゴリズムに基づいており、*時間の複雑さを_O(n log(n))_。*に与えます。要するに、TimSortはlink:を利用します/ java-insertion-sort [Insertion sort]およびlink:/java-merge-sort[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]
内部では、Dual-Pivot link:/java-quicksort[Quicksort algorithm]を使用します。 JDK 10からの内部実装は、通常、従来の1ピボットのクイックソートよりも高速です。
*このアルゴリズムは、_O(n log(n))_ average * link:/java-algorithm-complexity[*time complex *]を提供します。 これは、多くのコレクションが持つべき平均的なソート時間です。 さらに、完全に配置されているという利点があるため、追加のストレージを必要としません。
ただし、最悪の場合、その時間の複雑さは_O(n ^ 2 ^)_です。 *

4. 時間比較

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

4.1. 定性分析

  • Arrays.sort(Object [])_は、いくつかの異なる理由により、通常_Arrays.sort(int []) *と比較して低速です。

    1つは異なるアルゴリズムです。 * QuickSortは多くの場合、Timsortよりも高速です。*
    2番目は、各メソッドが値を比較する方法です。
    *を参照してください。比較操作が実際に何であれ。
    一方、* _ Arrays.sort(int [])_は、シングルバイトコード命令である_ <_や_> _ *のようなプリミティブな関係演算子を単純に使用できます。

* 4.2。 JMHパラメーター*

最後に、実際のデータでどのソート方法がより高速に実行されるかを調べましょう*。 そのために、link:/java-microbenchmark-harness[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_パラメーターを使用すると、JMHに100,000回の反復を実行して、結果の精度を高めることができます。

* 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};
}
プリミティブ要素の__Integer []番号__および_int [] _ _primitives_配列を選択しましょう。 _ @ 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は_stable_ *ではないため、_Objects_のソートに使用できません。 基本的に、2つのintsが等しい場合、1つの2 が別の2と変わらないので、それらの相対的な順序が同じであっても問題ありません。 ただし、オブジェクトでは、1つの属性で並べ替えてから別の属性で並べ替えることができるため、開始順序が重要になります。

5. 結論

この記事では、** Javaで利用可能な2つのソート方法を比較しました:_Arrays.sort(int [])_と** __ * Arrays.sort(* __ ** _ Integer [] _ ** __ *)* .__ 、実装で使用されるソートアルゴリズムについて説明しました。
最後に、ベンチマークパフォーマンステストの助けを借りて、各** _ _ **並べ替えオプションのサンプル実行時間を示しました。
いつものように、この記事の完全なコードはhttps://github.com/eugenp/tutorials/tree/master/core-java-modules/core-java-collections [GitHub]にあります。