コラム

CTC教育サービス・ホーム　＞　コラム　＞　スーパーエンジニアの独り言　＞　第22回　ノッティングヒルの恋人

スーパーエンジニアの独り言

CTC 教育サービス

[IT研修]注目キーワード Python UiPath(RPA) 最新技術動向 Microsoft Azure Docker Kubernetes

第22回　ノッティングヒルの恋人 2013年4月

　レオナルドと云えば、「レオ様」ことレオナルド・ディカプリオ、もしくは、「万能人」と称される本物の天才レオナルド・ダ・ヴィンチを思い出されるのでしょうが、今回は残念ながら別のレオナルドです。
　レオナルド・フィボナッチ登場で算盤の書からフィボナッチ数列の巻です。
　フィボナッチ数列（Fibonacci sequence）とは「兎の問題」です。

「1つがいの兎がいます。兎は1ヶ月経つと大人になり、その1ヶ月後（産まれてから2ヶ月後)には、1つがいの兎を産むとします。（しかも、どの兎も死ぬことはないという前提の場合に）兎は1年後には幾つのつがいになっているのか？」

　1ヶ月目、最初のつがいが1。
　2ヶ月目、最初のつがいが大人になり1のまま。
　3ヶ月目、最初のつがいが子供を産み 1 + 1 = 2 に増えます。
　4ヶ月目、2 + 1 = 3。5ヶ月目、3 + 2 = 5。と続きます。

　この問題を解くのには、単純に反復で導くことができます。
　また処理が再帰的であるため再帰呼び出しで解を導くことも自然です。
　ここでは再帰呼び出しを並列的な処理で行うことを試してみましょう。
　Java 7で追加された Fork/Joinフレームワークをご紹介します。
（モデルはUNIXのfork/exit/waitと同じ構造とお考えください。）

|　// File: Fibonacci.java
|　import java.util.concurrent.RecursiveTask;
|　import java.util.concurrent.ForkJoinPool;
|　import java.util.Scanner;
|
|　public class Fibonacci extends RecursiveTask {
|　　private final long n;
|
|　　Fibonacci(long n) { this.n = n; }
|
|　　@Override
|　　protected Long compute() {
|　　　if (n <= 1L) return n;
|
|　　　Fibonacci f1 = new Fibonacci(n - 1L);
|　　　f1.fork();
|　　　Fibonacci f2 = new Fibonacci(n - 2L);
|　　　return f2.compute() + f1.join();
|　　}
|
|　　public static void main(String[] args) {
|　　　System.out.print("Please Input Number : ");
|　　　Scanner sc = new Scanner(System.in);
|　　　long n = sc.nextLong();
|
|　　　ForkJoinPool forkJoin = new ForkJoinPool();
|　　　long fn = forkJoin.invoke(new Fibonacci(n));
|　　　System.out.println("\nFibonacci : n = " + n + "; Fn = " + fn);
|　　}
|　}

　Java 5で追加された並行処理のためのjava.util.concurrentパッケージに細かい粒度で並列性を増したFork/Joinフレームワークが Java 7から登場しました。大量の計算を小さく分けてマルチスレッド処理をしようという戦略で、これを分割統治法（Divide and Conquer Algorithm）と呼びます。
　いかつい名前ですが、問題を小さく分割して最終的に解決しようとする方法はとても自然です。
　加えてフレームワーク内部ではWork Stealingという方策で最小限のコストで適切にタスクを分配できる実装が為されています。これによりマルチコアCPUを効率的に稼動させる事が出来るのです。

　Fork/Joinフレームワークの使い方は、ForkJoinTaskのサブクラスである抽象クラスRecursiveTask（またはRecursiveAction）を継承した実装クラスを用意します。例示の様にRecursiveTaskはjoinの際に返り値が必要な場合、不要な場合にはRecursiveActionを選択し、computeをオーバーライドして処理を実装します。ForkJoinPoolクラスからinvoke（submit、execute）で実行し結果を受け取ります（但し、executeは結果を受け取りません）。

　フィボナッチ数列は単に再帰的に足し算するだけの単純な計算のため今回は恩恵を享受できない上にオーバーヘッドのコストが上回ります。
　筆者の非力なマシンでは、数値を増やすと目に見えて遅くなりました。
　むしろシンプルな線形アルゴリズムを使えば高速に実行できるでしょう。
　しかしながら、再帰すべき計算処理が複雑で且つ、多数のコアを有する場合に「コア数を意識することなく記述が可能」で、しかもコア数が増える程に飛躍的に処理速度が向上することでしょう（並列度は指定可能）。つまりメニーコア時代の潤沢な計算資源を有効活用する光明かもしれません。

　現在から少しだけ未来の話になりますが、Java 8リリースではFork/JoinフレームワークにParallelArray（並列処理のためのコレクション）が登場して内部イテレータで容易に並列化できる記述が検討されています。
　同じくJava 8に持ち越しされたProject Lambdaでラムダ式（クロージャー）が登場し、並列化での冗長な記述を排除し簡潔に表現出来ると期待されます。

　アルゴリズムの題材として初等数学のフィボナッチ数を取りあげました。
　フィボナッチは神秘的な数列で植物の花弁や葉の数、または巻き貝と一致するのが散見されます。フィボナッチは自然界とリンクしています。
　また幾何学的にもフィボナッチ数列の各項を一辺とする正方形を描き、その一辺の中点から対面する角への斜線を半径とした円弧を辺の延長線上まで描き、それを繰り返していくと黄金螺旋（フィボナッチ・スパイラル）なる綺麗な図形が紡ぎ出されます（Sybase社のロゴに使われていました）。
　隣り合う正方形一辺の比率は1:1.618（近似値）で黄金比率に収束します。
　最も美しいとされる比率です。やはり花弁と同じ比率を美しいと感じ取る人間こそがまさに自然の一部なのだと強く感じます。

　筆者は数学が苦手ではありますが、プログラムの基本ですので初歩的なことだけでも勉強しようかなと少し思っています。

　では次回もお楽しみに。