ゆっちのBlog

Java8 の Arrays.parallelSort() を試してみた

Java

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");

    }

}

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^*)

Hatena タグ: Java

TAGS: Java | 2013年4月21日10:54 AM | Comment : 0

Java8 の Arrays.parallelSort() を試してみた

Recent Comments

Java

NetBeans

カテゴリー

アーカイブ

RSS FEED

ねこび～ん

メタ情報

ゆっちのカレンダー

2013年4月
月	火	水	木	金	土	日
« 3月				5月 »
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

ゆっちのBlog

Java8 の Arrays.parallelSort() を試してみた

Popular post ranking

Recent Comments

Java

NetBeans

カテゴリー

アーカイブ

RSS FEED

ねこび～ん

メタ情報

ゆっちのカレンダー