配列結合最速王を決めよう.js

この文書の目的

タイトル通りですが、最近JavaScript（Node.js）において配列の結合でトラブルに遭遇したので、どうしてたら良かったのかを改めてまとめてみました。

条件

この文書では、配列の結合とは以下のようなものを指すこととします。
a=[1,2,3]; b=[10,20,30]をc=[1,2,3,10,20,30]のようにする。

この例ではたかだか3要素しかない2つの配列を結合するだけなので、まあ普通にconcat()でも使いましょう、で終わりですが、やりたいこと（というかトラブルになったこと）は、「ある程度の要素数を持ったある程度の数の配列を結合すること」です。

以下に示すサンプルでは、要素として配列を持った親配列が以下のように定義されているものとします。

parentArray = [
    [1,2,3,....],
    [10,20,30,....],
    [100,200,300,....],
    ...
]

これを結合して、
resultArray = [1,2,3,....,10,20,30,....,100,200,300,........]
となるようにするのが目的とします。

さあ比較しよう

普通の方法（普通に使えるけど条件によってはトラブルになるよ）

concat（その1）

配列を結合するんだからconcatに決まってんだろ、と思う方もいるかもしれません。
後述するように使い方によってはconcatは有効ですが、以下のような使い方は気を付ける必要があります。

let resultArray = [];
for (const subArray of parentArray) {
    resultArray = resultArray.concat(subArray);
}

まず気を付けるべきは、concatは「非破壊的関数だ」ということです。
従って、実行結果である「結合して大きくなった配列」を、ループの度にコピーしていることになります。
0要素の配列(resultArrayの初期値)と100要素の配列を足すと100要素のコピーが、その100要素の配列にまた100要素の配列を足すと200要素のコピーが発生します。これを1000要素になるまで繰り返すと、5500要素分のコピーが発生することになります。要素は1000しかないのに。
つまり、コピーに要する時間が指数的に伸びて行ってしまうのがこの方法です。

push（その1）

concatと違い、pushは破壊的変更をおこなう関数ですのでコピーは足す分だけになるので速いです。ただし配列自体を引数として渡しても配列のまま足してくれちゃうので、引数リストに変換してあげる必要があります。これはスプレッド演算子を使って実現できます。

const resultArray = [];
for (const subArray of parentArray) {
    resultArray.push(...subArray);
}

とても速いです。速いのですが唯一の欠点は、これが引数リストとして渡さないといけない、ということです。
引数リストの長さの制限は、配列長の制限よりはるかに厳しいです。従って、長大な配列に対してこれを使うと、スタックオーバーフローと言われてしまう可能性があります。

ちょっとひねった方法（トラブルを起こしにくい方法）

concat（その2）

そもそもparentArrayが用意されている時点でここにたどり着いてる人もいると思いますが、concatには引数を複数渡すことができます。ですから、今回の例のようにparentArrayのような形で結合したい配列が用意されているのなら以下のようにするだけで結合した配列が出来上がります。

const resultArray = [].concat(...parentArray);

これは速いです。試した中では最速でした。
今回はparentArrayが最初から用意されていましたが、プログラム的に順次足していくような処理になってる場合だと見落とすかもしれませんね。この形に持っていければ高速化できるので意識してみるといいと思います。
欠点の一つはここでもスプレッド演算子で配列→引数リストの変換をおこなっていることです。
引数リストの制限にひっかかるほどの数の配列を結合するケースはそんなにないだろうとは思いますけど・・・。
欠点のもう一つは、結合するまで結合対象の配列を保持しておかないといけないので、メモリを食うことです。そもそも大きい配列の結合の話をしているので実はこれも無視できません。

flat

concatの引数リストの制限も許せない、というのであればこの方法も考えてみてください。

const resultArray = parentArray.flat();

まあまあ速いです。concat（その1）に比べたら雲泥の差で速いです。pushやconcat（その2）に対する利点は引数リストを使わないこと、です。

(2024/10/19訂正)
Node.js v20(LTS)で試したらflatはなんだか遅いですね。条件にもよりますがざっくりでいうと他(pushなど)よりひとケタ位遅いです。Chromeだとpushと同程度なんですけどなんででしょうね？同じV8エンジンなのに。

push（その2）

引数リストの制限に負けないflatが遅かったものだから、「引数リストの制限に負けない」かつ「それなりに速い」手段を考えます。
おまけに、concat（その2）の欠点である「結合するまで結合対象の配列を保持しておかないといけないので、メモリを食う」の弱点も解消して、結合できる時にさっさと結合してメモリを解放していける方法になります。

const resultArray = [];
for (const subArray of parentArray) {
    for (let i = 0; i < subArray.length; i = i + 30000) {
      resultArray.push(...subArray.slice(i, 30000));
    }
}

基本的にpush（その1）と同じですが、引数リストの制限にかからないように分割してpushしています。
今回の条件だとparentArrayが最初から用意されてるので意味ないですが、これが生きるのは結合対象の配列が順次できあがってくるようなケースです。
「引数リストの制限にかからず」「メモリも必要最低限しか食わず」「そこそこ速い」ので、まあどんなケースかあんまり考えなくてもこれ使っとけば無難です。

おっと、記事のタイトルは最速王でしたね。諸々に目をつぶって速さだけを追い求めるならばconcat（その2）が抜群に速いですのでケースバイケースで使い分けましょう。

終わりに

参考になりましたら幸いです。