はじめに
もうすぐDart 1.9がリースされるので、新規に正式サポートされるGeneratorを使ってフィボナッチ数列を生成してみました。
Dartの最新仕様ECMA-408 2nd EditionのGeneratorには同期版(sync*
~yield
)と、非同期版(async*
~yield
~await
)が有ります。
ここではDart 1.9でサポート予定の同期版です。
なお、実行確認は現時点のDev版、version:1.9.0-dev.8.0 (Thu Feb 12 03:13:11 2015) on "windows_x64"、ビルド番号43715で行っています。
実装
フィボナッチ数列生成関数(同期Generator版)
Try Dart!にはフィボナッチ数を再帰計算で求めるサンプルがありますが、ここではフィボナッチ数列を求めます。
一つ前ともう一つ前の値を覚えておいてループの中で足し算するのが素直ですね。
Iterable<int> fibo() sync* {
int lastBut1 = 0;
int last = 1;
int ret;
yield lastBut1;
yield last;
while (true) {
ret = lastBut1 + last;
lastBut1 = last;
last = ret;
yield ret;
}
}
ポイントはItarable
、sync*
とyield
です。
コールサイトIterable
for
...in
版
次にGenerator関数を呼び出す側です。
まずはシンプルにIterableならではのfor
...in
版です。
const COUNT = 100;
void main() {
int i = 0;
for (int f in fibo()) {
print("fibo($i) = $f");
i++;
if (i >= COUNT) break;
}
}
せっかくのfor
...in
ですが、無限数列なのでループカウンタを導入して適当なところでbreak
しています。
ちゃんとIterable
として扱えました。
Iterator
版
次はIterator版です。
終了条件にループカウンタが必要なので、これはこれで素直かもしれません。
Iterator itr = fibo().iterator;
for (int i = 0; itr.moveNext() && i < COUNT; i++) {
print("fibo($i) = ${itr.current}");
}
ところで、DartにC言語でいうところのカンマ演算子は無いんですね。
ということで、Iterator
の初期化はfor
文の外で行っています。
他方で、moveNext()
はfalse
返したらそれがループ終了条件なので、お作法としてfor
文の中、継続条件のところで実行しています。
今回のmoveNext()
は永久にtrue
ですけどね。
Iteratable
関数パイプライン版
次はIteratable
に戻って、関数パイプラインで実現してみます。
無限数列なのでなんとかして止めなければいけません。
takeWhile()
というフィルタ関数でIterable
を切り詰めると良いようです。
int i = 0;
fibo().takeWhile((_) => i < COUNT).forEach((f) {
print("fibo($i) = $f");
i++;
});
DartはクロージャをサポートするのでtakeWhile()
、forEach()
内でもループカウンタが参照できてます。
Iteratable関数パイプライン版2
何番目のフィボナッチ数かを表示しなくて良いならば、ループカウンタを省いてずっと簡単に書けます。
fibo().take(COUNT).forEach((f) => print("fibo = $f"));
実は、というか当然ながら、take()
内部にはカウンタがあります。
それでも、アプリ側で気にする必要がないのが利点です。
感想
やっぱ速いですね。
Try Dart!の再帰版フィボナッチ数計算プログラムと比べると圧倒的に速いです(体感ですが)。
もっとも、Try Dart!はO(N²)、本プログラムはO(N)なので比較するのも何ですが。
また、fibo()
が本質的にループする処理でありながら、ループ終了条件や、得られた値をループ内で利用する処理(今回はprint()
のみ)を分離して、純粋にフィボナッチ数列を求める処理として実装できるのは、やはり素晴らしい。
おわりに (次は非同期版だ)
非同期版がサポートされた時点でまた紹介します。
今回のデジャブを体験することになりそうです。