Java 逆引き集 | バッファ付きコレクション（LinkedList の代替） — メモリ/性能の考慮

Java Java
スポンサーリンク

バッファ付きコレクション（LinkedList の代替） — メモリ/性能の考慮

「バッファ用途（キュー、先頭・末尾の出し入れ、スライディングウィンドウ）」で LinkedList を選びがちですが、実務では ArrayDeque や ArrayList（必要ならプリサイズ）で十分かつ高速・省メモリになることが多いです。LinkedList はノードごとのオブジェクト/参照コストが高く、ランダムアクセスが遅い（局所性が悪い）ため、近年の JVM/CPU では不利になりやすいのが実態です。

いつ LinkedList を避けるべきか

  • メモリ効率: LinkedList は各要素に前後ノード参照を持つため、オーバーヘッドが大きい。大量要素のバッファでは不利。
  • アクセス性能: ランダムアクセスが遅い（先頭から辿る必要）。配列ベースの ArrayList/ArrayDeque は連続メモリで CPU キャッシュヒットが見込みやすい。
  • 一般的な開発指針: 多くの場面では ArrayList を基本に、挿入/削除を頻繁に行う「位置依存」シナリオのみ LinkedList を検討するのが現代的なアドバイスです。

推奨代替と使い分け

  • ArrayDeque（双端キューの定番）: 先頭・末尾の入出力が高速。リングバッファ的に扱うのに最適。スタック/キュー両方の用途に向く。
  • ArrayList（連続メモリのバッファ）: 末尾中心の追加/削除が多いなら最速。サイズ見積もりがあるなら初期容量指定で拡張コストを低減。
  • ConcurrentLinkedQueue（並行キュー）: マルチスレッドでロックレスに使いたい場合の定番。弱一貫性の反復になる点に留意。

基本コード例

ArrayDeque をキュー/リングバッファとして使う

import java.util.ArrayDeque;
import java.util.Deque;

Deque<String> buf = new ArrayDeque<>(1024); // 初期容量で拡張を減らす

buf.addLast("A");  // enqueue
buf.addLast("B");
String x = buf.pollFirst(); // dequeue → "A"
Java
  • ポイント: 先頭・末尾の入出力が O(1) で高速。LinkedList よりメモリ効率が良く、キャッシュ局所性も高いことが多い。

ArrayList を「蓄積用バッファ」として使う（プリサイズ）

import java.util.ArrayList;
import java.util.List;

int expected = 10_000;
List<String> buf = new ArrayList<>(expected); // 事前容量でコピー拡張コストを回避
for (int i = 0; i < expected; i++) {
    buf.add("rec-" + i);
}
Java
  • ポイント: 末尾中心の追記に強い。ランダムアクセス O(1) で集計や後処理も速い。

ConcurrentLinkedQueue でプロデューサ/コンシューマ

import java.util.concurrent.ConcurrentLinkedQueue;

ConcurrentLinkedQueue<String> q = new ConcurrentLinkedQueue<>();
q.add("job1");
q.add("job2");

String job = q.poll(); // マルチスレッドでも安全（ロックレス）
Java
  • ポイント: 並行用途では ArrayDeque/LinkedList ではなく並行コレクションを選ぶ。

スライディングウィンドウ（固定長バッファ）のレシピ

import java.util.ArrayDeque;
import java.util.Deque;

class SlidingWindow {
    private final Deque<Integer> dq = new ArrayDeque<>();
    private final int max;

    SlidingWindow(int max) { this.max = max; }

    void add(int x) {
        if (dq.size() == max) dq.pollFirst(); // 先頭を落としてリング風に
        dq.addLast(x);
    }

    double avg() {
        int sum = 0;
        for (int v : dq) sum += v;
        return dq.isEmpty() ? 0.0 : (double) sum / dq.size();
    }
}

public class Main {
    public static void main(String[] args) {
        SlidingWindow w = new SlidingWindow(3);
        w.add(10); w.add(20); w.add(30); w.add(40); // 10 は落ちる
        System.out.println(w.avg()); // (20+30+40)/3 = 30.0
    }
}
Java
  • ポイント: ArrayDeque は双端操作が速く、固定長バッファを手軽に構築できる。

よくある用途別の選び方

  • ログやイベントの一時蓄積: 末尾追記中心 → ArrayList（プリサイズ）。
  • 到着順キュー処理/リングバッファ: 先頭/末尾入出力 → ArrayDeque。
  • 並行キュー（複数スレッド）: ConcurrentLinkedQueue、必要に応じて BlockingQueue（ArrayBlockingQueue 等）。
  • 中間挿入が非常に多い特殊ケース: 限定的に LinkedList（ただしメモリ/検索コストに注意）。

テンプレート集（そのまま使える形）

  • ArrayDeque（キュー/スタック）
Deque<T> dq = new ArrayDeque<>(capacity);
dq.addLast(x);     // enqueue
T y = dq.pollFirst(); // dequeue
dq.addFirst(x);    // push (stack)
T z = dq.pollFirst(); // pop (stack)
Java
  • ArrayList（蓄積＋ランダムアクセス）
List<T> buf = new ArrayList<>(expectedSize);
buf.add(elem);           // 末尾追記が中心なら最適
T e = buf.get(index);    // O(1)
Java
  • ConcurrentLinkedQueue（並行）
var q = new java.util.concurrent.ConcurrentLinkedQueue<T>();
q.add(task);
T t = q.poll();
Java
  • 固定長リング（溢れたら捨てる）
if (dq.size() == max) dq.pollFirst();
dq.addLast(x);
Java

落とし穴と回避策

  • LinkedList の乱用: 大量要素やランダムアクセスがある場合は不向き。配列ベースを優先。
  • 初期容量指定の不足: ArrayList/ArrayDeque で大規模想定ならプリサイズして拡張コストを減らす。
  • 並行性の誤用: 非並行コレクションを複数スレッドで共有しない。並行用のコレクションへ切り替え。
  • イミュータブル/ビューの編集: List.of やサブリストなど変更不可/ビュー編集は例外や不整合に注意。必要ならコピー。

まとめ

  • バッファ用途は「配列ベース」を第一選択に。双端なら ArrayDeque、末尾中心なら ArrayList（プリサイズ）。並行は専用コレクション。LinkedList は限定的用途のみ。
  • メモリ効率、CPU キャッシュ、アクセスパターンに合わせて選ぶと、シンプルで速いバッファが作れる。
スポンサーリンク
タイトルとURLをコピーしました