フィボナッチ数列を逐次、並行処理してみた

Java7 Goldの勉強してて、並行処理の分野で「Fork/Join Framework」を試したくなったのでちょっと実装
お題はフィボナッチ数列を逐次/並行で計算すると、どのくらい差が出るのか
javaで書くから逐次と平行じゃ結構差が出るのでは。と予想

　重要キーワード

結構よくわからいキーワード出てきたのでちょっとまとめ

1. Fork/Join Frameworkとは
Java7から導入された軽い並行処理が容易にできるフレームワーク
Java5からあるExecutorsでいいんじゃね？って考え方もあるが
各処理が小さい場合はExecutorsだと無駄が多いらしい
Java7からは重い処理は今まで通りExecutors、軽い並列処理はFock/Joinでしてね。ってこと
今回は、このFock/Joinフレームワークを使って、並列、逐次処理の処理速度の差を見てく


2. フィボナッチ数列とは
ひまわりの種の並び、木の枝の伸び、松ぼっくりの羽の並びなどなど..
自然界あるあるの有名な数列
プログラムだと再起関数とかの一例でよく出てくる
式で書くとこんな感じ。※ただし、$a_0$を考慮する場合は$a_0=0$
\[ \left\{ \begin{array} _a_1=1,a_2=1 & \\ a_{n+2}=a_{n+1} + a_n & \end{array} \right. \]

　実装

まずはタスククラスから
コンストラクタで指定した数字がフィボナッチ数列の第N項
このタスクでは第N項のフィボナッチ数を求める
ロジック的には、再起関数で求める時と同じ。関数じゃなくスレッドを量産して計算していく
22,23行目がミソ
j1.join()とはj1.fork()で実行されてる非同期処理が終わるのを待ち、結果を返すメソッド
j2.compute()は現在のスレッドでcompute()を呼んでるだけ
だから、
joinを第一項に持ってくると、非同期にしてるのに処理が終わるまで待つ　　　⇒ 逐次処理
joinを第二項に持ってくると、現在のスレッドと、非同期スレッドが同時に動く⇒ 平行処理
となり、逐次と平行を分けることができる

次にメイン文
タスクはForkJoinPoolクラスにより管理される
ForkJoinPool# invoke(task)　によりタスクの実行し、結果を返す。
今回はその前後に時間を測るようにして、計算時間を求めた。

　結果

めっちゃ差が出たｗｗ
20倍も差ができるとは思わなかった

　余談

ちなみに、フィボナッチ数列は一般項が求められる数列
だから回りくどいやり方をせずに、一撃で計算できる
一般項は三項間漸化式の解き方を知ってるちょろい
求め方を簡単に書くと \[ \left\{ \begin{array} _a_1=1,a_2=1 & \\ a_{n+2}=a_{n+1} + a_n & \end{array} \right. \] 上記式の特性方程式を解く \[ x^2=x+1 \Longrightarrow x=\frac{1\pm\sqrt{5}}{2} \] よって、漸化式は下記に変換できる \[ a_{n+2}-\frac{1\mp\sqrt{5}}{2}a_{n+1}=\frac{1\pm\sqrt{5}}{2}\Bigl( a_{n+1} -\frac{1\mp\sqrt{5}}{2}a_n\Bigr) \\ \] $a_{n+1}-\frac{1\pm\sqrt{5}}{2}a_n$を一つの数列として、整理する \[ a_{n+1}-\frac{1-\sqrt{5}}{2}a_n=\Bigl(\frac{1+\sqrt{5}}{2}\Bigr)^{n-1}\Bigl(a_2-\frac{1-\sqrt{5}}{2}a_1\Bigr) = \Bigl(\frac{1+\sqrt{5}}{2}\Bigr)^n \\ a_{n+1}-\frac{1+\sqrt{5}}{2}a_n=\Bigl(\frac{1-\sqrt{5}}{2}\Bigr)^{n-1}\Bigl(a_2-\frac{1+\sqrt{5}}{2}a_1\Bigr) = \Bigl(\frac{1-\sqrt{5}}{2}\Bigr)^n \] 差をとると、一般頂は \[ a_n= \frac{1}{\sqrt{5}} \biggl\{ \Bigl( \frac{1 + \sqrt{5}} {2} \Bigr)^n -\Bigl( \frac{1 - \sqrt{5}} {2} \Bigr)^n \biggr\} \] これを使て計算する
結果は 早すぎワロタ