IntStreamを降順ソートする方法

java言語で整数列をソートする場合、 IntStream用いたソートを思い浮かべるが IntStream#sorted()は昇順ソートしかできず、標準APIからは降順ソートができない。

調べてみると、Stream<Integer>に変換してComparatorを用いて逆順ソートする類が多い模様。
なので、IntStreamのまま降順ソートする方法をメモ書きしておく。

理論

昇順ソート結果が「$n_1, n_2, n_3, ...$」の実数は、以下の関係が成立する
\[ n_1 \leq n_2 \leq n_3 \leq .... \]

符号を反転(両辺にマイナス1を掛ける)させると、不等号も反転し
\[ -n_1 \geq -n_2 \geq -n_3 \geq .... \] 
つまり、反転状態で昇順ソートを行うと「$...., -n_3, -n_2, -n_1$」が成立。
その後、符号を戻せば、「$...., n_3, n_2, n_1$」となり、降順ソートとなる

実装

こんな感じ。

class Main {
    public static void main(String[] args) {
        int[] arr = {3, 2, 4, -5, -2, 14, 5, 6, 4};
        arr = java.util.Arrays.stream(arr) // ストリーム作る
            .map(n -> -n) // 符号反転
            .sorted()     // 昇順ソート
            .map(n -> -n) // 符号反転(元に戻す)
            .toArray();   // 配列化

        // 結果出力
        System.out.println(java.util.Arrays.toString(arr));
        // 結果：[14, 6, 5, 4, 4, 3, 2, -2, -5]になった！成功！
    }
}

問題があるとすれば、符号反転できない数値。つまりInteger.MIN_VALUEが含まれている場合。理論で説明した通り、数学上は問題ないが、プログラムである以上、数値の上限下限が存在し、変換できない数値があることは注意が必要

Stream<Integer>とどちらが速い？

降順ソートする速度として、以下はどちらが速いのか検証

• よく見かけるStream<Integer>に変換して行う
• 本記事のIntStreamのまま行う

下のプログラムをそれぞれ10回ずつ実行して、かかった時間をt検定する

/** 
 * Stream<Integer>に変換してComparatorを使って降順ソート
 */
class Main1 {
    public static void main(String[] args) {
        // 計測開始
        long start = System.currentTimeMillis();

        int[] arr = java.util.stream.IntStream.range(0, 50000000)
            .boxed().sorted(java.util.Comparator.reverseOrder())
            .mapToInt(Integer::valueOf).toArray();

        // 計測完了
        long end = System.currentTimeMillis();
        System.out.println("かかった時間:" + (end - start) + "[msec]");
    }
}

/** 
 * IntStreamのまま降順ソート
 */
class Main {
    public static void main(String[] args) {
        // 計測開始
        long start = System.currentTimeMillis();

        int[] arr = java.util.stream.IntStream.range(0, 50000000)
            .map(n -> -n).sorted().map(n -> -n).toArray();

        // 計測完了
        long end = System.currentTimeMillis();
        System.out.println("かかった時間:" + (end - start) + "[msec]");
    }
}

結果は

試行回数$n$	Stream<integer>に変換[msec]	IntStreamのまま[msec]
1	2678	418
2	2603	375
3	2613	391
4	2593	371
5	2612	371
6	2593	379
7	2525	377
8	2553	369
9	2524	392
10	2563	423

明らかに「IntStreamの方が速い」で結論が出る結果となったが、

Rでもt検定して統計的にも速くなっていることを示しておく(片側検定、優位水準5%)

帰無仮説：IntStreamとStream<Integer>では速度に差はない
対立仮説：IntStreamの方が速い

> # IntStreamの速度
> x1 =c(418,375,391,371,371,379,377,369,392,423)

> # Stream<Integer>変換型の速度
> x2 = c(2678,2603,2613,2593,2612,2593,2525,2553,2524,2563)

> t.test(x1, x2, alternative="less")

        Welch Two Sample t-test

data:  x1 and x2
t = -137.93, df = 12.089, p-value < 2.2e-16
alternative hypothesis: true difference in means is less than 0
95 percent confidence interval:
      -Inf -2170.701
sample estimates:
mean of x mean of y 
    386.6    2585.7

p値は0.05未満なので、帰無仮説は棄却され、
「IntStreamの方が速い」といえる
やっぱり、Integerクラスに変換して、また戻すって処理分遅いんだろうね(^^;)