素数列生成プログラムでCode Kata、あるいはJava8 Stream APIの勉強

Code Kataというのがありますが、指慣らしとか、反復練習として、自分にとって新しい言語やライブラリの使い方の習得に、お決まりのお題でプログラミングをしています。ボーリングのスコア計算とか、ソートを知ってる限りのアルゴリズムで書くとか、スタックやキューをTDDで書くんですね。

Java8のストリームAPIをそろそろ押さえておきたいと思って、素数列を生成するプログラムを書きました。

public int[] declarative(int end) {
    return IntStream
        .range(2, end)
        .filter(x -> x < 4 
            ? true 
            : IntStream.rangeClosed(2, (int) Math.sqrt(x))
                .allMatch(y -> x % y != 0))
        .toArray();
}

上記の実装は、1で割り切れることはわかっているので1では割らないとか、xの平方根まで試せばいいからショートカットしてますが、おおむね素数の定義に近いものです。
それに対してエラトステネスのふるいを実装してみようと思ったんですが、あれれ、java.util.Streamにはfoldあるいはreduceがない...scalaだとこういう感じですか。

def eratosthenesWithImmutableBitSet(end: Int): Array[Int] = {
  val sieved = Range.inclusive(2, math.sqrt(end).toInt)
    .foldLeft(immutable.BitSet.empty)((sieved, x) =>
      if (sieved(x)) sieved
      else Range(x + x, end, x).foldLeft(sieved)(_ + _))
  Range(2, end).filter(!sieved(_)).toArray
}

でもこれ実行するとさすがに遅い。教条的にやるとこうなんですが、BitSetを毎回生成するのは重いんですね。
で、Javaに戻ってAPIドキュメントを読み返してみるとcollectってメソッドがあって、

このストリームの要素に対して可変リダクション操作を実行します。可変リダクションとは、リデュース対象の値がArrayListのような可変の結果コンテナであり、結果を置き換えるかわりに結果の状態を更新することによって要素が組み込まれるようなリダクションのことです。

http://docs.oracle.com/javase/jp/8/api/java/util/stream/Stream.html

だそうです。ああ、リダクションの結果は可変(mutable)って考えるんですね。mutableでいいならscalaで書くとこういう感じで、

def eratosthenesWithMutableBitSet(end: Int): Array[Int] = {
  val sieved = Range.inclusive(2, math.sqrt(end).toInt)
    .foldLeft(mutable.BitSet.empty)((sieved, x) =>
      if (sieved(x)) sieved
      else Range(x + x, end, x).foldLeft(sieved)(_ += _))
  Range(2, end).filter(!sieved(_)).toArray
}

すごい早くなります。
で、Javaで書くと、

public static int[] pipelineEratosthenes(int end) {
    if (end <= 2) {
        return new int[0];
    }
    BitSet bits = IntStream.rangeClosed(2, (int) Math.sqrt(end)).collect(
        () -> new BitSet(end),
        (sieved, x) -> {
            if (!sieved.get(x)) {
                IntStream.rangeClosed(2, end / x).map(y -> y * x)
                    .forEach(sieved::set);
            }}, 
        (x, y) -> {
            x.and(y);
        });
    bits.flip(0);
    bits.clear(0, 2);
    return bits.stream().toArray();
}

こんな感じでしょうか。単にfoldしたいだけなんですが、Javaは大げさになりますね。定義域を分割して並列処理してもいいようにアルゴリズムを考えるのが基本みたいですね。

というようなことをここ二週間くらいで勉強しました。