JavaScriptで巨大な配列処理を行う時はジェネレーターが便利

JavaScriptで配列から指定した数の組合せを作る関数を作ったところ、組合せの数が数千万になるケースがあり、Node.js(v14.16.0)で実行したら使用できるメモリの上限に達したというエラーが出てしまいました。

FATAL ERROR: Ineffective mark-compacts near heap limit Allocation failed - JavaScript heap out of memory

以下のように--max-old-space-sizeオプションを指定してNode.jsで使用できるメモリを増やせば動くようになったのですが、

$ node --max-old-space-size=8192 index.js

ES2015で追加されたジェネレーター(Generator)を教えてもらったので書き直してみました。

差分

- function combine(list, n) {
+ function* combine(list, n) {
      const len = list.length;
-     const result = [];
      const indexes = [];
      for (let i = 0; i < n; i++) {
          indexes.push(i);
      }
      const lastPos = n - 1;

      while (indexes[0] + n <= len) {
          while (indexes[lastPos] < len) {
-             result.push(indexes.map(i => list[i]));
+             yield indexes.map(i => list[i]);
              indexes[lastPos]++;
          }

          for (let pos = lastPos - 1; pos >= 0; pos--) {
              indexes[pos]++;
              const lastIdx = indexes[pos] + (lastPos - pos);
              if (lastIdx < len) {
                  for (; pos + 1 < n; pos++) {
                      indexes[pos + 1] = indexes[pos] + 1;
                  }
                  break;
              }
          }
      }
-
-     return result;
  }

  const list = ['a', 'b', 'c', 'd', 'e'];
  const n = 3;
- const result = combine(list, n);
- console.log(result);
+ for (const combi of combine(list, n)) {
+     console.log(combi);
  }
  /*
- [
-   [ 'a', 'b', 'c' ],
-   [ 'a', 'b', 'd' ],
-   [ 'a', 'b', 'e' ],
-   [ 'a', 'c', 'd' ],
-   [ 'a', 'c', 'e' ],
-   [ 'a', 'd', 'e' ],
-   [ 'b', 'c', 'd' ],
-   [ 'b', 'c', 'e' ],
-   [ 'b', 'd', 'e' ],
-   [ 'c', 'd', 'e' ]
- ]
+ [ 'a', 'b', 'c' ]
+ [ 'a', 'b', 'd' ]
+ [ 'a', 'b', 'e' ]
+ [ 'a', 'c', 'd' ]
+ [ 'a', 'c', 'e' ]
+ [ 'a', 'd', 'e' ]
+ [ 'b', 'c', 'd' ]
+ [ 'b', 'c', 'e' ]
+ [ 'b', 'd', 'e' ]
+ [ 'c', 'd', 'e' ]
  */

修正前のコードは、組合せの配列を作り、その配列を返していたのですが、修正した方はループしつつも値を一つずつ返すようになります。

何を言っているのかわからないと思うのですが、ジェネレーターはyieldで値を返し、そこで処理を一時停止します。

そして次呼ばれた時に続きから実行し、またyieldに到達したら値を返して一時停止します。
一時停止するってすごいですよね。

値を順番に一つずつ返す考え方はイテレーターと同じで、ジェネレーターはイテレーターを書きやすくしたものだそうです。

以下のようなジェネレーターの使用例を見てもメリットがよくわからなかったのですが、こういう風に使うとメモリへの負担を少なくできるということがわかりました

function* generator() {
    yield 1;
    yield 2;
    yield 3;
}

const gen = generator(); // "Generator { }"
for (const v of gen) {
    console.log(v);
}
/*
1
2
3
*/

function* infinite() {
    let index = 0;

    while (true) {
        yield index++;
    }
}

const generator = infinite(); // "Generator { }"

console.log(generator.next().value); // 0
console.log(generator.next().value); // 1
console.log(generator.next().value); // 2