Java8 では Arrays.parallelSort() が導入される予定だ。
どうやら Fork/Join Framework を使っているようです。
今まではプリミティブ型はデュアルピボットのクイックソートで参照型は Tim ソートだったような記憶があります。
この記憶の信憑性はかなり低いので間違っていても怒らないでくださいね(^_^;)
そこで早速試してみることにします。
コードはシンプルなソートです。
| jp\yucchi\parallelsort\ParallelSort.java |
package jp.yucchi.parallelsort;
import java.util.Arrays;
import java.util.Date;
import java.util.Random;
public class ParallelSort {
private static final int TARGET_SIZE = 500_000_000;
private static final int LOOP_SIZE = 20;
private static long startTime;
private static long time;
private static long avgTime;
private static long sumTime;
private static int count;
private static long avg4p;
public static void main(String[] args) {
Random random = new Random(new Date().getTime());
int[] source = new int[TARGET_SIZE];
int[] copy;
for (int i = 0; i < TARGET_SIZE; ++i) {
source[i] = random.nextInt(TARGET_SIZE);
}
for (int i = 0; i < LOOP_SIZE; ++i) {
copy = Arrays.copyOfRange(source, 0, TARGET_SIZE);
startTime = System.nanoTime();
Arrays.parallelSort(copy);
time = System.nanoTime() - startTime;
System.out.println(i + 1 + "回目 : Arrays.parallelSortの処理時間は、"
+ (int) (time * 1e-9) / 3_600 + "時間"
+ (int) ((time * 1e-9) / 60) % 60 + "分"
+ (int) (time * 1e-9 % 60) + "秒"
+ Double.toString((time * 1e-9 % 60) % 1).substring(2) + "\n");
if (i > 9) {
sumTime += time;
count++;
}
}
avgTime = sumTime / count;
System.out.println("<----- Arrays.parallelSortの平均処理時間は、"
+ (int) (avgTime * 1e-9) / 3_600 + "時間"
+ (int) ((avgTime * 1e-9) / 60) % 60 + "分"
+ (int) (avgTime * 1e-9 % 60) + "秒"
+ Double.toString((avgTime * 1e-9 % 60) % 1).substring(2) + " ----->\n");
avgTime = 0;
count = 0;
sumTime = 0;
for (int i = 0; i < LOOP_SIZE; ++i) {
copy = Arrays.copyOfRange(source, 0, TARGET_SIZE);
startTime = System.nanoTime();
Arrays.sort(copy);
time = System.nanoTime() - startTime;
System.out.println(i + 1 + "回目 : Arrays.sortの処理時間は、"
+ (int) (time * 1e-9) / 3_600 + "時間"
+ (int) ((time * 1e-9) / 60) % 60 + "分"
+ (int) (time * 1e-9 % 60) + "秒"
+ Double.toString((time * 1e-9 % 60) % 1).substring(2) + "\n");
if (i > 9) {
sumTime += time;
count++;
}
}
avgTime = sumTime / count;
System.out.println("<----- Arrays.sortの平均処理時間は、"
+ (int) (avgTime * 1e-9) / 3_600 + "時間"
+ (int) ((avgTime * 1e-9) / 60) % 60 + "分"
+ (int) (avgTime * 1e-9 % 60) + "秒"
+ Double.toString((avgTime * 1e-9 % 60) % 1).substring(2) + " ----->\n");
}
}
全てのソート時間の取得と表示、そして１１回目からのソート処理平均時間の取得と表示をそれぞれ
Arrays.parallelSort() と Arrays.sort() で実行してます。
このプログラムの実行結果は概ね予測できますが下記に実行結果を貼っておきます。
1回目 : Arrays.parallelSortの処理時間は、0時間0分4秒4152691810000002
2回目 : Arrays.parallelSortの処理時間は、0時間0分3秒1656751470000004
3回目 : Arrays.parallelSortの処理時間は、0時間0分3秒4398564410000003
4回目 : Arrays.parallelSortの処理時間は、0時間0分3秒18688716800000016
5回目 : Arrays.parallelSortの処理時間は、0時間0分3秒4902016290000004
6回目 : Arrays.parallelSortの処理時間は、0時間0分3秒1557479500000003
7回目 : Arrays.parallelSortの処理時間は、0時間0分3秒5248610990000002
8回目 : Arrays.parallelSortの処理時間は、0時間0分3秒21521467700000008
9回目 : Arrays.parallelSortの処理時間は、0時間0分3秒4352946820000003
10回目 : Arrays.parallelSortの処理時間は、0時間0分3秒176553014
11回目 : Arrays.parallelSortの処理時間は、0時間0分3秒5098383400000004
12回目 : Arrays.parallelSortの処理時間は、0時間0分3秒2292058370000003
13回目 : Arrays.parallelSortの処理時間は、0時間0分3秒4357429300000004
14回目 : Arrays.parallelSortの処理時間は、0時間0分3秒20676435400000015
15回目 : Arrays.parallelSortの処理時間は、0時間0分3秒45285167800000004
16回目 : Arrays.parallelSortの処理時間は、0時間0分3秒2242083810000004
17回目 : Arrays.parallelSortの処理時間は、0時間0分3秒4621416820000004
18回目 : Arrays.parallelSortの処理時間は、0時間0分3秒5754989530000003
19回目 : Arrays.parallelSortの処理時間は、0時間0分3秒500453534
20回目 : Arrays.parallelSortの処理時間は、0時間0分3秒21473901200000034
<—– Arrays.parallelSortの平均処理時間は、0時間0分3秒3811444700000002 —–>
1回目 : Arrays.sortの処理時間は、0時間0分48秒9387049350000041
2回目 : Arrays.sortの処理時間は、0時間0分48秒9633070610000019
3回目 : Arrays.sortの処理時間は、0時間0分49秒015938085000001934
4回目 : Arrays.sortの処理時間は、0時間0分48秒9707528720000056
5回目 : Arrays.sortの処理時間は、0時間0分49秒2902336700000063
6回目 : Arrays.sortの処理時間は、0時間0分48秒9888089870000059
7回目 : Arrays.sortの処理時間は、0時間0分48秒9633770900000016
8回目 : Arrays.sortの処理時間は、0時間0分48秒9997757110000052
9回目 : Arrays.sortの処理時間は、0時間0分48秒9295900030000013
10回目 : Arrays.sortの処理時間は、0時間0分49秒08955452700000421
11回目 : Arrays.sortの処理時間は、0時間0分50秒13118777600000442
12回目 : Arrays.sortの処理時間は、0時間0分49秒8455564950000038
13回目 : Arrays.sortの処理時間は、0時間0分49秒24517728500000402
14回目 : Arrays.sortの処理時間は、0時間0分49秒12246824000000345
15回目 : Arrays.sortの処理時間は、0時間0分48秒901129044000001
16回目 : Arrays.sortの処理時間は、0時間0分49秒40450923900000646
17回目 : Arrays.sortの処理時間は、0時間0分50秒7024559510000046
18回目 : Arrays.sortの処理時間は、0時間0分49秒7857455720000033
19回目 : Arrays.sortの処理時間は、0時間0分50秒1460985550000018
20回目 : Arrays.sortの処理時間は、0時間0分51秒37098508900000127
<—– Arrays.sortの平均処理時間は、0時間0分49秒8655313240000027 —–>
Arrays.parallelSort() が３秒前半のスコアに対して Arrays.sort() は、ほぼ 50 秒かかってます。
予想通り Arrays.parallelSort() が圧倒的に高速ですね。(^_^)
その秘密は NetBeans のプロファイラで確認しました。
内部で Fork/Join Framework が使われてるのが確認されました。
Java は並行処理を簡単に実行できるようにいろいろがんばって作られてるようです。
ちなみに、アレイのサイズを２１億個まで増大させたときのプログラムの実行結果は次のようになりました。
1回目 : Arrays.parallelSortの処理時間は、0時間0分26秒7820320810000005
2回目 : Arrays.parallelSortの処理時間は、0時間0分14秒215850219
3回目 : Arrays.parallelSortの処理時間は、0時間0分15秒21248125400000006
4回目 : Arrays.parallelSortの処理時間は、0時間0分14秒17695699800000142
5回目 : Arrays.parallelSortの処理時間は、0時間0分15秒21644380900000115
6回目 : Arrays.parallelSortの処理時間は、0時間0分14秒13889982600000117
7回目 : Arrays.parallelSortの処理時間は、0時間0分15秒3859477300000016
8回目 : Arrays.parallelSortの処理時間は、0時間0分14秒15733845600000151
9回目 : Arrays.parallelSortの処理時間は、0時間0分15秒042537343000001115
10回目 : Arrays.parallelSortの処理時間は、0時間0分14秒10847939100000126
11回目 : Arrays.parallelSortの処理時間は、0時間0分15秒31738622100000136
12回目 : Arrays.parallelSortの処理時間は、0時間0分14秒09331228100000111
13回目 : Arrays.parallelSortの処理時間は、0時間0分15秒23933288000000097
14回目 : Arrays.parallelSortの処理時間は、0時間0分14秒09788163900000058
15回目 : Arrays.parallelSortの処理時間は、0時間0分15秒2869010420000002
16回目 : Arrays.parallelSortの処理時間は、0時間0分14秒1130110920000007
17回目 : Arrays.parallelSortの処理時間は、0時間0分15秒037243257000000085
18回目 : Arrays.parallelSortの処理時間は、0時間0分14秒1627590560000005
19回目 : Arrays.parallelSortの処理時間は、0時間0分15秒16421842200000114
20回目 : Arrays.parallelSortの処理時間は、0時間0分14秒3338693370000012
<—– Arrays.parallelSortの平均処理時間は、0時間0分14秒6845915220000016 —–>
1回目 : Arrays.sortの処理時間は、0時間3分46秒10638811700002293
2回目 : Arrays.sortの処理時間は、0時間3分45秒5415704870000013
3回目 : Arrays.sortの処理時間は、0時間3分44秒14708787200001439
4回目 : Arrays.sortの処理時間は、0時間3分44秒28659846600001515
5回目 : Arrays.sortの処理時間は、0時間3分44秒2646577520000051
6回目 : Arrays.sortの処理時間は、0時間3分43秒6922063590000107
7回目 : Arrays.sortの処理時間は、0時間3分43秒25756076300001496
8回目 : Arrays.sortの処理時間は、0時間3分44秒48740214200000764
9回目 : Arrays.sortの処理時間は、0時間3分42秒6569463620000136
10回目 : Arrays.sortの処理時間は、0時間3分42秒32911070500000505
11回目 : Arrays.sortの処理時間は、0時間3分41秒22716906600001607
12回目 : Arrays.sortの処理時間は、0時間3分41秒819911870000027
13回目 : Arrays.sortの処理時間は、0時間3分41秒3822147500000028
14回目 : Arrays.sortの処理時間は、0時間3分41秒0946705690000158
15回目 : Arrays.sortの処理時間は、0時間3分42秒02558318500001633
16回目 : Arrays.sortの処理時間は、0時間3分51秒4318844270000284
17回目 : Arrays.sortの処理時間は、0時間3分52秒048210971000003155
18回目 : Arrays.sortの処理時間は、0時間3分52秒01929548700002215
19回目 : Arrays.sortの処理時間は、0時間3分52秒04963036800000964
20回目 : Arrays.sortの処理時間は、0時間3分52秒09709150600002658
<—– Arrays.sortの平均処理時間は、0時間3分46秒7195662190000007 —–>
Java8 の正式リリースが待ち遠しいです！
ちなみに 9 月 9 日にリリース予定だったのですが、どうやら遅れそうです。
ツイッター上では 2014 年になるとか・・・つぶやかれていました。
今のうちにもっと情報集めて Java8 をしっかり楽しめるようにがんばってみるとしよう。(*^o^*)