5.10 ジェネレータ、イテレータ

フィボナッチ数列のように無限に続く数列や漸化式を扱うとき、より多くの数列を取り出そうとすると、プログラムの書き方によっては、計算量や使用メモリ量が膨大になる。
JavaScript（ES6以降）では、こうした長大な数列を効率的に扱うことができるジェネレータとイテレータという機能が備わっている。

サンプル・プログラム

ダウンロード

圧縮ファイルの内容
Fibonacci1.html	サンプル・プログラム(1)
Fibonacci2.html	サンプル・プログラム(2)
Fibonacci3.html	サンプル・プログラム(3)
Fibonacci4.html	サンプル・プログラム(4)

フィボナッチ数列

フィボナッチ数列は、イタリアの数学者レオナルド・フィボナッチ（1170年頃～1250年頃）にちなんで名付けられた数列で、次の漸化式で表すことができる。
\[ \displaystyle
\left\{\begin{array}{ll}
F_0 = 0 \\
F_1 = 1 \\
F_{n+2} = F_n + F_{n+1} \quad (n \ge 1)
\end{array}\right. \]
フィボナッチ数列は、なぜか自然界によくあらわれる。たとえば、ヒマワリの種の並びや巻き貝の巻き方がフィボナッチ数列にしたがっていることが分かっている。美術で習う黄金比とも関係する。また、大学入試の数学で出題されることがあり、覚えている方も多いだろう。

forループでフィボナッチ数列を求める

Fibonacci1.html を実行

  38: /**
  39:  * フィボナッチ数列を求める（forループ版）
  40:  * @param   Number n 求めたい数列の長さ
  41:  * @return  なし
  42: */
  43: function fibonacci1(n) {
  44:     let fibList = [0, 1];       //初期値
  45:     for (let i = 2; i < COUNT; i++) {
  46:         fibList[i] = fibList[i - 2] + fibList[i - 1];
  47:         Num++;
  48:     }
  49:     return fibList;
  50: }

  65:     //フィボナッチ数列を表示する．
  66:     let str = '';
  67:     fibList = fibonacci1(COUNT);
  68:     for (let i = 0; i < COUNT; i++) {
  69:         if (i > 0)  str += ', ';
  70:         str += fibList[i];
  71:     }
  72:     document.getElementById('fibonacci').innerHTML = str;
  73:     document.getElementById('num').innerHTML = '計算回数 = ' + Num;

フィボナッチ数列の漸化式を forループを使って実装したものがユーザー関数 fibonacci1 である。求めたい数列の長さを引数として渡し、フィボナッチ数列を配列で返す。
20個のフィボナッチ数列を計算するのに18回の計算で済むが、数列をいちいち配列に格納するのでメモリ消費量が多くなるのと、メインプログラム側で再び forループを回して表示用のテキストを生成してやる手間がかかる。

再帰でフィボナッチ数列を求める

Fibonacci2.html を実行

  38: /**
  39:  * フィボナッチ数列を求める（再帰関数版）
  40:  * @param   Number i 求めたい数列の順番
  41:  * @return  なし
  42: */
  43: function fibonacci2(i) {
  44:     let fib;
  45:     switch (i) {
  46:         case 0:
  47:             fib = 0;
  48:             break;
  49:         case 1:
  50:             fib = 1;
  51:             break;
  52:         default:
  53:             fib = fibonacci2(i - 1) + fibonacci2(i - 2);
  54:             break;
  55:     }
  56:     Num++;
  57:     return fib;
  58: }

  73:     //フィボナッチ数列を表示する．
  74:     let str = '';
  75:     for (let i = 0; i < COUNT; i++) {
  76:         if (i > 0)  str += ', ';
  77:         str += fibonacci2(i);
  78:     }
  79:     document.getElementById('fibonacci').innerHTML = str;
  80:     document.getElementById('num').innerHTML = '計算回数 = ' + Num;

フィボナッチ数列は漸化式で定義されているので、「4.5 再帰」で学んだ手法を使って解くことができる。これがユーザー関数 fibonacci2 である。求めたい数列の順番を指定してやれば、いちいち配列に格納することなくフィボナッチ数を取り出すことができる。
ところが（当然のことだが）、いちいち再帰を回すために計算回数は35,400回という非効率な結果になってしまった。

ジェネレータ関数でフィボナッチ数列を求める

Fibonacci3.html を実行

  38: /**
  39:  * フィボナッチ数列を求めるジェネレータ関数
  40:  * @param   なし
  41:  * @return  なし
  42: */
  43: function* fibonacci3() {
  44:     let a = 0, b = 1;   //初期値
  45:     while (true) {
  46:         yield a;
  47:         [a, b] = [b, a + b];
  48:         Num++;
  49:     }
  50: }

  65:     //フィボナッチ数列を表示する．
  66:     let fib = fibonacci3();
  67:     let str = '';
  68:     for (let i = 0; i < COUNT; i++) {
  69:         if (i > 0)  str += ', ';
  70:         str += fib.next().value;
  71:     }
  72:     document.getElementById('fibonacci').innerHTML = str;
  73:     document.getElementById('num').innerHTML = '計算回数 = ' + Num;

ここでジェネレータ関数の出番である。
ジェネレータ関数は、処理を途中で抜け出したり、途中から復帰することができる特殊な関数で、JavaScriptでは function* で定義し、"let fib = fibonacci3();" のように Generatorオブジェクトを介して呼び出す。
基本構造は

function* name(param) {
yield a;
return b;
}

のようになっており、Generatorオブジェクトの nextメソッドを実行する都度、yieldキーワードのある場所で処理を中断／復帰し、オブジェクト "{value: 値, done: false}" を返す。
処理が最後まで終わると、returnでオブジェクト "{value: 値, done: true}" を返す。

ジェネレーター関数 fibonacci3 の場合、whileループが無限ループに陥っているように見えるが、これはフィボナッチ数列が無限にあることをそのまま表しており、実際には、nextメソッドを呼び出すたびに、ループが1回ずつ回るようになっている。
結果的に計算回数は19回となり、表示のために回している forループだけで、余計な配列も必要としないし、再帰による余計な計算も行わなくて済む。

イテレータを生成しフィボナッチ数列を求める

Fibonacci4.html を実行

  38: /**
  39:  * フィボナッチ数列を求めるイテレータ生成関数
  40:  * @param   Number start 開始番号（省略時：0）
  41:  * @param   Number goal  終了番号（省略時：Infinity）
  42:  * @param   Number step  刻み幅（省略時：1）
  43:  * @return  Object {value:値, done:終了かどうか}
  44: */
  45: function fibonacci4(start = 0, goal = Infinity, step = 1) {
  46:     let nextIndex = start;
  47:     let a = 0, b = 1;   //初期値
  48:
  49:     //イテレータオブジェクトを定義する．
  50:     const rangeIterator = {
  51:         //nextメソッドを定義する．
  52:         next: function () {
  53:             let result;
  54:             if (nextIndex < goal) {
  55:                 result = { value: a, done: false };
  56:                 [a, b] = [b, a + b];
  57:                 nextIndex += step;
  58:                 Num++;
  59:                 return result;
  60:             }
  61:             return { value: a, done: true };
  62:         },
  63:     };
  64:     return rangeIterator;
  65: }

  80:     //フィボナッチ数列を表示する．
  81:     let fib = fibonacci4();
  82:     let str = '';
  83:     for (let i = 0; i < COUNT; i++) {
  84:         if (i > 0)  str += ', ';
  85:         str += fib.next().value;
  86:     }
  87:     document.getElementById('fibonacci').innerHTML = str;
  88:     document.getElementById('num').innerHTML = '計算回数 = ' + Num;

上述のジェネレータ関数 fibonacci3 の nextメソッドはどこから出てきたのだろうか。
JavaScript（ES6以降）では、value と done という2つのプロパティを持ったオブジェクトを返す nextメソッドを持ったオブジェクトをイテレータと呼ぶ。
ジェネレータ関数 fibonacci3 を生成するイテレータが fibonacci である。ジェネレータ関数に比べると記述が冗長になっており、その分、細かい制御が可能であるが、フィボナッチ数列のように反復処理したいだけであればゲネレータ関数を使ったほうが簡明であろう。