Google Apps Script による配列処理のためのループ速度評価(V8 有効版)

# Google Apps Script による配列処理のためのループ速度評価(V8 版)

# 概要

Google Apps Script (GAS)を実行するとき、1 度の実行で最大 6 分間の制限時間が設けられています。[<sup>1</sup>](#References) このため、ユーザは、スクリプトを各部分でプロセスコストが低くなるように努力と注意を払いつつ作成ます。特に配列処理は各 API やスプレッドシートなどで頻繁に使われることから、配列処理のプロセスコストを知ることは重要項目の一つであると考えられます。最近、GAS で [V8 エンジンを使用することができるようになり](https://developers.google.com/apps-script/guides/v8-runtime)、これにより、[V8 が無効の条件下での評価結果](https://qiita.com/tanaike/items/1f45e75019b5976e897f)が変化すると考えられます。そこで、この記事では V8 が無効の条件下で行ったスクリプトをそのまま使用して V8 を有効にした条件で行ったプロセスコストの評価について記載させていただきます。

# 実験方法

実験で使用した配列を処理するための方法は下記の 6 種類です。

1. 一般的な for loop
   - `for (var i = 0; i < 10; i++) {array[i]}`
1. for in
   - `for (var i in array) {array[i]}`
1. while
   - `while (i < 10) {array[i++]}`
1. forEach
   - `array.forEach(function(e){e})`
1. map, filter
   - `array.map(function(e){e})`
   - `array.filter(function(e){e})`
1. reduce
   - `array.reduce(function(ar,e){e},[])`

プロセスコストの測定用サンプルスクリプトとして、配列から 5 の倍数を抽出するプロセスを用いました。このプロセスについて、上記 6 つの手法でその処理時間を測定しました。測定に用いた各スクリプトは[こちら](#SampleScripts)をご覧ください。配列処理の時間を測定する元になる配列は、1 次元配列と 2 次元配列の 2 種類を用意しました。最初の配列生成のコストは除外しています。また、配列への値の代入コストも調べるために次のような比較を同時に行いました。

- `var array = []`で作成した配列へ`array.push(value)`を使って値を代入する。
- `var array = new Array()`で作成した配列へ`array[n][m] = value`を使って値を代入する。

GAS の処理速度はその都度変化することが分かっていますので、実験では図の各データ点毎に 100 回以上の測定を行い、平均値の変化が 1 %以下になったことを確認してそのときの平均値をデータとして採用しました。今の場合、エラーバーの重要性は低いことと、エラーバーを表示すると図が見えにくくなりましたので外しました。

> V8 が無効の条件下では`[e for each (e in array)]`のような Comprehension を使用することができましたが、V8 を有効にすると、使用できませんので今回は削除しています。

# 結果

![20200209a-fig1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/133383/d4329eaa-296c-702e-d930-ff31b38c268b.png)


図 1. 1 次元配列を処理する際の要素数と処理時間の関係. 横軸は要素数、縦軸は時間です.

![20200209a-fig2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/133383/7ac94884-5605-44af-78a9-37171adba1d8.png)


図 2. 2 次元配列を処理する際の要素数と処理時間の関係. 横軸は要素数、縦軸は時間です.

<br>

図 1, 2 から分かることは次の通りです。

- "for loop", "while", "forEach", "map, filter", "reduce"の処理時間は、要素数が 100 万以下の場合、要素数の増加に対して大きな変化は認められません。
- "for in"の処理時間は、要素数の増加に対して線形で増加しています。
- `push()`と`new Array()`ではそのプロセスコストはほぼ同じ。

ここで重要なことは、これらの V8 を有効にした場合の結果と V8 が無効の場合の結果との比較です。次に図 3, 4 として V8 有無でのプロセスコストの測定結果を示します。

<br>

![20200209a-fig3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/133383/6d43d680-8a99-5e0c-ba77-99925917706e.png)


図 3. 1 次元配列を処理する際の要素数と処理時間の関係. 横軸は要素数、縦軸は時間です. Without V8, With V8 は、それぞれ V8 が無効、有効の条件下での結果.

![20200209a-fig4.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/133383/4841e902-d11b-03e2-38a5-da0e105c6dc9.png)


図 4. 2 次元配列を処理する際の要素数と処理時間の関係. 横軸は要素数、縦軸は時間です. Without V8, With V8 は、それぞれ V8 が無効、有効の条件下での結果.

<br>

図 3, 4 から分かることは次の通りです。

- V8 を有効にすることで、これまで使用していたスクリプトのループのパフォーマンスがスクリプトを変更することなく大幅に向上することが分かります。

具体的に各メソッドに対する定量的な評価は次の表 1 をご覧ください。

<br>

表 1: 同一スクリプトで V8 を有効にした場合のコストの減少率. 計算は `(Result_with_V8 - Result_without_V8) / Result_with_V8` を使用しました.

| Methods             |       1D |        2D |
| :------------------ | -------: | --------: |
| map,filter          |  -4,464% | -202,033% |
| for loop (newArray) | -40,788% | -241,181% |
| for in (newArray)   |  -1,601% |  -50,574% |
| while (newArray)    | -41,573% | -200,235% |
| foreach (newArray)  |  -8,886% | -258,614% |
| for loop (push)     | -23,059% | -171,697% |
| for in (push)       |  -1,782% |  -54,261% |
| while (push)        | -19,505% | -256,434% |
| foreach (push)      |  -7,431% | -253,924% |
| reduce              |  -7,999% | -253,887% |
|                     |          |
| Average             | -15,709% | -253,887% |

マイナス値になっている理由は、コストが下がっていることを示しています。また、上記の場合、大幅なコスト減少が認められます。

ここで、V8 を有効にすることで 2D 配列の方が 1D 配列よりもよりコストの減少率が低くなっていることについて、次のように考えられます。この測定方法では、100 万要素でコストを測定する場合、1D 配列では一つの配列内に 100 万要素を入れ、それをループさせています。これに対して、2D 配列では、2D 配列内の各要素である 1D 配列の要素を 1,000 個と固定して、この 1D 配列の数を 1,000 に増加させることで 1,000 x 1,000 = 1,000,000 要素として測定しています。この違いが顕著に現れたものと思われます。

# まとめ

この記事では 6 種類のループ手法を用いて配列処理を行い、それぞれのプロセスコストを調べました。実験で得たことは次の通りです。

- "for loop", "while", "forEach", "map, filter", "reduce"の処理時間は、要素数が 100 万以下の場合、要素数の増加に対して大きな変化は認められない。
- "for in"の処理時間は、要素数の増加に対して線形で増加している。
- `push()`と`new Array()`ではそのプロセスコストはほぼ同じ。

これらの結果から、V8 を有効にすることで、これまで使用していたスクリプトをそのまま使用してもループのパフォーマンスが大幅に向上することが分かりました。

**（注意）この方法は Google Apps Script での結果です。他の言語については異なる可能性がありますのでご注意ください。**

<a name="References"></a>

# 参考

1. [Current limitations at Quotas for Google Services](https://developers.google.com/apps-script/guides/services/quotas#current_limitations)

# 付録

<a name="SampleScripts"></a>

## スクリプト

### 元になる配列の作成

1 次元配列の作成

```javascript
function make1dArray(row) {
  var ar = [];
  for (var i = 0; i < row; i++) {
    ar[i] = i + 1;
  }
  return ar;
}
```

2 次元配列の作成

```javascript
function make2dArray(row) {
  var ar1 = [];
  for (var i = 0; i < row; i++) {
    var ar2 = [];
    for (var j = 0; j < 100; j++) {
      ar2[j] = j + 1;
    }
    ar1[i] = ar2;
  }
  return ar1;
}
```

### 1 次元配列の処理

```javascript
// for loop using push()
var result = [];
for (var i = 0; i < array.length; i++) {
  if (array[i] % 5 == 0) {
    result.push(array[i]);
  }
}

// for loop using new Array()
var result = new Array(array.length / 5);
var c = 0;
for (var i = 0; i < array.length; i++) {
  if (array[i] % 5 == 0) {
    result[c++] = array[i];
  }
}

// for in using push()
var result = [];
for (var i in array) {
  if (array[i] % 5 == 0) {
    result.push(array[i]);
  }
}

// for in using new Array()
var result = new Array(array.length / 5);
var c = 0;
for (var i in array) {
  if (array[i] % 5 == 0) {
    result[c++] = array[i];
  }
}

// while using push()
var result = [];
var i = 0;
while (i < array.length) {
  if (array[i] % 5 == 0) {
    result.push(array[i]);
  }
  i += 1;
}

// while using new Array()
var result = new Array(array.length / 5);
var c = 0;
var i = 0;
while (i < array.length) {
  if (array[i] % 5 == 0) {
    result[c++] = array[i];
  }
  i += 1;
}

// forEach using push()
var result = [];
array.forEach(function(e) {
  if (e % 5 == 0) {
    result.push(e);
  }
});

// forEach using new Array()
var result = new Array(array.length / 5);
var c = 0;
array.forEach(function(e) {
  if (e % 5 == 0) {
    result[c++] = e;
  }
});

// map, filter
var result = array.filter(function(e) {
  return e % 5 == 0;
});

// reduce
var result = array.reduce(function(o, e) {
  if (e % 5 == 0) o.push(e);
  return o;
}, []);
```

### 2 次元配列の処理

```javascript
// for loop using push()
var result = [];
for (var i = 0; i < array.length; i++) {
  var temp = [];
  for (var j = 0; j < array[i].length; j++) {
    if (array[i][j] % 5 == 0) {
      temp.push(array[i][j]);
    }
  }
  result.push(temp);
}

// for loop using new Array()
var result = new Array(array.length);
for (var i = 0; i < array.length; i++) {
  var temp = new Array(100 / 5);
  var c = 0;
  for (var j = 0; j < array[i].length; j++) {
    if (array[i][j] % 5 == 0) {
      temp[c++] = array[i][j];
    }
  }
  result[i] = temp;
}

// for in using push()
var result = [];
for (var i in array) {
  var temp = [];
  for (var j in array[i]) {
    if (array[i][j] % 5 == 0) {
      temp.push(array[i][j]);
    }
  }
  result.push(temp);
}

// for in using new Array()
var result = new Array(array.length);
var c1 = 0;
for (var i in array) {
  var temp = new Array(100 / 5);
  var c2 = 0;
  for (var j in array[i]) {
    if (array[i][j] % 5 == 0) {
      temp[c2++] = array[i][j];
    }
  }
  result[c1++] = temp;
}

// while using push()
var result = [];
var i = 0;
while (i < array.length) {
  var temp = [];
  var j = 0;
  while (j < array[i].length) {
    if (array[i][j] % 5 == 0) {
      temp.push(array[i][j]);
    }
    j += 1;
  }
  result.push(temp);
  i += 1;
}

// while using new Array()
var result = new Array(array.length);
var i = 0;
while (i < array.length) {
  var temp = new Array(100 / 5);
  var c = 0;
  var j = 0;
  while (j < array[i].length) {
    if (array[i][j] % 5 == 0) {
      temp[c++] = array[i][j];
    }
    j += 1;
  }
  result[i] = temp;
  i += 1;
}

// forEach using push()
var result = [];
array.forEach(function(e) {
  var temp = [];
  e.forEach(function(f) {
    if (f % 5 == 0) {
      temp.push(f);
    }
  });
  result.push(temp);
});

// forEach using new Array()
var result = new Array(array.length);
array.forEach(function(e, i) {
  var temp = new Array(100 / 5);
  var c = 0;
  e.forEach(function(f) {
    if (f % 5 == 0) {
      temp[c++] = f;
    }
  });
  result[i] = temp;
});

// map, filter
var result = array.map(function(e) {
  return e.filter(function(f) {
    return f % 5 == 0;
  });
});

// reduce
var result = array.reduce(function(o, e) {
  var temp = e.reduce(function(p, f) {
    if (f % 5 == 0) p.push(f);
    return p;
  }, []);
  o.push(temp);
  return o;
}, []);
```

上記の語版が必要な場合は、[こちら](https://gist.github.com/tanaikech/3331e1e631d619abef8f32c4be14ba3a)をご覧ください。