M.Hiroi's Home Page

Java Programming

続・お気楽 Java プログラミング入門

[ PrevPage | Java | NextPage ]

immutable な遅延ストリーム (後編)

●zipWith()

遅延ストリームを操作する場合、2 つの遅延ストリームを受け取るマップ関数があると便利です。関数型言語 Haskell では、この処理を zipWith() と呼んでいます。プログラムは次のようになります。

リスト : マップ関数 zipWith()

  public static <T, U, V> LazyStream<V> zipWith(BiFunction<? super T, ? super U, ? extends V> func, LazyStream<T> xs, LazyStream<U> ys) {
    if (xs.isEmpty() || ys.isEmpty())
      return nil();
    else
      return cons(func.apply(xs.first(), ys.first()), () -> zipWith(func, xs.rest(), ys.rest()));
  }

今回は zipWith() をスタティックメソッドとして定義しました。遅延ストリーム xs と ys からそれぞれの要素を取り出してメソッド func に渡します。そして、その返り値を遅延ストリームに格納して返します。どちらかの遅延ストリームが空になった場合は空の遅延ストリームを返します。これで有限と無限どちらの遅延ストリームにも対応することができます。

簡単な実行例を示しましょう。

jshell> import immutable.LazyStream

jshell> var xs = LazyStream.iota(1, 10)
xs ==> immutable.LazyStream@1a86f2f1

jshell> var ys = LazyStream.iota(11, 20)
ys ==> immutable.LazyStream@506c589e

jshell> var zs = LazyStream.iterate(1, x -> x + 1)
zs ==> immutable.LazyStream@4b85612c

jshell> LazyStream.zipWith((x, y) -> x * y, xs, ys).take(10)
$5 ==> [11, 24, 39, 56, 75, 96, 119, 144, 171, 200]

jshell> LazyStream.zipWith((x, y) -> x * y, xs, zs).take(10)
$6 ==> [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

jshell> LazyStream.zipWith((x, y) -> x * y, zs, ys).take(10)
$7 ==> [11, 24, 39, 56, 75, 96, 119, 144, 171, 200]

jshell> LazyStream.zipWith((x, y) -> x * y, zs, zs).take(20)
$8 ==> [1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400]

zipWith() を使うと、遅延ストリームに対していろいろな処理を定義することができます。次の例を見てください。

リスト : zipWith() の例 (2)

import immutable.LazyStream;
import static immutable.LazyStream.*;

public class sample191 {
  static LazyStream<Integer> addStream(LazyStream<Integer> xs, LazyStream<Integer> ys) {
    return zipWith((x, y) -> x + y, xs, ys);
  }
  
  static LazyStream<Integer> ones = repeat(1);
  static LazyStream<Integer> ints;
  static LazyStream<Integer> fibo;
  static {
    ints = cons(1, () -> addStream(ones, ints));
    fibo = cons(0, () -> cons(1, () -> addStream(fibo.rest(), fibo)));
  }
  
  public static void main(String[] args) {
    System.out.println(ints.take(20));
    System.out.println(fibo.take(20));
  }
}
$ javac sample191.java
$ java sample191
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]

addStream() は xs と ys の要素を加算した遅延ストリームを返します。この addStream() を使うと、整数を生成する遅延ストリーム ints やフィボナッチ数列を生成する遅延ストリーム fibo を定義することができます。

遅延ストリーム ints は、現在の ints に 1 を足し算することで整数を生成しています。fibo は現在のフィボナッチ数列を表していて、fibo.rest() で次の要素を求め、それらを足し算することで、その次の要素を求めています。この場合、ストリームの初期値として 2 つの要素が必要になることに注意してください。

なお、スタティック変数 ints と fibo は代入演算子 (=) で初期値を指定すると、右辺式に自分自身 (ints や fibo) が含まれるためコンパイルエラーになります。このため、ints と fobo の初期化には「スタティックイニシャライザ (静的初期化子)」を使っています。

static { 初期化処理; ... }

クラスの中で static を付けたブロックを定義すると、そのクラスを最初に利用したときに、その中の処理が一度だけ実行されます。

●遅延ストリームの併合

次は、要素を昇順に出力する 2 つの遅延ストリームを併合 (マージ: merge) するメソッドを作りましょう。次のリストを見てください。

リスト : 遅延ストリームのマージ

  public static <E extends Comparable<E>> LazyStream<E> merge(LazyStream<E> xs, LazyStream<E> ys) {
    if (xs == NIL) {
      return ys;
    } else if (ys == NIL) {
      return xs;
    } else {
      E x = xs.first();
      E y = ys.first();
      int r = x.compareTo(y);
      if (r <= 0)
        return cons(x, () -> merge(xs.rest(), ys));
      else
        return cons(y, () -> merge(xs, ys.rest()));
    }
  }

スタティックメソッド merge() は 2 つの遅延ストリームを併合して新しい遅延ストリームを返します。基本的には連結リストのメソッド mergeList() と同じです。xs が空であれば ys を返し、ys が空ならば xs を返します。そうでなければ、遅延ストリームの先頭要素を取り出して変数 x, y にセットします。x <= y ならば x を、そうでなければ y を遅延ストリームに格納します。

簡単な実行例を示しましょう。

jshell> var xs = LazyStream.iterate(1, x -> x + 2)
xs ==> immutable.LazyStream@3eb07fd3

jshell> var ys = LazyStream.iterate(0, x -> x + 2)
ys ==> immutable.LazyStream@446cdf90

jshell> LazyStream.merge(xs, ys).take(20)
$4 ==> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

jshell> LazyStream.merge(xs, xs).take(20)
$5 ==> [1, 1, 3, 3, 5, 5, 7, 7, 9, 9, 11, 11, 13, 13, 15, 15, 17, 17, 19, 19]

●集合演算

ここで、遅延ストリームには重複要素が存在せず、要素は昇順に出力されることを前提にすると、遅延ストリームでも集合演算を行うことができます。次のリストを見てください。

リスト : 集合演算

  // 和集合
  public static <E extends Comparable<E>> LazyStream<E> union(LazyStream<E> xs, LazyStream<E> ys) {
    if (xs == NIL) {
      return ys;
    } else if (ys == NIL) {
      return xs;
    } else {
      E x = xs.first();
      E y = ys.first();
      int r = x.compareTo(y);
      if (r < 0)
        return cons(x, () -> union(xs.rest(), ys));
      else if (r > 0)
        return cons(y, () -> union(xs, ys.rest()));
      else
        return cons(x, () -> union(xs.rest(), ys.rest()));
    }
  }

  // 積集合
  public static <E extends Comparable<E>> LazyStream<E> intersection(LazyStream<E> xs, LazyStream<E> ys) {
    if (xs == NIL) {
      return nil();
    } else if (ys == NIL) {
      return nil();
    } else {
      while (true) {
        E x = xs.first();
        E y = ys.first();
        int r = x.compareTo(y);
        if (r == 0) {
          LazyStream<E> xs1 = xs;
          LazyStream<E> ys1 = ys;
          return cons(x, () -> intersection(xs1.rest(), ys1.rest()));
        } else if (r < 0) {
          xs = xs.dropWhile(x1 -> x1.compareTo(y) < 0);
        } else {
          ys = ys.dropWhile(y1 -> x.compareTo(y1) > 0);
        }
      }
    }
  }

スタティックメソッド union() は xs と ys から要素を取り出して、小さいほうを遅延ストリームに追加します。等しい場合は x だけを追加します。このとき、xs と ys の両方から先頭要素を取り除くことに注意してください。

スタティックメソッド intersection() はちょっと複雑です。xs, ys から先頭要素を取り出して、変数 x, y にセットします。x と y が等しい場合は、その要素を遅延ストリームに追加します。x が y よりも小さい場合、dropWhile() で xs から y よりも小さい要素を取り除きます。逆に、x が y よりも大きい場合は ys から x よりも小さい要素を取り除きます。あとは while ループで同じ処理を繰り返すだけです。

簡単な実行例を示しましょう。

jshell> var xs = LazyStream.iterate(1L, x -> x + 1)
xs ==> immutable.LazyStream@67424e82

jshell> var triangular = xs.map(x -> x * (x + 1) / 2)
triangular ==> immutable.LazyStream@579bb367

jshell> var square = xs.map(x -> x * x)
square ==> immutable.LazyStream@41906a77

jshell> triangular.take(20)
$9 ==> [1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210]

jshell> square.take(20)
$10 ==> [1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400]

jshell> LazyStream.union(triangular, square).take(20)
$11 ==> [1, 3, 4, 6, 9, 10, 15, 16, 21, 25, 28, 36, 45, 49, 55, 64, 66, 78, 81, 91]

jshell> LazyStream.intersection(triangular, square).take(7)
$12 ==> [1, 36, 1225, 41616, 1413721, 48024900, 1631432881]

遅延ストリーム triangular は「三角数」、square は「四角数」を表します。これらの遅延ストリームを union() でまとめると、三角数または四角数の数列になります。intersection() でまとめると、三角数かつ四角数の数列 (平方三角数) になります。なお、平方三角数は拙作のページ Puzzle DE Progamming 多角数 でも取り上げています。興味のある方はお読みくださいませ。

●ハミングの問題

次は「ハミングの問題」を解いてみましょう。

[ハミングの問題]

7 以上の素数で割り切れない正の整数を小さい順に N 個求めよ

参考文献 : 奥村晴彦,『C言語による最新アルゴリズム事典』, 技術評論社, 1991 (361 ページより引用)

7 以上の素数で割り切れない正の整数は、素因子が 2, 3, 5 しかない自然数のことで、これを「ハミング数 (Hamming Numbers)」といいます。ハミング数は素因数分解したとき、\(2^i \times 3^j \times 5^k \ (i, j, k \geq 0)\) の形式になります。たとえば、100 以下のハミング数は次のようになります。

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 
54, 60, 64, 72, 75, 80, 81, 90, 96, 100

遅延ストリームを使うと「ハミングの問題」は簡単に解くことができます。小さい順にハミング数を出力する遅延ストリームを hs としましょう。hs は 1 から始まるので次のように定義できます。

hs = cons(1, () -> ...);

最初の要素は 1 なので、それに 2, 3, 5 を掛け算した値 (2, 3, 5) もハミング数になります。これらの値は hs.map(x -> x * 2), hs.map(x -> x * 3), hs.map(x -> x * 5) で生成することができます。あとは、これらの遅延ストリームをひとつにまとめて、小さい順に出力する遅延ストリームを作ればいいわけです。hs の定義は次のようになります。

hs = cons(1, () -> union(union(hs.map(x -> x * 2), hs.map(x -> x * 3)), hs.map(x -> x * 5)));

プログラムは次のようになります。

リスト : ハミングの問題

import immutable.LazyStream;

public class hamming {
  static LazyStream<Long> union(LazyStream<Long> xs, LazyStream<Long> ys) {
    return LazyStream.union(xs, ys);
  }
  
  static LazyStream<Long> hs;
  static {
    hs = LazyStream.cons(1L, () -> union(union(hs.map(x -> x * 2), hs.map(x -> x * 3)), hs.map(x -> x * 5)));
  }

  public static void main(String[] args) {
    System.out.println(hs.take(100));
  }
}

LazyStrem.union() を直接呼び出すとコンパイルエラーになったので、スタティックメソッド union() を定義しました。実行結果を示します。

$ javac hamming.java
$ java hamming
[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45,
 48, 50, 54, 60, 64, 72, 75, 80, 81, 90, 96, 100, 108, 120, 125, 128, 135, 144,
150, 160, 162, 180, 192, 200, 216, 225, 240, 243, 250, 256, 270, 288, 300, 320,
324, 360, 375, 384, 400, 405, 432, 450, 480, 486, 500, 512, 540, 576, 600, 625,
640, 648, 675, 720, 729, 750, 768, 800, 810, 864, 900, 960, 972, 1000, 1024, 1080, 
1125, 1152, 1200, 1215, 1250, 1280, 1296, 1350, 1440, 1458, 1500, 1536]

●順列の生成

異なる n 個の順列の総数は、n の階乗 (n!) だけあります。たとえば、3 つの整数 1, 2, 3 の順列は次に示すように 6 通りあります。

(1 2 3), (1 3 2), (2 1 3), (2 3 1), (3 1 2), (3 2 1)

順列を生成するプログラムは再帰定義で簡単に作ることができます。(1 2 3) の順列を生成する場合、最初に 1 で始まる順列を生成します。これは 1 を取り除いた数字 (2 3) の順列を生成することで実現できます。次は 2 で始まる順列を生成します。同様に、2 を取り除いた数字 (1 3) の順列を生成すればいいわけです。(2 3) や (1 3) の順列を生成する場合も同じように考えることができます。

●要素の選択

それではプログラムを作りましょう。最初に、連結リスト ImList<E> から要素を一つ選んで、選んだ要素と残りの要素を返すメソッド select() を作ります。次のリストを見てください。

リスト : 要素の選択

import immutable.ImList;
import immutable.Pair;
import immutable.LazyStream;
import static immutable.LazyStream.*;

public class sample192 {
  static <E> LazyStream<Pair<E, ImList<E>>> select(ImList<E> xs) {
    if (xs.rest().isEmpty())
      return cons(Pair.pair(xs.first(), ImList.nil()), () -> nil());
    else
      return cons(Pair.pair(xs.first(), xs.rest()),
                  () -> select(xs.rest()).map(p -> Pair.pair(p.getFst(), ImList.cons(xs.first(), p.getSnd()))));
  }

  public static void main(String[] args) {
    var xs = select(ImList.iota(1, 4));
    xs.forEach(System.out::println);
  }
}

select() は選んだ要素と残りの要素を Pair に格納し、それを遅延ストリームに格納して返します。最初に、リスト xs の要素が一つしかない場合は (xs.first(), ImList.nil()) を遅延ストリームに格納します。そうでなければ、(xs.first(), xs.rest()) を遅延ストリームに格納し、第 2 引数のラムダ式の中で残りの要素を選びます。

ラムダ式の中では select(xs.rest()) を実行して、残りの要素を一つ選びます。返り値は遅延ストリームなので、map() で要素 (Pair) を順番に取り出して、Pair の第 2 要素のリストに xs.first() を追加します。Pair は immutable なので値を書き換えることはできません。新しい Pair を生成していることに注意してください。これで、リスト xs から要素を順番に選ぶことができます。

それでは実行してみましょう。

$ javac sample192.java
$ java sample192
(1, (2 3 4))
(2, (1 3 4))
(3, (1 2 4))
(4, (1 2 3))

●プログラムの作成

select() を使うと順列を生成するメソッド permutations() は簡単にプログラムすることができます。次のリストを見てください。

リスト : 順列の生成

import immutable.ImList;
import immutable.Pair;
import immutable.LazyStream;
import static immutable.LazyStream.*;

public class sample193 {
  //
  // select() は省略
  //

  static <E> LazyStream<ImList<E>> permutations(ImList<E> xs) {
    if (xs.isEmpty())
      return cons(ImList.nil(), () -> nil());
    else
      return select(xs).flatMap(p -> permutations(p.getSnd()).map(ys -> ImList.cons(p.getFst(), ys)));
  }
  
  public static void main(String[] args) {
    var ys = permutations(ImList.iota(1, 4));
    ys.forEach(System.out::println);
  }
}

メソッド permutations() は引数のリスト xs から順列を生成し、それを遅延ストリームに格納して返します。引数が空リストの場合、空リストを遅延ストリームに格納します。このリストに対して要素を追加していきます。

xs が空リストでなければ select() で要素を一つ選びます。flatMap() のラムダ式の引数 p は Pair です。p.getSnd() で残りのリストを取り出し、permutations() でその順列を生成します。そして、その返り値を map() で取り出して、先頭に選択した要素 p.getFst() を追加すれば順列を生成することができます。

それでは実行してみましょう。

$ javac sample193.java
$ java sample193
(1 2 3 4)
(1 2 4 3)
(1 3 2 4)
(1 3 4 2)
(1 4 2 3)
(1 4 3 2)
(2 1 3 4)
(2 1 4 3)
(2 3 1 4)
(2 3 4 1)
(2 4 1 3)
(2 4 3 1)
(3 1 2 4)
(3 1 4 2)
(3 2 1 4)
(3 2 4 1)
(3 4 1 2)
(3 4 2 1)
(4 1 2 3)
(4 1 3 2)
(4 2 1 3)
(4 2 3 1)
(4 3 1 2)
(4 3 2 1)

●select() を使わない方法

順列は select() を使わなくてもプログラムを作ることができます。次のリストを見てください。

リスト : 順列の生成 (2)

import immutable.ImList;
import immutable.LazyStream;
import static immutable.LazyStream.*;

public class sample194 {
  static <E> LazyStream<ImList<E>> permutations(ImList<E> xs) {
    if (xs.isEmpty())
      return cons(ImList.nil(), () -> nil());
    else
      return of(xs).flatMap(x -> permutations(xs.filter(y -> !x.equals(y))).map(z -> ImList.cons(x, z)));
  }

  public static void main(String[] args) {
    var perm = permutations(ImList.iota(1, 4));
    perm.forEach(System.out::println);
  }
}

要素の選択は of(xs).flatMap() で行います。この場合、連結リスト xs の要素を先頭から順番に選択することになります。ラムダ式の中で permutations() を呼び出すとき、リスト xs から選んだ要素 x を filter() で削除します。これで x を取り除いたリストの順列を生成することができます。あとは map() でリスト z の先頭に x を追加していくだけです。

●組み合わせの生成

次は「組み合わせ (combination)」を生成するプログラムを作ってみましょう。たとえば、リスト (1 2 3 4 5) の中から 3 個を選ぶ組み合わせは次のようになります。

(1 2 3), (1 2 4), (1 2 5), (1 3 4), (1 3 5), (1 4 5)
(2 3 4), (2 3 5), (2 4 5), (3 4 5)

最初に 1 を選択した場合、次は (2 3 4 5) の中から 2 個を選べばいいですね。2 番目に 2 を選択したら、次は (3 4 5) の中から 1 個を選べばいいわけです。これで、(1 2 3), (1 2 4), (1 2 5) が生成されます。(2 3 4 5) の中から 2 個選ぶとき、2 を選ばない場合があります。この場合は (3 4 5) の中から 2 個を選べばいいわけです。ここで 3 を選ぶと (1 3 4), (1 3 5) が生成できます。同様に、3 を除いた (4 5) の中から 2 個をえらぶと (1 4 5) を生成することができます。

これで 1 を含む組み合わせを生成したので、次は 1 を含まない組み合わせ、つまり (2 3 4 5) から 3 個を選ぶ組み合わせを生成すればいいわけです。けっきょく、この処理の考え方は次に示す組み合わせの公式と同じです。

\( {}_n \mathrm{C}_r = \begin{cases} 1 & if \ r = 0 \\ 1 & if \ r = n \\ {}_{n-1} \mathrm{C}_{r-1} + {}_{n-1} \mathrm{C}_r \quad & if \ r \gt 0 \end{cases} \tag{3} \)

これをプログラムすると次のようになります。

リスト : 組み合わせの生成

import immutable.ImList;
import immutable.Delay;
import immutable.LazyStream;
import static immutable.LazyStream.*;

public class sample195 {
  static <E> LazyStream<ImList<E>> combinations(int n, ImList<E> xs) {
    if (n == 0)
      return cons(ImList.nil(), () -> nil());
    else if (xs.length() == n)
      return cons(xs, () -> nil());
    else
      return combinations(n - 1, xs.rest()).map(ys -> ImList.cons(xs.first(), ys))
             .lazyAppend(Delay.delay(() -> combinations(n, xs.rest())));
  }

  public static void main(String[] args) {
    var xs = combinations(3, ImList.iota(1, 5));
    xs.forEach(System.out::println);
  }
}

combinations() の第 1 引数が選択する要素の個数、第 2 引数が要素を格納したリストです。n が 0 の場合、選択する要素がないので空リストを格納した遅延ストリームを返します。n と xs.length() が等しい場合は、その要素を全て選択するので xs を格納した遅延ストリームを返します。

そうでなければ、先頭要素 xs.first() を選びます。残りのリスト xs.rest() から n - 1 個を選ぶ組み合わせを combinations() で求め、その先頭に xs.first() を追加します。あとは、xs.rest() から n 個を選ぶ組み合わせを combinations() で求め、lazyAppend() で連結するだけです。

それでは実行してみましょう。

$ javac sample195.java
$ java sample195
(1 2 3)
(1 2 4)
(1 2 5)
(1 3 4)
(1 3 5)
(1 4 5)
(2 3 4)
(2 3 5)
(2 4 5)
(3 4 5)

正常に動作していますね。

●組 (Pair) を生成する遅延ストリーム

次は、2 つのストリームからその要素の組み合わせを生成するストリームを作りましょう。要素が n 個のストリームの場合、組み合わせは n * n 個あります。次の図を見てください。

(a0, b0) (a0, b1) (a0, b2) ... (a0, bn)
(a1, b0) (a1, b1) (a1, b2) ... (a1, bn)
(a2, b0) (a2, b1) (a2, b2) ... (a2, bn)

                           ...

(an, b0) (an, b1) (an, b2) ... (an, bn)


        図 : n * n 個の組

これは「直積集合」を求めることと同じです。プログラムは次のようになります。

リスト : 組の生成 (1)

import immutable.Pair;
import immutable.LazyStream;
import static immutable.LazyStream.*;

public class sample196 {
  static <T, U> LazyStream<Pair<T, U>> pairStream(LazyStream<T> xs, LazyStream<U> ys) {
    return xs.flatMap(x -> ys.map(y -> Pair.pair(x, y)));
  }

  public static void main(String[] args) {
    var ps1 = pairStream(iota(1, 4), iota(5, 8));
    System.out.println(ps1.take(16));
    var ps2 = pairStream(iterate(1, x -> x + 1), iterate(5, x -> x + 1));
    System.out.println(ps2.take(16));
  }
}

メソッド pairStream() はとても簡単ですが、実は問題点があるのです。実際に実行してみましょう。

$ javac sample196.java
$ java sample196
[(1, 5), (1, 6), (1, 7), (1, 8), (2, 5), (2, 6), (2, 7), (2, 8), (3, 5), (3, 6),
 (3, 7), (3, 8), (4, 5), (4, 6), (4, 7), (4, 8)]
[(1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (1, 10), (1, 11), (1, 12), (1, 13), 
 (1, 14), (1, 15), (1, 16), (1, 17), (1, 18), (1, 19), (1, 20)]

有限の遅延ストリームであれば問題ありませんが、無限ストリームの要素で組を作る場合、Pair の第 1 要素は 1 しか出力されません。そこで、下図に示すように、対角線上に組を生成していくことにします。

   | a0  a1  a2  a3  a4  a5
---+-----------------------------
b0 | 0   1   3   6   10  15  ...
   |
b1 | 2   4   7   11  16  ...
   |
b2 | 5   8   12  17  ...
   |
b3 | 9   13  18  ...
   |
b4 | 14  19  ...
   |
b5 | 20 ...
   |
   | ...
   |


図 : 無限ストリームによる組の生成

図を見ればおわかりのように、対角線の要素数を n とすると、組は (an-1, b0), (an-2, b1), ..., (a1, bn-2), (a0, bn-1) となっています。これは、xs から n 個の要素を取り出したリストと、ys から n 個の要素を取り出して反転したリストを zip でまとめた形になっています。プログラムは次のようになります。

リスト : 組の生成 (2)

import java.util.List;
import immutable.Pair;
import immutable.Delay;
import immutable.ImList;
import immutable.LazyStream;
import static immutable.LazyStream.*;

public class sample197 {
  static <T, U> ImList<Pair<T, U>> makePair(List<T> xs, List<U> ys) {
    ImList<Pair<T, U>> zs = ImList.nil();
    for (int i = 0; i < ys.size(); i++) {
      int j = ys.size() - 1 - i;
      zs = ImList.cons(Pair.pair(xs.get(j), ys.get(i)), zs);
    }
    return zs;
  }
  
  static <T, U> LazyStream<Pair<T, U>> makePairStream(int n, LazyStream<T> xs, LazyStream<U> ys) {
    var zs = makePair(xs.take(n), ys.take(n));
    return of(zs).lazyAppend(Delay.delay(() -> makePairStream(n + 1, xs, ys)));
  }
  
  static <T, U> LazyStream<Pair<T, U>> pairStream(LazyStream<T> xs, LazyStream<U> ys) {
    return makePairStream(1, xs, ys);
  }

  public static void main(String[] args) {
    var xs = iterate(1, x -> x + 1);
    var ps = pairStream(xs, xs);
    System.out.println(ps.take(50));
  }
}

実際の処理はメソッド makePairStream() で行っています。引数 n が対角線上の要素数を表します。take() で xs と ys から要素を取り出し、それをメソッド makePair() に渡して組を作成します。このリストを of() で遅延ストリームに変換します。これで無限リストに対応することができます。

それでは実行してみましょう。

$ javac sample197.java
$ java sample197
[(1, 1), (1, 2), (2, 1), (1, 3), (2, 2), (3, 1), (1, 4), (2, 3), (3, 2), (4, 1),
 (1, 5), (2, 4), (3, 3), (4, 2), (5, 1), (1, 6), (2, 5), (3, 4), (4, 3), (5, 2),
 (6, 1), (1, 7), (2, 6), (3, 5), (4, 4), (5, 3), (6, 2), (7, 1), (1, 8), (2, 7),
 (3, 6), (4, 5), (5, 4), (6, 3), (7, 2), (8, 1), (1, 9), (2, 8), (3, 7), (4, 6),
 (5, 5), (6, 4), (7, 3), (8, 2), (9, 1), (1, 10), (2, 9), (3, 8), (4, 7), (5, 6)]

正常に動作していますね。

●エラトステネスの篩

最後に、遅延ストリームを使って素数を求めるプログラムを作ってみましょう。考え方は簡単です。最初に、2 から始まる整数列を生成する遅延ストリームを用意します。2 は素数なので、素数ストリームの要素になります。次に、この整数列から 2 で割り切れる整数を取り除き除きます。これは filter() を使うと簡単です。

2 で割り切れる整数が取り除かれたので、次の要素は 3 になります。今度は 3 で割り切れる整数を取り除けばいいのです。これも filter() を使えば簡単です。このとき、入力用の遅延ストリームは 2 で割り切れる整数が取り除かれています。したがって、この遅延ストリームに対して 3 で割り切れる整数を取り除くように filter() を設定すればいいわけです。

このように、素数を見つけたらそれで割り切れる整数を取り除いていくアルゴリズムを「エラトステネスの篩」といいます。ようするに、2 から始まる整数ストリームに対して、見つけた素数 2, 3, 5, 7, 11, ... を順番に filter() で設定して素数でない整数をふるい落としていくわけです。

プログラムは次のようになります。

jshell> LazyStream<Integer> sieve(LazyStream s) {
   ...>     int p = s.first();
   ...>     return LazyStream.cons(p, () -> sieve(s.rest().filter(x -> x % p != 0)));
   ...> }
|  次を作成しました: メソッド sieve(LazyStream)

jshell> var ps = sieve(LazyStream.iterate(2, x -> x + 1))
ps ==> immutable.LazyStream@799f7e29

jshell> ps.take(25)
$4 ==> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

jshell> ps.take(50)
$5 ==> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 
101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 
211, 223, 227, 229]

jshell> ps.take(100)
$6 ==> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 
101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 
211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 
337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 
461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541]

sieve() には 2 から始まる整数列を生成する遅延ストリームを渡します。ラムダ式で sieve() を呼び出すとき、filter() により整数列から 2 で割り切れる整数を取り除いた遅延ストリームが渡されます。次の要素 3 を取り出すとき、この遅延ストリームに対して 3 で割り切れる整数を取り除くことになるので、2 と 3 で割り切れる整数が取り除かれることになります。

次の要素は 5 になりますが、その遅延ストリームからさらに 5 で割り切れる整数が filter() で取り除かれることになります。このように filter() が設定されていくことで、素数でない整数をふるい落としていくことができるわけです。

●sieve() の高速化

メソッド sieve() は簡単にプログラムできますが、生成する素数の個数が多くなると、その実行速度はかなり遅くなります。実をいうと、sieve() なみに簡単で sieve() よりも高速な方法があります。

整数 n が素数か確かめる簡単な方法は、\(\sqrt n\) 以下の素数で割り切れるか試してみることです。割り切れる素数 m があれば、n は素数ではありません。そうでなければ、n は素数であることがわかります。

これをそのままプログラムすると次のようになります。

リスト : 素数の生成 (2)

import immutable.LazyStream;
import static immutable.LazyStream.*;

public class sievelazy {
  static LazyStream<Integer> sieve(LazyStream<Integer> s) {
    int p = s.first();
    return cons(p, () -> sieve(s.rest().filter(x -> x % p != 0)));
  }
  
  // 高速化
  static LazyStream<Integer> primes =
    cons(2, () -> cons(3, () -> cons(5, () -> primesFrom(7))));

  static int nextPrime(int n) {
    while (true) {
      var ps = primes;
      while (true) {
        int p = ps.first();
        if (p * p > n) return n;
        if (n % p == 0) break;
        ps = ps.rest();
      }
      n += 2;
    }
  }

  static LazyStream<Integer> primesFrom(int n) {
    int p = nextPrime(n);
    return cons(p, () -> primesFrom(p + 2));
  }

  public static void main(String[] args) {
    var ps = sieve(iterate(2, x -> x + 1));
    long start = System.currentTimeMillis();
    System.out.println(ps.get(3000));
    long end = System.currentTimeMillis();
    System.out.println((end - start)  + "ms");
    start = System.currentTimeMillis();
    System.out.println(primes.get(3000));
    end = System.currentTimeMillis();
    System.out.println((end - start)  + "ms");
  }
}

変数 primes に素数列を生成する遅延ストリームをセットします。実際に素数を生成する処理はメソッド primesFrom() で行います。primesFrom() は簡単で、メソッド nextPrime() を呼び出して n 以上で最小の素数を求め、それを遅延ストリームに追加します。偶数は素数ではないので、引数 n には奇数を与えていることに注意してください。

nextPrime() も簡単です。\(\sqrt n\) 以下の素数は生成済みなので、while ループで primes から素数を順番に first() で取り出して変数 p にセットします。p が \(\sqrt n\) よりも大きければ n を返します。ここでは \(\sqrt n\) のかわりに条件を p * p <= n としています。n が素数 p で割り切れれば、break で内側の while ループを脱出して次の数 (n + 2) を調べます。

それでは実行してみましょう。get() で 3001 番目の素数を求めてみました。

$ javac sievelazy.java
$ java sievelazy
27457
1275ms
27457
8ms

実行環境 : Ubunts 18.04 (WSL), Intel Core i5-6200U 2.30GHz

sieve() よりも primes のほうが高速になりました。興味のある方はいろいろ試してみてください。


初版 2016 年 12 月 18 日
改訂 2021 年 2 月 28 日

Copyright (C) 2016-2021 Makoto Hiroi
All rights reserved.

[ PrevPage | Java | NextPage ]