JavaScriptだと function*
で宣言して yield
で値を返すジェネレータ。これは何が便利なのか解説します。
JavaScriptで説明していきますが、最後に見るようにPython, Rubyでもジェネレータは使えます。
ジェネレータとは?
例:自然数を無限に生成するジェネレータ
function* createNaturalNumberGenerator() {
let n = 1;
while (true) {
yield n;
n += 1;
}
}
const generator = createNaturalNumberGenerator();
console.log(generator.next().value);
console.log(generator.next().value);
console.log(generator.next().value);
console.log(generator.next().value);
console.log(generator.next().value);
1
2
3
4
5
-
function*
で定義される関数のことをジェネレータ関数といい、 - ジェネレータ関数が返す値、つまり変数
generator
の値のことをジェネレータと言います
for ... of
を使って呼び出すと、ジェネレータから値がなくなるまでループします。
function* createNaturalNumberGenerator() {
let i = 1;
while (true) {
yield i;
i += 1;
}
}
const generator = createNaturalNumberGenerator();
for (let n of generator) {
console.log(n);
}
と言っても自然数の場合は無限にあるので、無限に続きます。
1
2
3
4
5
...(無限につづく)
[ポイント]
createNaturalNumberGenerator
の中で無限ループしているけど、この関数が永久に戻らないわけではなく、next()
を呼ぶごと、あるいはfor ...of
で1回ループを回るごとに1回yield
が呼ばれて呼び出し元に戻っていることに注意してください。
そんなのクラスやクロージャでもできるよ
はい、確かにできます。
クラスを使う版
class NaturalNumberGenerator {
constructor() {
this.n = 0;
}
get() {
this.n += 1;
return this.n;
}
}
const g = new NaturalNumberGenerator();
console.log(g.get());
console.log(g.get());
console.log(g.get());
console.log(g.get());
しかし、この場合this.n
という今どこまで進んだかという状態を自分で管理しなければならないことになります。
ジェネレータ関数を使うと、状態を自分で管理しなくて済むようになります。
まだ何のことか分からないと思いますので、次に具体的にメリットが分かる例を出します。
組み合わせ(nCr)を出力する関数(非ジェネレータ)
function getCombinations(xs, r) {
if (xs.length < r) {
return [];
}
if (r == 1) {
const result = [];
for (let x of xs) {
result.push([x]);
}
return result;
}
const x = xs[0];
const xs_ = xs.slice(1);
return getCombinations(xs_, r - 1).map(comb => [x, ...comb]).concat(getCombinations(xs_, r));
}
console.log(getCombinations([1, 2, 3, 4], 2));
[ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ], [ 3, 4 ] ]
- 中で自分自身を2回呼び出している2重再帰
- パスカルの三角形を素直にアルゴリズム化したのがこの実装
-
自分自身を1回しか呼び出さない実装もあり、そっちの方が効率はいいけど、こっちの方が発想は素直かと
-
問題点
- 入力が大きくなると結果の配列が大きくなり、メモリを圧迫する
-
50C10 == 10272278170
(102億!) - 試しにさっきのプログラムでやってみると返ってこないです
ジェネレータなら
- さっきの関数とアルゴリズムは同じで、ジェネレータで書き換えたもの
function* createCombinationGenerator(xs, r) {
if (xs.length < r) {
return;
}
if (r == 1) {
for (let x of xs) {
yield [x];
}
return;
}
const x = xs[0];
const xs_ = xs.slice(1);
for (let comb of createCombinationGenerator(xs_, r - 1)) {
yield [x, ...comb];
}
for (let comb of createCombinationGenerator(xs_, r)) {
yield comb;
}
}
const xs = [];
for (let i = 0; i < 50; i++) {
xs.push(i + 1);
}
const generator = createCombinationGenerator(xs, 10);
for (let comb of generator) {
console.log(comb);
}
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 11 ]
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 12 ]
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 13 ]
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 14 ]
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 15 ]
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 16 ]
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 17 ]
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 18 ]
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 19 ]
...(相当な時間がかかるが、順次結果を出力する)
- 結果を保存しておく配列を考えなくてもよくなるので、コーディングも楽になります(この手の処理はしばしば配列の配列の配列とか出てきてややこしくなるので)
ジェネレータはどう実装されているのか?
不思議に思いませんでしたか?どう実装されているのか。
Node.jsの場合
How does yield actually pause/resume the flow of a generator? : javascript
- Node.jsではC++内でスタックフレームを保存・復元しているらしい
- (C言語レベルのスタックフレームではなく、JavaScriptのスタックフレーム)
BabelでES5に変換する場合
BabelでES5に変換できるのだから、C++で書かれたインタープリタ自体がサポートしていなくても実装できるはず。
Babalは有限状態機械に変換するらしい。
(変換されたコードを読もうとしてもメッチャ分かりづらい)
"use strict";
var _marked =
/*#__PURE__*/
regeneratorRuntime.mark(createNaturalNumberGenerator);
function createNaturalNumberGenerator() {
var i;
return regeneratorRuntime.wrap(function createNaturalNumberGenerator$(_context) {
while (1) {
switch (_context.prev = _context.next) {
case 0:
i = 1;
case 1:
if (!true) {
_context.next = 7;
break;
}
_context.next = 4;
return i;
case 4:
i += 1;
_context.next = 1;
break;
case 7:
case "end":
return _context.stop();
}
}
}, _marked);
}
var generator = createNaturalNumberGenerator();
console.log(generator.next().value);
console.log(generator.next().value);
console.log(generator.next().value);
console.log(generator.next().value);
console.log(generator.next().value);
async/awaitも実はジェネレータで実装されている
…らしい。
自分でジェネレータを使ってasync/awaitを実装することもできます。
ES6 Generatorを使ってasync/awaitを実装するメモ - maru source
PythonやRubyにもジェネレータはある
Python
def generate_natural_numbers():
n = 1
while True:
yield n
n += 1
for i in generate_natural_numbers():
print(i)
Ruby
generator = Enumerator.new {|yielder|
n = 1
loop do
yielder.yield n
n += 1
end
}
generator.each do |n|
puts n
end
まとめ
- ジェネレータを使うと、巨大な組み合わせや探索をする再帰関数が効率的に書ける。楽に書ける