DartのGeneratorでフィボナッチ数列 (非同期版)

はじめに

Dart 1.9のリースを目前にして、Dev版にて非同期版のgeneratorがサポートされました。
DartのGeneratorでフィボナッチ数列 (同期版)で約束した通り非同期版を紹介します。

なお、実行確認はversion:1.9.0-dev.10.2 (Thu Mar 05 09:49:17 2015) on "windows_x64"、ビルド番号44260で行っています。

実装

フィボナッチ数列生成関数(非同期Generator版)

Try Dart!にはフィボナッチ数を再帰計算で求めるサンプルがありますが、ここではフィボナッチ数列を求めます。
一つ前ともう一つ前の値を覚えておいてループの中で足し算するのが素直ですね。

import "dart:async";

Stream<int> fibo() async* {
  int lastBut1 = 0;
  int last = 1;
  int ret;

  yield lastBut1;
  yield last;

  while(true){
    ret = lastBut1 + last;
    lastBut1 = last;
    last = ret;
    yield ret;
  }
}

ポイントはimport "dart:async";、Stream、async*とyieldです。

コールサイトStream async for...in版

次にGenerator関数を呼び出す側です。
まずはシンプルにStreamならではのawait for...in版です。

const COUNT = 10;

main() async {
  int i = 0;
  await for(int f in fibo()){
    print("fibo($i) = $f");
    i++;
    if(i >= COUNT) break;
  }
}

せっかくのfor...inですが、無限数列なのでループカウンタを導入して適当なところでbreakしています。
ちゃんとStreamとして扱えました。

なお、mainはvoidとすると怒られます。
Future<void>とすると、やはり怒られます。( ´∀｀)
FutureやFuture<dynamic>とすれば良いのですが、ここでは省略して暗黙的にdynamicにしています。

StreamIterator版

次はStreamIterator版です。
終了条件にループカウンタが必要なので、これはこれで素直かもしれません。

  StreamIterator itr = new StreamIterator(fibo());
  for(int i = 0; await itr.moveNext() && i < COUNT ; i++){
    print("fibo($i) = ${itr.current}");
  }

DartにはC言語でいうところのカンマ演算子が無いので、StreamIteratorの初期化はfor文の外で行っています。
また、StreamからgetterでStreamIteratorが取り出せないので、Streamを引数にStreamIteratorをコンストラクトしています。

他方で、moveNext()はfalse返したらそれがループ終了条件なので、お作法としてfor文の中、継続条件のところで実行しています。
今回もmoveNext()は永久にtrueですけどね。

Stream関数パイプライン版

次はStreamに戻って、関数パイプラインで実現してみます。
無限数列なのでなんとかして止めなければいけません。
takeWhile()というフィルタ関数でStreamIterableを切り詰めると良いようです。

  int i = 0;
  fibo().takeWhile((_) => i < COUNT).forEach((f){
    print("fibo($i) = $f");
    i++;
  });

DartはクロージャをサポートするのでtakeWhile()、forEach()内でもループカウンタが参照できてます。

Stream関数パイプライン版2

何番目のフィボナッチ数かを表示しなくて良いならば、ループカウンタを省いてずっと簡単に書けます。

  fibo().take(COUNT).forEach((f) => print("fibo = $f"));

実は、というか当然ながら、take()内部にはカウンタがあります。
それでも、アプリ側で気にする必要がないのが利点です。

感想

やっぱ速いですね。
Try Dart!の再帰版フィボナッチ数計算プログラムと比べると圧倒的に速いです(体感ですが)。
もっとも、Try Dart!はO(N²)、本プログラムはO(N)なので比較するのも何ですが。

同期版と比べても、全く遜色が無いスピードで実行されました。

また、fibo()が本質的にループする処理でありながら、ループ終了条件や、得られた値をループ内で利用する処理(今回はprint()のみ)を分離して、純粋にフィボナッチ数列を求める処理として実装できるのは、やはり素晴らしい。

おわりに

これでStreamのプログラミングがコールバックのネストやチェーン無しに、同期処理的に記述できるようになりました。
DartのGeneratorでフィボナッチ数列 (同期版)と比較してもらえれば分かりますが、コードはほとんど同じです。
ライバル言語よりちょっと早い実装ですね。