では、初心者向けに「巨大配列でも先頭削除や追加を高速にする方法」を具体例付きで解説します。
1. 配列の先頭操作は遅い理由
let arr = [1,2,3,4,5];
arr.shift(); // 先頭を削除
- shift は配列の 全要素を左に詰め直す 必要がある
- 巨大配列だと 100万件でも 100万回のコピーが発生 → とても遅い
同様に unshift（先頭に追加）も同じ理由で遅い
2. 高速にする方法①：Deque（両端キュー）を自作する
配列をそのまま使わず、先頭操作用のインデックスをずらす方法です。
class FastQueue {
constructor() {
this.data = [];
this.head = 0; // 先頭の位置
}
enqueue(value) {
this.data.push(value); // 末尾追加は高速
}
dequeue() {
if (this.head >= this.data.length) return undefined;
return this.data[this.head++]; // 先頭をずらして取得
}
size() {
return this.data.length - this.head;
}
}
// 使用例
let q = new FastQueue();
for (let i = 0; i < 1000000; i++) q.enqueue(i);
console.time('dequeue');
while (q.size() > 0) {
let v = q.dequeue();
// console.log(v); // 巨大配列だと出力は控える
}
console.timeEnd('dequeue');
💡 ポイント
dequeue()は コピーを作らない- 巨大配列でも非常に高速
- 末尾追加（enqueue）と先頭削除（dequeue）が O(1) の操作になる
3. 高速にする方法②：二つの配列で分ける
- 元配列は「追加用」と「削除用」の2つに分ける
- 削除が溜まったら、まとめてスライスする
let front = [];
let back = [];
function enqueue(v) {
back.push(v);
}
function dequeue() {
if (front.length === 0) {
front = back.reverse(); // 先頭側にまとめる
back = [];
}
return front.pop();
}
// 使用例
for (let i = 0; i < 1000000; i++) enqueue(i);
console.time('dequeue2');
while (front.length + back.length > 0) {
let v = dequeue();
}
console.timeEnd('dequeue2');
- こちらも 先頭操作を高速化
- shift/unshift を繰り返すより大幅に高速
4. 実践のポイントまとめ
| 方法 | 長所 | 注意点 |
|---|---|---|
| 配列 + head インデックス | シンプル、直接アクセス | 配列が大きくなりすぎるとメモリの先頭部分が使われなくなるので定期的に slice で圧縮可能 |
| 二つの配列（front/back） | 先頭削除・追加が高速、コピーが少ない | 少し構造が複雑、逆順操作に注意 |
💡 初心者向けアドバイス
- 巨大データを扱う場合、shift/unshift は避ける
- 「先頭削除・追加が多い場合は、インデックス管理か二つの配列で処理」する
- 通常サイズの配列（数百～数千件）なら普通の配列操作で問題なし
