Java 逆引き集 | ストリームでのランダムアクセスの落とし穴 — パフォーマンス評価

Java Java
スポンサーリンク

概要と本質

ストリームは「順次走査」に強く、「ランダムアクセス」に弱い仕組みです。配列や ArrayList のようなランダムアクセス向きのデータ構造でも、ストリームに乗せるとインデックス指定は基本的に「前から舐める」動きになり、必要要素までの要素数に比例して遅くなります。設計の要点は「ランダムアクセスが必要ならストリームに乗せない」「どうしても乗せるならインデックスを流す」か「一度だけ走査して必要なものを集める」に寄せることです。

ランダムアクセスが遅くなる理由

skip/findFirst は線形

stream.skip(n).findFirst() は n 個をスキップするために n 要素を順次消費します。インデックス i にアクセスするのに O(i) かかり、これを複数回行うと総じて O(∑i) のコストに膨らみます。インデックス直接参照できる配列やリストの .get(i) と構造的に違う動きだと理解してください。

データ構造による違い（ArrayList と LinkedList）

ArrayList は .get(i) が O(1) でも、stream().skip(i) は O(i) です。LinkedList はそもそも .get(i) が O(i) で、さらにストリームの skip も O(i) のため、ランダムアクセスは二重に不利になります。リンク構造をストリームで「飛び越える」方法はなく、逐次辿るしかありません。

ストリームの一回性と再走査コスト

ストリームは「一度限りの消費」です。必要インデックスごとに毎回 list.stream() を作って skip(i) するようなコードは、毎回先頭から走査し直すため累積コストが大きくなります。乱択アクセスが複数あるなら、走査は一度にまとめるか、インデックス列を先に用意するのが安全です。

典型的な落とし穴の例

インデックス取り出しを繰り返すケース

「いくつかのインデックスを取りたい」処理で、次のように書くと確実に遅くなります。

List<String> list = // 大量データ
int[] idx = {10, 1000, 50000};

for (int i : idx) {
    String x = list.stream().skip(i).findFirst().orElse(null); // 毎回先頭から O(i)
    // use x...
}
Java

このアプローチは3回とも先頭から再走査します。配列やリストの直接アクセスに切り替えるだけで桁違いに速くなります。

for (int i : idx) {
    String x = i < list.size() ? list.get(i) : null; // O(1)（ArrayList）
}
Java

フィルタ後のランダムアクセス

「条件を満たす要素のうち k 番目が欲しい」場面で filter(...).skip(k).findFirst() を何度も呼ぶと、毎回条件判定とスキップが発生します。必要な k が複数あるなら、一度だけフィルタして toList() した上で直接アクセスするほうが速く、読みやすいです。

List<Item> filtered = items.stream().filter(this::cond).toList();
Item kth = (k < filtered.size()) ? filtered.get(k) : null;
Java

実務での安全な設計指針

乱択パターンは配列・for で書く

「インデックスから取り出す」「ランダムにサンプリングする」「 nth 要素だけ処理する」などのパターンは、配列や ArrayList の直接アクセスに寄せるのが正解です。ストリームは「全体を流す」ほうが得意で、ランダムアクセスは得意ではありません。

インデックスを流すアプローチ

どうしてもストリームで書きたいなら「要素を流す」のではなく「インデックスを流す」ことで直接アクセスを維持します。IntStream.range(0, list.size()) を使えば、ランダムも順次も自由に設計できます。

List<String> list = // ...
String kth = IntStream.range(0, list.size())
    .filter(i -> i == k)
    .mapToObj(list::get)
    .findFirst()
    .orElse(null);
Java

この形は skip ではなく配列アクセスで取りに行くため、ArrayList なら O(1) アクセスが保てます。

一度だけ順次処理して必要なものを集める

複数の位置が必要なら、一度だけ順次走査して「必要位置を拾う」処理にしましょう。スキャンを一度にまとめることで、再走査を避けられます。

List<Integer> targets = List.of(10, 1000, 50000);
Set<Integer> need = new HashSet<>(targets);
Map<Integer, String> picked = new HashMap<>();

for (int i = 0; i < list.size(); i++) {
    if (need.contains(i)) picked.put(i, list.get(i));
    if (picked.size() == need.size()) break; // すべて拾ったら終了
}
Java

コード例とテンプレート

skip の代替（配列・リスト直接アクセス）

// NG: ストリームでスキップ
String x = list.stream().skip(i).findFirst().orElse(null);

// OK: 直接アクセス
String y = (i < list.size()) ? list.get(i) : null;
Java

IntStream.range でインデックスを付与

List<String> list = // ...
List<String> picked = IntStream.range(0, list.size())
    .filter(i -> i % 1000 == 0)       // 例えば1000件ごとに抽出
    .mapToObj(list::get)
    .toList();
Java

フィルタ後に上位 N 件を効率取得

「条件に合うものの先頭 N 件」なら、filter → limit → 収集 で一度だけ順次処理します。乱択にせず、短絡で早く止めるのがコツです。

List<Item> topN = items.stream()
    .filter(this::cond)
    .limit(N)
    .toList();
Java

LinkedList に対する注意

LinkedList はインデックスアクセス自体が O(i) です。ランダムアクセスがあるなら ArrayList へ移すか、配列へコピーしてから処理するほうが安全です。

LinkedList<String> ll = // ...
String[] arr = ll.toArray(String[]::new);
String x = (i < arr.length) ? arr[i] : null;
Java

簡易パフォーマンス評価のやり方

ナノ秒計測の雛形

正確なベンチは JMH が理想ですが、まずは「傾向」を見るためにウォームアップと簡易計測を行います。GC や JIT の影響を減らすため、先に同じ処理を数回実行してから本計測に入るのが基本です。

Runnable slow = () -> {
    for (int i = 0; i < 10_000; i++) {
        list.stream().skip(i).findFirst().orElse(null);
    }
};
Runnable fast = () -> {
    for (int i = 0; i < 10_000; i++) {
        list.get(i);
    }
};

// ウォームアップ
slow.run(); fast.run();

// 計測
long t1 = System.nanoTime(); slow.run(); long t2 = System.nanoTime();
long t3 = System.nanoTime(); fast.run(); long t4 = System.nanoTime();

System.out.printf("stream skip=%.3f ms, direct get=%.3f ms%n",
    (t2 - t1) / 1_000_000.0, (t4 - t3) / 1_000_000.0);
Java

JMH を使う場面の指針

微妙な差や並列化の影響を比較したいなら JMH を使うべきです。簡易計測は「桁が違う遅さ」を見分ける用途に限り、最適化やチューニングの最終判断は JMH のベンチで固めると失敗しません。

まとめ

ストリームは「流して処理」するための道具であり、「位置を指定して即取り出す」用途には向きません。乱択アクセスが必要なら直接アクセス（配列・ ArrayList・ for ループ）に寄せ、ストリームを使う場合はインデックスを流すか、一度だけ順次処理して必要なものを集める設計に切り替えましょう。評価はウォームアップ付きの簡易計測で傾向を掴み、最終的に JMH で裏取りするのがプロの手筋です。

スポンサーリンク
タイトルとURLをコピーしました