Go to Qiita Advent Calendar 2024 Top
LoginSignup
50
41

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@tanaike(Kanshi Tanaike)

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

Last updated at Posted at 2018-04-18

Google Apps Script による配列処理のためのループ速度評価(V8 有効版)はこちらでご覧いただけます。

概要

Google Apps Script (GAS)を実行するとき、1度の実行で最大6分間の制限時間が設けられています。1 このため、ユーザは、スクリプトを各部分でプロセスコストが低くなるように努力と注意を払いつつ作成ます。 特に配列処理は各APIやスプレッドシートなどで頻繁に使われることから、配列処理のプロセスコストを知ることは重要項目の一つであると考えられます。GASは、他の言語とは異なり、実行時の最適化による効率化はあまり期待できないことからユーザ自身がプロセスコストを下げるための工夫を行う必要があります。2, 3 この記事では配列処理を行うためのループのコストについて報告させていただきます。すなわち、いくつかのループ手法を用いて配列処理を行い、それぞれの方法での処理速度を測定しています。

実験方法

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

  1. 一般的なfor loop
    • for (var i = 0; i < 10; i++) {array[i]}
  2. for in
    • for (var i in array) {array[i]}
  3. while
    • while (i < 10) {array[i++]}
  4. forEach
    • array.forEach(function(e){e})
  5. map, filter
    • array.map(function(e){e})
    • array.filter(function(e){e})
  6. Comprehension: GASはJavaScript 1.7を使っていることから、下記のような配列の内包表記を使用することができます。4, 5
    • [e for each (e in array)]

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

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

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

結果

20180416a-fig1.png

図 1. 1次元配列を処理する際の要素数と処理時間の関係. 横軸は要素数、縦軸は時間です. 傾きの逆数が速度に当たります. 縦軸が0にに近づくほど速度が速いことを示しています.

20180416a-fig2.png

図 2. 2次元配列を処理する際の要素数と処理時間の関係. 横軸は要素数、縦軸は時間です. 傾きの逆数が速度に当たります. 縦軸が0にに近づくほど速度が速いことを示しています.


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

  • 要素数が100万以下の範囲では要素数の増加に対して処理時間がほぼ線形で増加しています。
  • 処理時間の短い順番、すなわちプロセスコストの低い順番は、1次元配列、2次元配列共に"map, filter", "Comprehension", "forEach", "for in", "for loop", "while"
    • 最小、最大コストは、それぞれ"map, filter", "while"です。
    • 1次元配列、2次元配列の処理に対して"map, filter"は、"while"に比べてそれぞれ50 %, 58 %低くなることが分かりました。
    • "for loop"のコストが予想以上に高かったことには驚かされました。これはGAS特有の結果かもしれません。
  • push()とnew Array()ではそのプロセスコストはほぼ同じ。
    • これもまたとても興味深い結果です。

次に、図 1, 2を使って処理する配列の次元が変化した場合のプロセスコストの増加率を計算してみました。

20180416a-fig3.png

図 3. 1次元配列と2次元配列のそれぞれの処理時間の差を示した図. 縦軸が0に近づくほど配列の次元増加に対して処理時間の変化が一定であることを意味します.


Table 1. 図3を使って配列の次元が1から2次元に変化した際のプロセスコストの増加率の平均値を数値で表したもの. 例えば、comprehension（内包表記）を用いた場合の増加率7.3 %とは、処理する配列が1次元配列から2次元配列に変化したときのプロセスコストの増加率を示しています. 増加率が大きいほど、処理する配列の次元が増加することでコストがより増加する、すなわち効率が低くなることを意味します.

ループの手法 増加率 (%)
comprehension 7.3
foreach (newArray) 9.8
map,filter 10.5
foreach (push) 12.7
for in (push) 19.7
for in (newArray) 20.4
for loop (push) 28.8
while (push) 28.9
while (newArray) 29.0
for loop (newArray) 30.7

図3、表1から分かることは次の通りです。

  • "Comprehension", "forEach", "map, filter"では、配列の次元数増加に対するプロセスコストの変化は、"for in", "for loop", "while"の変化と比較して小さい。
    • "Comprehension", "forEach", "map, filter"の効率は配列の次元が変化してもそれほどコストは高まらない。

提案

上記の結果から、"map, filter"は、配列処理だけでなく従来のforループをより効率的に書き換えることができるのではないかと推測してみます。そこで、次のようなスクリプトを試してみました。

var max = 1000;

// 従来法
for (var i = 0; i < max; i++) {
  // do something
}

// 提案した方法
var r = Array.apply(null, new Array(max)).map(function(_, i) {
  // do something
});

この場合もこれまでの方法と同様にmaxの値を変化させながらそれぞれのmax値で100回以上の処理時間を測定しました。結果から、提案した方法は、従来法よりも10 %程度コストを下げることができることを確認しました。Array.apply()のコストが追加されるためにこの程度のコスト低減になりました。

まとめ

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

  1. 1次元配列、2次元配列から5の倍数を抜き出す処理では、"map, filter"が最も適している。
  2. 処理時間の短い順番、すなわちプロセスコストの低い順番は、1次元配列、2次元配列共に"map, filter", "Comprehension", "forEach", "for in", "for loop", "while"
  3. 1次元配列、2次元配列の処理に対して、"map, filter"は、"while"に比べてそれぞれ50 %, 58 %低い。
  4. var array = []で作成した配列へarray.push(value)を使って値を代入するコストとvar array = new Array()で作成した配列へarray[n][m] = valueを使って値を代入するコストはほぼ同じ。
  5. "Comprehension", "forEach", "map, filter"では、配列の次元増加に対するプロセスコストの変化は、"for in", "for loop", "while"の変化と比較して小さい。
  6. "map, filter"を使って一般的なforループから10 %程度のコスト低減が可能な手法を提案することができました。
    • 他にも考えられる方法があれば試してみたいと思います。

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

参考

  1. Current limitations at Quotas for Google Services
  2. Google Apps Scriptで配列要素の総和処理を高速で行いたい
  3. ピラミッド方式の他言語への適応性
  4. Basic JavaScript features at Built-in Google Services
  5. Array comprehensions

付録

スクリプト

元になる配列の作成

1次元配列の作成

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

2次元配列の作成

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次元配列の処理

// 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});


// comprehension
var result = [e for each (e in array) if (e % 5 == 0)];

2次元配列の処理

// 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})});


// comprehension
var result = [[f for each (f in e) if (f % 5 == 0)] for each (e in array)];

英語版

もしも本記事の英語版が必要な場合は、こちらをご覧ください。

50
41
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
50
41

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?