JavaScript で配列ループ処理の計算量&メモリ効率を調べてみた
はじめに
最近、生成AIを使ってプログラミングする際、時間計算量や空間計算量、メモリ効率を気にして書いている事が多いんですが、特に配列ループ処理についての計算量で個人的に誤解してた部分もあり、改めて、JavaScript を使って、配列ループ処理について調査しました。
そもそも、計算量とは?
以下、記事が参考になると思います。
今回の記事では、時間計算量と空間計算量、メモリ効率も含めて、調査していきます。
また、計算量はO記法で表記していきます。
今回試した内容
約100万要素ある2次元配列から、a - z までのアルファベット26文字が格納されてる1次元配列を生成するコードを作成します。
また、データの変更に影響されないように、bigArr の配列内容の構造に依存せず、抽出するようにします。
サンプルコード
// 約100万要素 を生成する2次元配列を作成
// [[a, b, c], [b, c, d] ....] という配列を生成
const bigArr = Array.from({ length: 333334 }, (_, i) => {
const base = 97 + (i % 26); // ASCII 'a' - 'z' 繰り返し
return [String.fromCharCode(base), String.fromCharCode(base + 1), String.fromCharCode(base + 2)];
});
// 2重 forEach
const alphabetArrA = () => {
const alphabetSet = new Set();
bigArr.forEach(subArr => {
subArr.forEach(char => {
if (char >= 'a' && char <= 'z') {
alphabetSet.add(char);
}
});
});
return Array.from(alphabetSet);
};
// flatMap + filter を使う
const alphabetArrB = () => {
return [...new Set(bigArr.flatMap(subArr => subArr.filter(char => char >= 'a' && char <= 'z')))];
};
// flat().filter() を使う
const alphabetArrC = () => {
return [...new Set(bigArr.flat().filter(char => char >= 'a' && char <= 'z'))];
};
function benchmark(label, fn) {
const start = performance.now();
fn();
const end = performance.now();
console.log(`${label}: ${(end - start).toFixed(3)} ms`);
}
benchmark("1: 2重 forEach", () => {
alphabetArrA();
});
benchmark("2: flatMap + filter", () => {
alphabetArrB();
});
benchmark("3: flat → filter", () => {
alphabetArrC();
});
前提条件
計算量の表記について、今回は以下の前提で、記載します。
-
n -
m -
k -
r -
u
1: 2重 forEach + Set
まずは、2重 forEach + Set を使ったパターンです。
普段使ってる Claude Code はこのコードを作成してきました。
const alphabetArrA = () => {
const alphabetSet = new Set();
bigArr.forEach(subArr => {
subArr.forEach(char => {
if (char >= 'a' && char <= 'z') {
alphabetSet.add(char);
}
});
});
return Array.from(alphabetSet);
};
時間計算量
さて、この処理の時間計算量ですが、よくハマる考えが、2重 forEach =
しかし、厳密には元の2次元配列は、行数(
生成したデータの数 = 配列から不要な値と重複が除外された数を
最後の返り値の Array.from() で
空間計算量
空間計算量は new Set() の宣言で
メモリ効率
ループ中に中間配列が生成されていないので、メモリの使用率が少なく、メモリ効率はかなり良いです。
2: flatMap + filter + Set
flatMap + filter + Set を使ったパターンです。コードの可読性的には、スマートに書かれており、見やすい印象です。では、計算量はどうでしょうか?
const alphabetArrB = () => {
return [...new Set(bigArr.flatMap(subArr => subArr.filter(char => char >= 'a' && char <= 'z')))];
};
時間計算量
- flatMap+filter →
O(n) - Set 構築 →
O(r) r - 配列展開 →
O(u)
空間計算量
- フィルタ結果の中間配列 →
O(r) - Set →
O(u) - 返り値の配列展開 →
O(u)
この場合、中間配列が生成されているため、空間計算量は
メモリ効率
中間配列が生成されているため、メモリ負荷が大きくなっています。
3: flat() → filter() → Set() → 配列化
flat() → filter() → Set() → 配列化の順で生成するパターンです。
(Copilot はこのコードを提示してきました。)
const alphabetArrC = () => {
return [...new Set(bigArr.flat().filter(char => char >= 'a' && char <= 'z'))];
};
こちらも、コードはスマートですが、計算量はどうでしょうか?
時間計算量
-
flat()→O(n) -
filter()→O(n) -
Set()→O(r) - 配列化 →
O(u)
上記を合計すると
空間計算量
-
flat()の中間配列 →O(n) - フィルタ結果 →
O(r) - Set/返り値 →
O(u)
上記を計算すると
メモリ効率
flat() で一度すべての配列要素を中間配列で生成してしまうため、メモリ負荷はこの中で最も重いです
計算量の結果まとめ
| 関数 | 時間計算量 | 空間計算量 | メモリ効率 |
|---|---|---|---|
| 1: 2重 forEach | ◎ | ||
| 2: flatMap + filter | △ | ||
| 3: flat → filter |
|
✗ |
上記の結果を見ると、
1の2重 forEach が最もパフォーマンスが良く、3の flat → filter が最も重いものになります。
ベンチマークテストで検証する
では、実際にサンプルコードを動かして、ベンチマークテストしてみます。
$ node arr.js
1: 2重 forEach: 17.198 ms
2: flatMap + filter: 29.177 ms
3: flat → filter: 32.821 ms
やはり、1 が一番早く、3 が一番遅い結果になりました。
まとめ
今回は、配列ループ処理の計算量やメモリ効率を調べてみました。
基本的には、如何に中間配列を生成せずに処理させるがポイントかなと思いましたが、大半のモダンな書き方はシャローコピーで中間配列を生成するため、実際にコードの可読性なども考慮すると、多少、計算量をトレードオフの対象にすることも考慮する必要はあるのかなと思いました。
とはいえ、計算量を意識して書くことは、生成AIを使用する現代の開発では必要なことだなと改めて思いました。
(余談ですが、Claude Code は 1 の方法で作成したので、パフォーマンスの観点では考慮されたコード書いていることがわかりました。すげぇな。)
Discussion