はじめに
AtCoder で D - Writing a Numeral という問題をやったときなんだかんだACすることはできたのですが、JSで2000ms前後かかっているところに引っかかりました。
感覚的には「500msもかからないはず…」と思い、他の人の時間を調べて見ました。
すると、約200msの人と2000ms強の人で二分化されていました。
それぞれ、アルゴリズムはほぼ同じだったので、「アルゴリズムではなく、プログラム的な部分や言語的な部分の最適化だろう」と思い、入出力周りを見比べて高速化のヒントを得ることができました。
どうすれば高速化できるのか？
結論から書いてしまうと、出力内容を配列に溜めておいて、最後にまとめて出力することで高速化できます。
コード例
function main(log) {
// console.log ではなく log を使う
log(1);
}
(() => {
const buffer = [];
// 使えるメモリに応じて調整
const MAX_BUFFER_LENGTH = 1000000;
const log = (v) => {
if (buffer.push(v) >= MAX_BUFFER_LENGTH) {
console.log(buffer.join('\n'));
buffer.length = 0;
}
};
main(log);
console.log(buffer.join('\n'));
})();
関数名は好きに付けて構いませんが、一応console.logに倣ってlogとしました。
console.logを使わずにlogを使えば最終的にまとめて出力されるというコードになっています。
どのぐらい速くなるのか？
AtCoderでやった問題が、最大60万回出力される可能性があったので、60万回数値を出力するので比較してみます。
検証環境は v18.15.0 です。
console.log を使った場合
default: 1.657s
検証コード
実行コマンド
node memo/log3.js | tail -n 1
memo/log3.js
function main() {
const N = 600000;
for (let i = 0; i < N; i++) {
console.log(i);
}
}
console.time();
main();
console.timeEnd();
log を使って最後にまとめて出力した場合
default: 100.129ms
検証コード
実行コマンド
node memo/log2.js | tail -n 1
memo/log2.js
function main(log) {
const N = 600000;
// console.log ではなく log を使う
for (let i = 0; i < N; i++) {
log(i);
}
}
(() => {
const buffer = [];
// 使えるメモリに応じて調整
const MAX_BUFFER_LENGTH = 1000000;
const log = (v) => {
if (buffer.push(v) >= MAX_BUFFER_LENGTH) {
console.log(buffer.join('\n'));
buffer.length = 0;
}
};
console.time();
main(log);
console.log(buffer.join('\n'));
console.timeEnd();
})();
16倍ぐらい速くなった！
約1.6s → 約100ms
約16倍速くなりました！
ちなみにAtCoderで提出したものは、約1900msから約200msになりました。
あとがき
実際のところ、業務だとfsでファイルに書き出したりすることが多く、標準出力に大量に吐き出すことはあまりないので、気にすることもないですが、もし console.log を使って大量のデータを出力する事があればぜひ参考にしてください。
Discussion