Java 8： Supplier を使った遅延評価で「たらい回し関数」を書いてみる

『ふつうの Haskellプログラミング』って本の５．３章、遅延評価について説明している部分で、「たらい回し関数」が紹介されている。

こんなコード。

main = print (tarai 20 10 5)

tarai :: Int -> Int -> Int -> Int
tarai x y z = if x <= y then y
                        else tarai (tarai (x-1) y z)
                                   (tarai (y-1) z x)
                                   (tarai (z-1) x y)

で実行時間は、Java コードでは約１３秒かかっているのに対し、遅延評価によって必要最小限の計算しかやらない Haskell では 0.002 秒と、6千倍以上速くなっている。

今回は、これを Java 8で試してみたい。


まず、上記 Haskell コードをそっくり置き換えた、オーソドックスなスタイルのタライ回し。

  static int tarai(int x, int y, int z) {
    return x <= y ? y : tarai(tarai(x - 1, y, z),
                              tarai(y - 1, z, x),
                              tarai(z - 1, x, y));
  }

Haskell と違って、不要な計算も全部評価してしまう。うちのマシンでは、だいたい４秒かかった。

以下が遅延評価的な手法を取り入れたバージョン。

  static IntSupplier taraiLazy(int x, int y, int z) {
    return tarai(() -> x, () -> y, () -> z);
  }
  static IntSupplier tarai(
      IntSupplier x, IntSupplier y, IntSupplier z) {
    return () -> { 
      int yv = y.getAsInt();
      return x.getAsInt() <= yv
             ? yv 
             : tarai(tarai(() -> x.getAsInt() - 1, y, z),
                     tarai(() -> y.getAsInt() - 1, z, x),
                     tarai(() -> z.getAsInt() - 1, x, y)).getAsInt();
    };
  }

ここでは Java 8 の IntSupplier を使ってみた。
これは、保持している値がプリミティブの int である、Supplier の特殊な形のクラス。

こんな感じで比較してみた。

  public static void main(final String[] args) {
    measureTimeElapsed(() -> tarai(20, 10, 5));
    measureTimeElapsed(taraiLazy(20, 10, 5));
  }
  public static void measureTimeElapsed(IntSupplier s) {
    long start = System.currentTimeMillis();

    System.out.printf("計算結果:%d, 経過時間:%.3f秒%n",
      s.getAsInt(),
      (System.currentTimeMillis() - start) / 1000.0);
  }

結果は以下

  [java] 計算結果:20, 経過時間:4.389秒
  [java] 計算結果:20, 経過時間:0.004秒

６千倍とまでは行かないが、千倍くらいにはなっている。

まあ言語レベルで遅延評価になったわけでもなく、やろうと思えば Java 7 以前でもできた事ではあるけど、こういう遅延評価っぽいアプローチが少しだけ簡単になったのは、まあ良いことだとは思う。