Arrays.sortとArrays.parallelSort
1. 概要
私たちは皆、 Arrays.sort()を使用してオブジェクトまたはプリミティブの配列をソートしました。 JDK 8では、作成者はAPIを拡張して、新しいメソッド Arrays.parallelSort()を提供しました。
このチュートリアルでは、 sort()メソッドと parallelSort()メソッドの比較を行います。
2. Arrays.sort()
Arrays.sort()メソッドは、オブジェクトまたはプリミティブの配列を並べ替えます。 この方法で使用される並べ替えアルゴリズムはデュアルピボットクイックソートです。つまり、パフォーマンスを向上させるためのクイックソートアルゴリズムのカスタム実装です。
このメソッドはシングルスレッドであり、次の2つのバリエーションがあります。
- sort(array) –配列全体を昇順で並べ替えます
- sort(array、fromIndex、toIndex) – fromIndexからtoIndexまでの要素のみを並べ替えます
両方のバリアントの例を見てみましょう。
@Test
public void givenArrayOfIntegers_whenUsingArraysSortMethod_thenSortFullArrayInAscendingOrder() {
int[] array = { 10, 4, 6, 2, 1, 9, 7, 8, 3, 5 };
int[] expected = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
Arrays.sort(array);
assertArrayEquals(expected, array);
}
@Test
public void givenArrayOfIntegers_whenUsingArraysSortWithRange_thenSortRangeOfArrayAsc() {
int[] array = { 10, 4, 6, 2, 1, 9, 7, 8, 3, 5 };
int[] expected = { 10, 4, 1, 2, 6, 7, 8, 9, 3, 5 };
Arrays.sort(array, 2, 8);
assertArrayEquals(expected, array);
}
このアプローチの長所と短所を要約してみましょう。
長所 | 短所 |
---|---|
小さいデータセットで高速に動作します | 大規模なデータセットではパフォーマンスが低下します |
システムの複数のコアは使用されません |
3. Arrays.parallelSort()
このメソッドは、オブジェクトまたはプリミティブの配列も並べ替えます。 sort()と同様に、完全配列と部分配列をソートするための2つのバリアントもあります。
@Test
public void givenArrayOfIntegers_whenUsingArraysParallelSortMethod_thenSortFullArrayInAscendingOrder() {
int[] array = { 10, 4, 6, 2, 1, 9, 7, 8, 3, 5 };
int[] expected = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
Arrays.parallelSort(array);
assertArrayEquals(expected, array);
}
@Test
public void givenArrayOfIntegers_whenUsingArraysParallelSortWithRange_thenSortRangeOfArrayAsc() {
int[] array = { 10, 4, 6, 2, 1, 9, 7, 8, 3, 5 };
int[] expected = { 10, 4, 1, 2, 6, 7, 8, 9, 3, 5 };
Arrays.parallelSort(array, 2, 8);
assertArrayEquals(expected, array);
}
parallelSort()は機能が異なります。 単一のスレッドを使用してデータを順番にソートするsort()とは異なり、は並列ソート-マージソートアルゴリズムを使用します。 配列をサブ配列に分割し、サブ配列自体を並べ替えてからマージします。
並列タスクを実行するために、ForkJoinプールを使用します。
ただし、特定の条件が満たされた場合にのみ並列処理が使用されることを知っておく必要があります。 アレイサイズが8192以下の場合、またはプロセッサにコアが1つしかない場合は、シーケンシャルデュアルピボットクイックソートアルゴリズムを使用します。 それ以外の場合は、並列ソートを使用します。
それを使用することの長所と短所を要約しましょう:
長所 | 短所 |
---|---|
大きなサイズのデータセットのパフォーマンスが向上します | 小さいサイズのアレイの場合は遅くなります |
システムの複数のコアを利用します |
4. 比較
次に、両方の方法が異なるサイズのデータセットでどのように実行されたかを見てみましょう。 以下の数値は、JMHベンチマークを使用して導き出されています。テスト環境ではAMDA10PRO2.1GhzクアッドコアプロセッサとJDK1.8.0_221を使用しています。
配列サイズ | Arrays.sort() | Arrays.parallelSort() |
---|---|---|
1000 | o.048 | 0.054 |
10000 | 0.847 | 0.425 |
100000 | 7.570 | 4.395 |
1000000 | 65.301 | 37.998 |
5. 結論
この簡単な記事では、 sort()と parallelSort()の違いを確認しました。
パフォーマンスの結果に基づいて、並べ替えるデータセットが大きい場合は、 parallelSort()の方が適していると結論付けることができます。 ただし、サイズの小さい配列の場合は、パフォーマンスが向上するため、 sort()を使用することをお勧めします。
いつものように、完全なソースコードはGitHubでから入手できます。