Java8 Streamではクイックソートが書けない

java java8

タイトルは釣りです。
もちろん、汎用ライブラリなので、Streamを使ってクイックソートが書けないわけではありません。
ただ、Streamで完結したままではクイックソートは書けません。Listとの相互変換が必要です。


で、Streamで完結したままクイックソートが書けない直接的要因はいくつかあって、それを解消するユーティリティメソッドが用意されてれば、この件に関してはStreamで完結することもできるのですが、だからといってさまざま出てくる「xxxが書けない」を解決するためのユーティリティメソッドを追加しまくれば幸せになれるかというと、そうでもないわけです。
そもそも、なんでそんなユーティリティメソッドが必要になるのかというのが本題。


結局のところListなどCollectionと、新たに追加されたStreamが別扱いになっているところに原因があって、CollectionとStreamの変換がいろいろ必要になってコードがめんどくさくなるのが問題です。
たとえば、クイックソートの中での、ピボットよりも小さいリストを得るコードをStreamを使って書くと次のようになります。

list.stream().skip(1).filter(i -> i < pivot)
    .collect(toList()))

もしここでListをそのままStreamとして、StreamをそのままCollectionとして扱うことができれば、.stream()メソッドや、.collect(toList())メソッドは不要になって、コードは次のようにすっきりします

list.skip(1).filter(i -> i < pivot)


結局現状では、Listを結合するメソッドがないとかStreamオブジェクトを別の用途に使いまわせないとかStream結合のconcatが引数２つしかとらないというのがかさなって、クイックソートは次のようになってしまいます。

public static List<Integer> quickSort(List<Integer> list){
    return list.size() <= 1 ? list :
        concat(
            concat(
                quickSort(list.stream().skip(1).filter(i -> i < list.get(0))
                        .collect(toList())).stream(),
                list.stream().limit(1)),
            quickSort(list.stream().skip(1).filter(i -> i >= list.get(0))
                    .collect(toList())).stream()).collect(toList());
}


もし、ListとStreamが同じように扱えれば、つまり、stream()とcollect(toList())を取り除ければ、次のようになります。

public static List<Integer> quickSort(List<Integer> list){
    return list.size() <= 1 ? list :
        concat(
            concat(
                quickSort(list.skip(1).filter(i -> i < list.get(0))),
                list.limit(1)),
            quickSort(list.skip(1).filter(i -> i >= list.get(0))));
}

concatがかぶってしまうのがかっこ悪いとしても、クイックソートに必要な操作だけが記述できています。


もうひとつ、Streamをややこしくしているものがあります。基本型とラップクラスの扱いです。
数値を扱う基本型に関しては、専用のStreamが用意されています。また、関数型インタフェースも、数値の基本型を引数にとるものが専用で用意されています。まずこの使い分けが面倒です。
また、基本型を扱うStreamと汎用Streamの相互変換も必要になってきます。
クイックソートを試すためのランダムな数列を作るコードは次のようになります。

List<Integer> zeroToTen = IntStream.range(0, 15)
    .boxed()
    .collect(Collectors.toList());
Collections.shuffle(zeroToTen);

IntStreamという基本型intを扱うためのStreamから、汎用のStreamに変換するためのboxed()メソッドが必要になっています。


もしListとStreamが同一に扱えて、基本型とラップクラスの違いを気にする必要がなければ、次のようになります。

List<Integer> zeroToTen = IntStream.range(0, 15);
Collections.shuffle(zeroToTen);


Java2SE5.0からのオートボクシング・アンボクシングのおかげで、intとIntegerの違いはnullを扱えるかどうかとGenericsに指定できるかどうかだけ、くらいに単純化して使うこともできていたわけですが、Streamやラムダのおかげで使い分けを気にする必要が大きくなってしまいました。


ぼくら高度に訓練されたJavaプログラマにとって、setXxx/getXxxのコードや匿名クラスnew Hoge(){void foo(){〜}}の記述は視界にまったく入らなかったのと同様に、stream()やcollect(toList())は視界に入らなくなっていくと思われるので全く問題ないわけですが、基本型とラップクラスの扱いに関しては使い分けが必要になるので、そのたびに頭を悩まされることになり、少し問題です。


とりあえず、クイックソートのコードです。

import static java.util.Collections.shuffle;
import java.util.List;
import static java.util.stream.Collectors.toList;
import static java.util.stream.IntStream.range;
import static java.util.stream.Stream.concat;

public class QS2 {
    public static void main(String... args){
        List<Integer> zeroToTen = range(0, 15)
            .boxed()
            .collect(toList());
        shuffle(zeroToTen);
        System.out.println(zeroToTen);
        System.out.println(quickSort(zeroToTen));
    }
    
    public static List<Integer> quickSort(List<Integer> list){
        return list.size() <= 1 ? list :
            concat(
                concat(
                    quickSort(list.stream().skip(1).filter(i -> i < list.get(0))
                            .collect(toList())).stream(),
                    list.stream().limit(1)),
                quickSort(list.stream().skip(1).filter(i -> i >= list.get(0))
                        .collect(toList())).stream()).collect(toList());
    }
}