Java: RecursiveTask

Java 7 の RecursiveTask でフィボナッチ数列なサンプル。

import java.util.concurrent.RecursiveTask;
import java.util.concurrent.ForkJoinTask;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.ExecutionException;

public class Fibonacci {
  public static void main(String[] args) {
    ForkJoinPool fjpool = new ForkJoinPool();
    ForkJoinTask<Long> f = new FibonacciTask(40);
    long start = System.currentTimeMillis();
    fjpool.execute(f);
    try {
      System.out.println(f.get());
    } catch (InterruptedException | ExecutionException e) { }
    long end = System.currentTimeMillis();
    System.out.println((end - start) +"msec");
  }
}

class FibonacciTask extends RecursiveTask<Long> {
  private final long n;
  FibonacciTask(long n) {
    this.n = n;
  }
  protected Long compute() {
    if (n <= 1) {
      return n;
    }
    FibonacciTask f1 = new FibonacciTask(n - 1);
    FibonacciTask f2 = new FibonacciTask(n - 2);
    f1.fork();
    return f2.compute() + f1.join();
  }
}
// EOF

再帰を使ったサンプル

public class Recursive {
  public static void main(String[] args) {
    Recursive a = new Recursive();
    long start = System.currentTimeMillis();
    System.out.println(a.recursive(40));
    long end = System.currentTimeMillis();
    System.out.println((end - start) +"msec");
  }

  protected long recursive(int n) {
    if (n <= 1) {
      return n;
    }
    return recursive(n - 1) + recursive(n - 2);
  }
}
// EOF

もう一つおまけ。メモ化再帰

public class Recursive2 {
  public static void main(String[] args) {
    Recursive2 c = new Recursive2(40);
    long start = System.currentTimeMillis();
    System.out.println(c.recursive());
    long end = System.currentTimeMillis();
    System.out.println((end - start) +"msec");
  }

  int len;
  long[] calc;    // 結果格納用
  protected Recursive2(int n) {
    len = n;
    calc = new long[len+1];
    calc[0] = 0;
    calc[1] = 1;
    for (int i = 2; i < calc.length; i++) {
      calc[i] = -1;
    }
  }
  protected long recursive() {
    return recursive(len);
  }
  protected long recursive(int n) {
    if (n <= 1) {
      return n;
    }
    if (n < len && calc[n] != -1) {
      return calc[n];
    }
    int result = recursive(n - 2) + recursive(n - 1);
    if (n < len) {
      calc[n] = result;
    }
    return result;
  }
}
// EOF

実行時間
CPU: Core 2 Duo E8400
OS: Windows XP Professional SP3 x86
MEM: 4GByte

> java Fibonacci
102334155
9234msec

> java Recursive
102334155
1219msec

> java Recursive2
102334155
0msec