(2020/6/15 実験3を追記)
巷でよく、forループの条件に使う配列のlengthの値はキャッシュしておけという記事を見かけたことはありませんか？
私も最近遊び始めたAtCoderでよくTLEにぶつかるので、lengthをキャッシュしたりして、あがいています。
……が、それで解決したことって無いんですよね～。
というわけで、配列のlengthをキャッシュすると良いのが本当かどうか、調べてみました。
ついでにループ数を別の方法で毎回計算したり、for-ofを使う場合も一緒に実験しています。
実験1
まずは普通にやってみます。
ループの中身が必要なのかどうは解りませんが、とりあえず適当に書いてみた。
"use strict";
let t = 22;
let a = Array(2 ** t);
let p = Array(4).fill(0);
const alen = a.length;
console.time("teisu");
for (let i = 0; i < alen; i++) {
p[0] += 1;
}
console.timeEnd("teisu");
console.time("length");
for (let i = 0; i < a.length; i++) {
p[1] += 1;
}
console.timeEnd("length");
console.time("math");
for (let i = 0; i < Math.floor(2 ** t); i++) {
p[2] += 1;
}
console.timeEnd("math");
console.time("for-of");
for (let v of a) {
p[3] += 1;
}
console.timeEnd("for-of");
console.log(p);
- 結果
PS C:\******\test> node --version
v10.16.3
PS C:\******\test> node index.js
teisu: 19.144ms
length: 19.322ms
math: 87.904ms
for-of: 112.216ms
[ 4194304, 4194304, 4194304, 4194304 ]
PS C:\******\test> node index.js
teisu: 19.193ms
length: 18.266ms
math: 86.701ms
for-of: 109.150ms
[ 4194304, 4194304, 4194304, 4194304 ]
PS C:\******\test> node index.js
teisu: 19.923ms
length: 19.601ms
math: 110.356ms
for-of: 113.152ms
[ 4194304, 4194304, 4194304, 4194304 ]
あれ、なんだか定数にキャッシュした方が遅くないですか？
もしかして、配列のlengthみたいな値は内部でキャッシュされてて、配列を変更しない限りは素早く回せるように、内部実装が頑張っているんでしょうか？
実験2
今度は、ループの中で配列のサイズを変更してみましょう。
ついでに重くなりすぎたのでループ回数をちょっと減らします。
"use strict";
let t = 20;
let a = Array(2 ** t);
let p = Array(4).fill(0);
const alen = a.length;
console.time("teisu");
for (let i = 0; i < alen; i++) {
a.push(1);
p[0] += 1;
a.pop();
}
console.timeEnd("teisu");
console.time("length");
for (let i = 0; i < a.length; i++) {
a.push(a[0]);
p[1] += 1;
a.pop();
}
console.timeEnd("length");
console.time("math");
for (let i = 0; i < Math.floor(2 ** t); i++) {
a.push(a[0]);
p[2] += 1;
a.pop();
}
console.timeEnd("math");
console.time("for-of");
for (let v of a) {
a.push(1);
p[3] += 1;
a.pop();
}
console.timeEnd("for-of");
console.log(p);
- 結果
PS C:\******\test> node --version
v10.16.3
PS C:\******\test> node index.js
teisu: 1280.028ms
length: 1283.918ms
math: 1294.721ms
for-of: 1408.628ms
[ 1048576, 1048576, 1048576, 1048576 ]
PS C:\******\test> node index.js
teisu: 1312.229ms
length: 1285.958ms
math: 1262.693ms
for-of: 1394.593ms
[ 1048576, 1048576, 1048576, 1048576 ]
PS C:\******\test> node index.js
teisu: 1275.405ms
length: 1323.932ms
math: 1296.542ms
for-of: 1381.911ms
[ 1048576, 1048576, 1048576, 1048576 ]
内部の処理が重くなりすぎたせいか、今度は毎回長さを計算するバージョンまでほとんど差がなくなってしまいました。1
配列のlengthって、配列の長さが更新されるたびに予め計算されていたりするんでしょうか？2
実験3 (追記)
teisuをlengthの順序を入れ替えたらどうなるかという指摘がありましたので、やってみます。
ついでに「length」「teisuu」の文字数もそろえ、2回ずつ10周、計20回ずつ測定してみました。
"use strict";
let t = 25;
let a = Array(2 ** t);
let p = Array(4).fill(0);
const alen = a.length;
for (let j = 0; j < 10; j++) {
console.time("length");
for (let i = 0; i < a.length; i++) {
p[1] += 1;
}
console.timeEnd("length");
console.time("teisuu");
for (let i = 0; i < alen; i++) {
p[2] += 1;
}
console.timeEnd("teisuu");
console.time("length");
for (let i = 0; i < a.length; i++) {
p[3] += 1;
}
console.timeEnd("length");
console.time("teisuu");
for (let i = 0; i < alen; i++) {
p[0] += 1;
}
console.timeEnd("teisuu");
console.log(p);
}
- 結果
PS C:\******\test> node index.js
length: 110.039ms
teisuu: 112.988ms
length: 113.025ms
teisuu: 118.405ms
[ 33554432, 33554432, 33554432, 33554432 ]
length: 123.954ms
teisuu: 112.184ms
length: 110.691ms
teisuu: 109.649ms
[ 67108864, 67108864, 67108864, 67108864 ]
length: 114.410ms
teisuu: 115.328ms
length: 109.536ms
teisuu: 110.819ms
[ 100663296, 100663296, 100663296, 100663296 ]
length: 111.722ms
teisuu: 116.108ms
length: 114.514ms
teisuu: 112.101ms
[ 134217728, 134217728, 134217728, 134217728 ]
length: 113.597ms
teisuu: 111.972ms
length: 138.793ms
teisuu: 112.685ms
[ 167772160, 167772160, 167772160, 167772160 ]
length: 116.327ms
teisuu: 111.483ms
length: 120.830ms
teisuu: 151.815ms
[ 201326592, 201326592, 201326592, 201326592 ]
length: 113.967ms
teisuu: 109.445ms
length: 110.041ms
teisuu: 109.446ms
[ 234881024, 234881024, 234881024, 234881024 ]
length: 114.933ms
teisuu: 110.076ms
length: 114.454ms
teisuu: 109.270ms
[ 268435456, 268435456, 268435456, 268435456 ]
length: 111.252ms
teisuu: 109.153ms
length: 112.982ms
teisuu: 110.567ms
[ 301989888, 301989888, 301989888, 301989888 ]
length: 114.891ms
teisuu: 113.678ms
length: 112.419ms
teisuu: 114.236ms
[ 335544320, 335544320, 335544320, 335544320 ]
やっぱりドングリの背比べになりました。
結論
Node.jsの場合、配列をループさせる際の条件式においてlengthをキャッシュする意味はほぼなさそうですね。
条件式を計算させたりするとさすがに時間がかかりますが、ループ内で重たい操作をするなら誤差の範囲ですので、やっぱり気にしなくてよさそうです。TLEするならもっと別の原因を探しましょう。3